【数据结构】关于快速排序,归并排序,计数排序,基数排序,你到底了解多少???(超详解)

本文主要是介绍【数据结构】关于快速排序,归并排序,计数排序,基数排序,你到底了解多少???(超详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言:

🌟🌟Hello家人们,这期继续讲解排序算法的原理,希望你能帮到屏幕前的你。

🌈上期博客在这里:http://t.csdnimg.cn/g7PyB

🌈感兴趣的小伙伴看一看小编主页:GGBondlctrl-CSDN博客

目录

📚️1.比较排序与非比较排序

📚️2.比较排序

2.1快速排序

1.递归基本思想:

2.非递归基本思想 :

 3.Hoare法:

4.挖坑法:

5.双指针(了解):

 6.快速排序总结:

2.2归并排序

1.递归基本思想:

2.非递归基本思想:

3.实现合并:

4.归并排序总结:

📚️3.非比较排序

3.1计数排序

3.2基数排序

📚️4.总结


📚️1.比较排序与非比较排序

排序算法主要分为比较排序和非比较排序两大类:
1.比较排序:

比较算法通过比较元素的大小来确定它们的相对顺序。常见的比较排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等,本期小编将讲述快速排序,归并排序。

2.非比较排序:

非比较排序算法则不依赖于元素之间的直接比较来确定顺序。例如,计数排序、桶排序、基数排序等,小编这期将
 两者的区别:


1.比较排序的优点是其思想相对简单直观,易于理解和实现。但它的缺点也较为明显,比较操作的次数通常与待排序元素的数量呈特定的函数关系,导致其时间复杂度在最坏情况下可能较高。
 
2.非比较排序的优势在于在某些特定情况下,能够在较低的时间复杂度内完成排序。但它们往往需要额外的空间来辅助排序,并且对数据的特征有一定要求。

总的来说,比较排序适用于一般性的排序需求,而非比较排序在数据具有特定特征或对时间复杂度有极高要求时表现出色。具体使用哪种排序算法,取决于数据的特点、问题的规模以及对时间和空间复杂度的权衡。

📚️2.比较排序

2.1快速排序

1.递归基本思想:

任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

这里就要每次根据基准来进行递归,实现快速排序:

图解:

代码实现:

public static void Quick(int[] array,int start,int end){if(start>=end)return;int privot=privot2(array,start,end);Quick(array,start,privot-1);Quick(array,privot+1, end);}

 这里要规定开始的索引下标,以及结束的索引下标; 

2.非递归基本思想 :

在非递归思想就是要运用栈这个结构,我们要找到实现基准查找的左右指针,先导入第一次基准后,进行循环,实现右树基准的查找,这里每次要进行出栈进行基准查找,找完之后进栈左右指针。

代码实现:

  public static void Quicknor(int[] array){Stack<Integer> stack=new Stack<>();int left=0;int right= array.length-1;int privot=privot1(array,left,right);if (privot-1>left){stack.push(left);stack.push(privot-1);}if(privot+1<right){stack.push(privot+1);stack.push(right);}while (!stack.isEmpty()){right=stack.pop();left=stack.pop();privot=privot1(array,left,right);if (privot-1>left){stack.push(left);stack.push(privot-1);}if(privot+1<right){stack.push(privot+1);stack.push(right);}}}

注意:这里要判断基准的左右是否还存在至少两个数据,存在才进栈,否则不进入。 

上述已经完成了基本的递归思想,那么接下来就要进行基准的实现了~~~

 3.Hoare法:

查找基准思路:

设置两个最左端索引(left),和最右端索引(right),和一个关键下标表示key;最右端索引进行向前遍历,若所表示的值大于key,那么right--,如果发现了大于key的值,那么就进行left向前遍历,若小于key,那么left++,直到发现比key大的数据,然后交换right和left,直到两者相遇,最后与key进行交换。

图解: 

代码实现:

 public static int privot(int[] array,int left,int right){int key=array[left];int i=left;while (right>left){while (array[right]>=key&&left<right){right--;}while (array[left]<=key&&left<right){left++;}swap(right,left,array);}swap(i,left,array);return left;}
4.挖坑法:

查找基本思路:

和上述Hoare思想基本一致,但是当right索引发现比key小的数值时,left索引所指向的数值就为right索引所指的值,当left索引发现比key大的数值时,right索引所指向的数值就为left索引所指的值,两者相遇后与最初始的left索引所指的数值进行交换。

 图解:

代码实现:

 public static int  privot1(int[] array,int left,int right){int privot=array[left];while (left<right){while (array[right]>=privot&&left<right){right--;}array[left]=array[right];while (array[left]<=privot&&left<right){left++;}array[right]=array[left];}array[left]=privot;return left;}
5.双指针(了解):

代码实现:

 public static int privot2(int[] array,int left,int right){int prev=left;int k=array[prev];int cur=left+1;while (cur<=right){if(array[cur]<k&&(++prev)!=cur){swap(cur,prev,array);}cur++;}swap(prev,left,array);return prev;}

这里的双指针法了解就好,小编不再赘述,可以画图理解一下。

 6.快速排序总结:


1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序


2. 时间复杂度:O(N*logN)


3. 空间复杂度:O(logN)


4. 稳定性:不稳定

2.2归并排序

1.递归基本思想:

运用递归实现,我们需要进行查找中间索引,进行两两拆分直到只有一个数据,再实现两两合并。

图解: 

代码实现: 

public static void Merge(int[] array,int left,int right){if(left>=right){return;}int mid=(left+right)/2;Merge(array,left,mid);Merge(array,mid+1,right);mergeCore(array,left,right,mid);}
2.非递归基本思想:

即分组进行合并排序,先是一个和一个,再次为二和二到最后全部合并(这里的合并是排好序的)

图解:

代码实现:

public static void Mergenor(int[] array){int left;int right;int gap=1;int mid;while (gap<array.length){for (int i = 0; i < array.length; i+=2*gap) {left=i;mid=left+gap-1;right=mid+gap;if(mid >= array.length) {mid = array.length-1;}if(right >= array.length) {right = array.length-1;}mergeCore(array,left,right,mid);}gap*=2;}}
3.实现合并:

实现合并思想:

小编在这里认为当两个数组进行合并时,第一个数组的第一个元素与第二个数组的第一个元素进行比较,如果那个更小,在与另一个数组下标加一后的值进行比较,直到索引越界。

图解: 

代码实现 :

 public static void mergeCore(int[] array,int left,int right,int mid){int[] tmp=new int[right-left+1];int k=0;int s1=left;int s2=mid+1;while (s1<=mid&&s2<=right){if(array[s1]<=array[s2]){tmp[k]=array[s1];k++;s1++;}else {tmp[k]=array[s2];k++;s2++;}}while (s1>mid&&s2<=right){tmp[k]=array[s2];s2++;k++;}while (s2>right&&s1<=mid){tmp[k]=array[s1];k++;s1++;}for (int i = 0; i <k ; i++) {array[i+left]=tmp[i];}}
4.归并排序总结:

1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(N)
4. 稳定性:稳定

📚️3.非比较排序

3.1计数排序

思路步骤:

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

图解: 

代码实现: 

 public static void CountSort(int[] array){int max=array[0];int min=array[0];for (int i = 1; i < array.length; i++) {if (array[i]<min){min=array[i];}if(array[i]>max){max=array[i];}}int[] tmp=new int[max-min+1];for (int i = 0; i < array.length ; i++) {tmp[array[i]-min]++;}for (int i = 0; i < tmp.length ; i++) {while (tmp[i]!=0){System.out.print(i+min+" ");tmp[i]--;}}}

注意:若为90-100区间,不可能申请100个长度,这样会造成浪费,所以数组长度是最大值减去最小值加1;所以0下标的值就为数据0+数据最小值,1下标的值为1+最小值。

计数排序总结:

1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
2. 时间复杂度: O(MAX(N, 范围 ))
3. 空间复杂度: O( 范围 )
4. 稳定性:稳定

3.2基数排序

思路:

通过二维数组进行存储,导入对应位置的数值,然后再设置一个一维数组进行每行个数的值,进行打印,循环最大数的长度,就能在最后一次打印中取得顺序数组。

 图解:

代码如下: 

 public static void BaseSort(int[] array){int max=max(array);int maxLength=0;while (max!=0){max/=10;maxLength++;}int[][] bucket = new int[10][array.length-1];int[] elementCount = new int[10];int n=1;for (int i = 0; i < maxLength; i++) {for (int j = 0; j < array.length ; j++) {int element=array[j]/n%10;bucket[element][elementCount[element]]=array[j];elementCount[element]++;}//拿出数据int index=0;for (int j = 0; j <elementCount.length ; j++) {if(elementCount[j]!=0){for (int k = 0; k < elementCount[j]; k++) {array[index]=bucket[j][k];index++;}}elementCount[j]=0;}n*=10;}}public static int max(int[] array){int max=array[0];for (int i = 1; i < array.length ; i++) {if(array[i]>max){max=array[i];}}return max;}
}

注意:这里不仅要求最大值,还要求最大值的长度来表示循环次数,每次循环条件是要变化的,依次按照位数来进行操作,每次输出后再重新载入到二维数组中。

📚️4.总结

💬💬小编这期讲解了关于比较排序的最后两个排序:快速排序,归并排序,关于他们的代码以及思路都罗列了出来,还有包括非比较排序的基数排序,计数排序的思路原理和代码实现。

对于每个排序都要掌握它的基本原理,对于以上两个比较排序来说,还要了解二叉树的概念。

🌅🌅🌅~~~~最后希望与诸君共勉,共同进步!!!


                               💪💪💪以上就是本期内容了, 感兴趣的话,就关注小编吧。

                                                         😊😊  期待你的关注~~~ 

 

这篇关于【数据结构】关于快速排序,归并排序,计数排序,基数排序,你到底了解多少???(超详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1099607

相关文章

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

详解C#如何提取PDF文档中的图片

《详解C#如何提取PDF文档中的图片》提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使用,下面我们就来看看如何使用C#通过代码从PDF文档中提取图片吧... 当 PDF 文件中包含有价值的图片,如艺术画作、设计素材、报告图表等,提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使

Android中Dialog的使用详解

《Android中Dialog的使用详解》Dialog(对话框)是Android中常用的UI组件,用于临时显示重要信息或获取用户输入,本文给大家介绍Android中Dialog的使用,感兴趣的朋友一起... 目录android中Dialog的使用详解1. 基本Dialog类型1.1 AlertDialog(

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2