十大经典排序算法最强总结（含JAVA代码实现）

这几天一直在研究排序算法。看了很多博客，发现网上有些文章对排序算法解释的不是很透彻，而且有很多代码是错误的。例如，有些文章中，“桶排序”算法中要对每个桶进行排序，就直接使用Collection.sort()函数。虽然这样可以达到效果，但是对于算法研究来说却是不可能的。

0.排序算法说明

0.1 排序的定义

根据某个关键字对对象序列进行排序。

0.2 术语解释

稳定：如果a本来在b前面，且a=b，则排序后a仍然在b前面；不稳定：如果a本来在b前面，且a=b，则排序后a可能会出现在b后面；内部排序：所有排序操作都在内存中完成；外部排序：因为数据太大，所以将数据放在磁盘上，通过磁盘和内存之间的数据传输来进行排序；时间复杂度：执行一个算法所花费的时间。空间复杂度：运行程序所需的内存量。

参考：稳定排序和不稳定排序

0.3 算法总结

图片名词解释：

n: 数据规模k: “桶”数量In-place: 占用恒定内存，不占用额外内存Out-place: 占用额外内存0.4 算法分类

0.5 比较与非比较的区别

常见的快速排序、归并排序、堆排序、冒泡排序等都属于比较排序。在排序的最终结果中，元素之间的顺序取决于它们之间的比较。每个数字必须与其他数字进行比较以确定其位置。

在冒泡排序等排序中，问题大小为n，由于需要进行n次比较，因此平均时间复杂度为O(n)。在归并排序、快速排序等排序中，通过分而治之的方法将问题规模缩小到logN倍，因此平均时间复杂度为O(nlogn)。

比较排序的优点是适用于各种规模的数据，并且无论数据的分布如何都可以进行排序。可以说，比较排序适用于所有需要排序的情况。

计数排序、基数排序和桶排序都是非比较排序。非比较排序通过确定每个元素前面应有多少元素进行排序。对于数组arr，计算arr[i]之前有多少个元素，那么arr[i]在排序数组中的位置就唯一确定了。

非比较排序只需判断每个元素之前存在的元素个数，一次遍历即可全部解决。算法时间复杂度为O(n)。

非比较排序的时间复杂度最低，但确定唯一位置会占用空间。因此，对数据规模和数据分布有一定的要求。

1. 冒泡排序

冒泡排序是一种简单的排序算法。它反复遍历要排序的序列，一次比较两个元素，如果顺序错误则交换它们。重复访问数组的工作，直到不需要再进行交换，这意味着数组已经排序完毕。

这个算法的名字来源于这样一个事实：较小的元素会通过交换慢慢“浮动”到数组的顶部。冒泡排序简介：冒泡排序

1.1 算法描述

比较相邻元素。如果第一个大于第二个，则交换它们；对每对相邻元素做同样的操作，从第一对开始到最后一对结束，这样最后的元素应该是最大的数字；对除最后一个元素之外的所有元素重复上述步骤；重复步骤1至3，直至排序完成。 1.2 GIF演示

1.3 代码实现

