【数据结构】关于快速排序，归并排序，计数排序，基数排序，你到底了解多少？？？（超详解）

前言：

🌟🌟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.总结

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

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

🌅🌅🌅~~~~最后希望与诸君共勉，共同进步！！！

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

😊😊 期待你的关注~~~