/** * 冒泡排序* * @param array * @return */public static int[] bubbleSort(int[] array) { if (array.length==0) return array; for (int i=0; i array.length; i++) for (int j=0; j array.length - 1 - i; j++) if (array[j + 1] array[j]) { int temp=array [j+1]；数组[ j + 1]=数组[j];数组[j]=温度；返回数组； }1.4 算法分析

最好情况：T(n)=O(n) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(n2)

2. 选择排序

最稳定的排序算法之一，因为无论输入什么数据，时间复杂度都是O(n2)，所以使用时数据量越小越好。唯一的优点可能就是不占用额外的内存空间。从理论上讲，选择排序也可能是大多数人在排序时想到的最常见的排序方法。

选择排序是一种简单直观的排序算法。工作原理：首先，找到未排序序列中最小（大）的元素，并将其存储在已排序序列的起始位置。然后，继续从剩余的未排序元素中找到最小（大）的元素，然后将其放入已排序的序列中。的结束。依此类推，直到所有元素都排序完毕。选择排序简介：选择排序

2.1 算法描述

对n条记录进行直接选择排序，经过n-1次直接选择排序即可得到有序结果。具体算法描述如下：

初始状态：无序区为R[1.n]，有序区为空；在第i 次排序开始时（i=1,2,3.n-1），当前有序区域和无序区域分别为R[1.i-1] 和R(i.n)。该排序操作从当前无序区域中选择键最小的记录R[k]，并将其与无序区域中的第一条记录R交换，使得R[1.i]和R[i+1. n) 分别成为记录数增加1的新的有序区域和记录数减少1的新的无序区域； n-1 遍完成并且数组已排序。 2.2 GIF演示

2.3 代码实现

/** * 选择排序* @param array * @return */public static int[] SelectionSort(int[] array) { if (array.length==0) return array; for (int i=0; i array.length; i++) { int minIndex=i; for (int j=i; j array.length; j++) { if (array[j] array[minIndex]) //找到最小的数minIndex=j; //改变最小的数，保存该数的索引} int temp=array[minIndex];数组[minIndex]=数组[i];数组[i]=温度；返回数组； }2.4 算法分析

最好情况：T(n)=O(n2) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(n2)

3.插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它通过构建有序序列来工作。对于未排序的数据，它会在已排序的序列中从后向前扫描，找到对应的位置并插入。在插入排序的实现中，通常使用就地排序（即只使用O(1)额外空间的排序）。因此，在从后向前扫描的过程中，需要反复地、逐渐地将排序后的元素向后移动。为最新元素提供插入空间。插入排序：直接插入排序

3.1 算法描述

一般来说，插入排序是使用原地在数组上实现的。具体算法描述如下：

从第一个元素开始，可以认为该元素已经排序；取出下一个元素，在排序后的元素序列中从后向前扫描；如果元素（已排序）大于新元素，则将该元素移动到下一个位置；重复步骤3，直到找到排序元素小于等于新元素的位置；将新元素插入到该位置；重复步骤2~5。 3.2 动画演示

3.2 代码实现

/** * 插入排序* @param array * @return */public static int[] insertSort(int[] array) { if (array.length==0) return array;整数电流； for (int i=0; i array.length - 1; i++) { current=array[i + 1]; int preIndex=i; while (preIndex=0 当前数组[preIndex]) { 数组[preIndex + 1]=数组[preIndex];预索引- -; } 数组[preIndex + 1]=当前；返回数组； }3.4 算法分析

最好情况：T(n)=O(n) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(n2)

4.希尔排序

希尔排序是Donald Shell于1959年提出的一种排序算法。希尔排序也是一种插入排序。它是简单插入排序的更高效版本，也称为收缩增量排序。同时，该算法也是最早突破O(n2)的算法之一。它与插入排序的不同之处在于它首先比较较远的元素。希尔排序也称为减少增量排序。希尔排序： 希尔排序

希尔排序是将表中的记录按照一定的增量进行分组，并使用直接插入排序算法对每个组进行排序；随着增量逐渐减小，每组包含的关键词越来越多。当增量减至1 时，整个文件被分为一组，算法终止。

4.1 算法描述

我们来看看希尔排序的基本步骤。这里我们选择增量gap=length/2，并以gap=gap/2的方式继续减少增量。我们可以用一个序列来表示这种增量选择，{n/2,(n/2)/2…1}，称为增量序列。希尔排序增量序列的选择和证明是一个数学问题。我们选择的增量序列是比较常用的，也是Hill推荐的增量。这称为希尔增量。但事实上，这种增量序列并不是最优的。出色的。这里我们以Hill 增量为例。

首先将整个待排序的记录序列分成若干子序列进行直接插入排序。具体算法描述：

选择增量序列t1,t2,tk，其中titj,tk=1；根据增量序列数k对序列进行k次排序；在每一次排序过程中，根据对应的增量ti，将待排序的序列分成若干个长度为m的子序列，对每个子表进行直接插入排序。只有当增量因子为1时，整个序列才被当作一个表来处理，表的长度就是整个序列的长度。 4.2 工艺演示

4.3 代码实现

/** * 希尔排序* * @param array * @return */public static int[] ShellSort(int[] array) { int len=array.length; int temp, 间隙=len/2; while (间隙0 ) { for (int i=间隙； i len; i++) { temp=array[i]; int preIndex=i - 间隙； while (preIndex=0 array[preIndex] temp) { array[preIndex + 间隙]=array[ preIndex]; preIndex -=间隙； } 数组[preIndex + 间隙]=temp; } 间隙/=2;返回数组； }4.4 算法分析

最好情况：T(n)=O(nlog2 n) 最坏情况：T(n)=O(nlog2 n) 平均情况：T(n)=O(nlog2n)

5. 归并排序

与选择排序一样，合并排序的性能不受输入数据的影响，但其性能比选择排序好得多，因为它的时间复杂度始终为O(n log n)。代价是额外的内存空间。归并排序：归并排序

归并排序是一种基于归并操作的有效排序算法。该算法是分而治之法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已经有序的子序列合并，得到完全有序的序列；即先对每个子序列进行排序，然后对子序列段进行排序。如果两个有序列表合并为一个有序列表，则称为2 路合并。

5.1 算法描述

将长度为n的输入序列分为两个长度为n/2的子序列；分别对两个子序列进行归并排序；将两个已排序的子序列合并为最终的排序序列。 5.2 GIF演示

5.3 代码实现

/** * 合并排序* * @param array * @return */public static int[] MergeSort(int[] array) { if (array.length 2) return array; int mid=array.length/2; int[ ] left=Arrays.copyOfRange(array, 0, mid); int[] right=Arrays.copyOfRange(array, mid, array.length);返回合并（合并排序（左），合并排序（右））； } /** * 合并排序—— 将两个已排序数组合并为一个已排序数组* * @param left * @param right * @return */public static int[] merge(int[] left, int[] right) { int[ ] 结果=new int[left.length + right.length]; for (int index=0, i=0, j=0; 索引result.length; index++) { if (i=left.length) result[index]=right[j++]; } else if (j=right.length) result[index]=left[i++]; else if (左[i] 右[j]) 结果[索引]=右[j++];否则结果[索引]=左[i++];返回结果； }5.4 算法分析

最好情况：T(n)=O(n) 最坏情况：T(n)=O(nlogn) 平均情况：T(n)=O(nlogn)

6. 快速排序

快速排序的基本思想是通过一次排序将待排序的记录分成两个独立的部分。如果一部分记录的关键字小于另一部分记录的关键字，则可以将两部分记录分别排序，以达到整个序列有序。快速排序：快速排序

6.1 算法描述

快速排序使用分而治之的方法将列表分为两个子列表。具体算法描述如下：

从数组中选取一个元素，称为“枢轴”；对数组进行重新排序，使得所有小于主元值的元素都放在主元的前面，所有大于主元值的元素都放在主元的后面（相同的数字可以到任一侧）。该分区退出后，碱基位于序列的中间。这称为分区操作；它递归地对小于主元值的元素子数组和大于主元值的元素子数组进行排序。 6.2 GIF演示

6.3 代码实现

/** * 快速排序方法* @param array * @param start * @param end * @return */public static int[] QuickSort(int[] array, int start, int end) { if (array.length 1 | 1) | 开始0 || 结束=array.length || 开始结束) 返回null; int SmallIndex=分区(数组， 开始， 结束); if (smallIndex start) QuickSort(数组， start,smallIndex - 1); if (smallIndex end ) QuickSort(数组，smallIndex + 1, end);返回数组； } /** * 快速排序算法——partition * @param array * @param start * @param end * @return */public static int partition(int[] array , int start, int end) { int hub=(int) (开始+ Math.random() * (结束- 开始+ 1)); int 小索引=开始- 1;交换（数组，枢轴，结束）； for ( int i=start; i=end; i++) if (array[i]=array[end]) {smallIndex++;如果（我小索引）交换（数组，我，小索引）；返回小索引； } /** * 交换数组中的两个元素* @param array * @param i * @param j */public static void swap(int[] array, int i, int j) { int temp=array[i];数组[i]=数组[j]；数组[j]=温度； }6.4 算法分析

最好情况：T(n)=O(nlogn) 最坏情况：T(n)=O(n2) 平均情况：T(n)=O(nlogn)

7. 堆排序

堆排序是指利用堆的数据结构设计的排序算法。堆叠是一种近似完全二叉树的结构，满足堆叠的性质：即子节点的键值或索引总是小于（或大于）其父节点。堆排序：堆排序

7.1 算法描述

将待排序关键字的初始序列（R1,R2.Rn）构造成一个大顶堆，即初始无序区；将最上面的元素R[1]与最后一个元素R[n]交换，此时得到一个新的无序区域(R1,R2,…Rn-1)和一个新的有序区域(Rn)，并满足R [1,2.n-1]=R[n]；由于堆顶新增的R[1]可能违反堆的属性，因此需要将当前无序区（R1,R2,Rn-1）调整为新的堆，并且然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2.Rn-2)和新的有序区(Rn-1,Rn)。重复这个过程，直到有序区域的元素个数为n-1，则整个排序过程完成。 7.2 GIF演示

7.3 代码实现

注意：这里使用了完全二叉树的一些属性：

最好情况：T(n)=O(nlogn) 最坏情况：T(n)=O(nlogn) 平均情况：T(n)=O(nlogn)

8. 计数排序

计数排序的核心是将输入数据值转换为键并存储在额外开辟的数组空间中。计数排序作为一种线性时间复杂度排序，要求输入数据必须是一定范围内的整数。

计数排序是一种稳定的排序算法。计数排序使用额外的数组C，其中第i个元素是要排序的数组A中值等于i的元素的个数。然后根据数组C将A中的元素排列到正确的位置。它只能对整数进行排序。

8.1 算法描述

找到待排序数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，并将其存储在数组C的第i项中；累加所有计数（从C 中的第一个元素开始，将每个项目添加到前一个项目）；反向填充目标数组：将每个元素i 放置在新数组的第C(i) 项中，并为每个放置的元素从C(i) 中减去1。 8.2 GIF演示

8.3 代码实现

/** * 计数排序* * @param array * @return */public static int[] CountingSort(int[] array) { if (array.length==0) return array; int 偏差，最小值=数组[0]，最大值=数组[0]； for (int i=1; i array.length; i++) { if (array[i] max) max=array[i]; } if (array[i] min) min=array[i]; } 偏差=0 - 分钟； int[] Bucket=new int[max - min + 1]; Arrays.fill(桶， 0); for (int i=0; i array.length; i++) { 桶[array[i] + 偏差]++; } int 索引=0, i=0; while (index array.length) { if (bucket[i] !=0) { array[index]=i - 偏差；桶[i]——；索引++；否则我++；返回数组； }8.4 算法分析

当输入元素为n个0到k之间的整数时，其运行时间为O(n + k)。计数排序不是比较排序，并且排序比任何比较排序算法都快。由于用于计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值之差加1），这就使得计数排序对于数据范围较大的数组，需要大量数据。时间和记忆。

最好情况：T(n)=O(n+k) 最坏情况：T(n)=O(n+k) 平均情况：T(n)=O(n+k)

9. 桶排序

桶排序是计数排序的升级版本。它利用了函数的映射关系。效率的关键在于这个映射函数的确定。

桶排序的工作原理：假设输入数据服从均匀分布，将数据划分到有限个桶中，然后对每个桶分别进行排序（也可以使用其他排序算法或者继续递归使用）种类

9.1 算法描述

手动设置一个BucketSize，决定每个bucket可以容纳多少个不同的值（例如当BucketSize==5时，bucket可以存储{1,2,3,4,5}，但容量不限制）即即，100 3) 可存储；遍历输入数据，将数据一一放入对应的桶中；对每个不为空的桶进行排序，可以使用其他排序方法，也可以递归地使用桶排序；从不将已排序的数据连接到空桶中。注意，如果递归地使用桶排序对每个桶进行排序，当桶数为1时，必须在下一个循环中手动减少BucketSize并增加桶数，否则会陷入死循环，导致内存溢出。

9.2 图片演示

9.3 代码实现

/** * 桶排序* * @param array * @param bucketSize * @return */public static ArrayListInteger BucketSort(ArrayListInteger array, int bucketSize) { if (array==null || array.size() 2) return array; } int max=array.get(0), min=array.get(0); //求最大值和最小值for (int i=0; i array.size(); i++) { if (array.get(i ) max) max=array.get(i); if (array.get(i) min) min=array.get(i); } int BucketCount=(最大值- 最小值)/BucketSize + 1; ArrayListArrayListInteger bucketArr=new ArrayList (buck