十大经典排序算法回顾

1.1.排序定义

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

1.2.排序术语

稳定：如果a本来在b前面，且a=b，则排序后a仍然在b前面；

不稳定：如果a本来在b前面，且a=b，那么排序后a可能会出现在b后面；

内部排序：所有排序操作都在内存中完成；

外部排序：由于数据太大，所以将数据放在磁盘上，只能通过磁盘和内存之间的数据传输来进行排序；

时间复杂度：执行算法所需的时间。

空间复杂度：运行程序所需的内存量。

1.3.算法总结

（注：n指数据大小；k指“桶”的数量；In-place指占用常量内存，不占用额外内存；Out-place指占用额外内存）

1.4.算法分类

1.5.比较与非比较的区别

常见的快速排序、归并排序、堆排序、冒泡排序等都属于比较排序。在排序的最终结果中，元素之间的顺序取决于它们之间的比较。每个数字必须与其他数字进行比较以确定其位置。在冒泡排序等排序中，问题大小为n，由于需要进行n次比较，因此平均时间复杂度为O(n)。在归并排序、快速排序等排序中，通过分而治之的方法将问题规模缩小到logN倍，因此平均时间复杂度为O(nlogn)。比较排序的优点是适用于各种规模的数据，并且无论数据的分布如何都可以进行排序。可以说，比较排序适用于所有需要排序的情况。计数排序、基数排序和桶排序都是非比较排序。非比较排序通过确定每个元素前面应有多少元素进行排序。对于数组arr，计算arr[i]之前有多少个元素，那么arr[i]在排序数组中的位置就唯一确定了。非比较排序只需判断每个元素之前存在的元素个数，一次遍历即可全部解决。算法时间复杂度为O(n)。非比较排序的时间复杂度最低，但确定唯一位置会占用空间。因此，对数据规模和数据分布有一定的要求。

2. 冒泡排序

冒泡排序是一种简单的排序算法。它反复遍历要排序的序列，一次比较两个元素，如果顺序错误则交换它们。重复访问数组的工作，直到不需要再进行交换，这意味着数组已经排序完毕。这个算法的名字来源于这样一个事实：较小的元素会通过交换慢慢“浮动”到数组的顶部。

2.1.算法说明

比较相邻元素。如果第一个比第二个大，则交换它们；

对每对相邻元素都做同样的事情，从开始的第一对到最后的最后一对，这样最后的元素应该是最大的数字；

对除最后一个元素之外的所有元素重复上述步骤；

重复步骤1~3，直至排序完成。

2.2. GIF演示

2.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];array[ j + 1]=array[j];array[j]=temp;}返回数组；}2.4.算法分析

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

3.选择排序

最稳定的排序算法之一，因为无论输入什么数据，时间复杂度都是O(n2)，所以使用时数据量越小越好。唯一的优点可能就是不占用额外的内存空间。从理论上讲，选择排序也可能是大多数人在排序时想到的最常见的排序方法。选择排序是一种简单直观的排序算法。工作原理：首先，找到未排序序列中最小（大）的元素，并将其存储在已排序序列的起始位置。然后，继续从剩余的未排序元素中找到最小（大）的元素，然后将其放入已排序的序列中。的结束。依此类推，直到所有元素都排序完毕。

3.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 遍结束时，数组已排序。

3.2. GIF演示

3.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];array[minIndex]=array[i];array[i]=temp;}return array;}3.4.算法分析

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

4.插入排序

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

4.1.算法说明

一般来说，插入排序是使用原地在数组上实现的。具体算法描述如下： 从第一个元素开始，可以认为该元素已排序；取出下一个元素，在排序后的元素序列中从后向前扫描；如果元素（已排序）大于新元素，则将元素移动到下一个位置；重复步骤3，直到找到排序元素小于等于新元素的位置；将新元素插入到该位置；重复步骤2~5。 4.2、动画演示

4.3.代码实现

/** * 插入排序* @param array * @return */public static int[] insertSort(int[] array) {if (array.length==0)return array;int current;for (int i=0; i array.length - 1; i++) {current=array[i + 1];int preIndex=i;while (preIndex=0 当前数组[preIndex]) {array[preIndex + 1]=array[preIndex];preIndex- -;}array[preIndex + 1]=current;}return array;}4.4、算法分析

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

5. 希尔排序

希尔排序是Donald Shell于1959年提出的一种排序算法。希尔排序也是一种插入排序。它是简单插入排序的更高效版本，也称为收缩增量排序。同时，该算法也是最早突破O(n2)的算法之一。它与插入排序的不同之处在于它首先比较较远的元素。希尔排序也称为减少增量排序。希尔排序是将表中的记录按照一定的增量进行分组，并使用直接插入排序算法对每个组进行排序；随着增量逐渐减小，每组包含的关键词越来越多。当增量减至1 时，整个文件被分为一组，算法终止。

5.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时，整个序列才被当作一个表来处理，表的长度就是整个序列的长度。

5.2.工艺演示

5.3.代码实现

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

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

6. 归并排序

与选择排序一样，合并排序的性能不受输入数据的影响，但其性能比选择排序好得多，因为它的时间复杂度始终为O(n log n)。代价是额外的内存空间。归并排序是一种基于归并操作的有效排序算法。该算法是分而治之法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已经有序的子序列合并，得到完全有序的序列；即先对每个子序列进行排序，然后对子序列段进行排序。如果两个有序列表合并为一个有序列表，则称为2 路合并。

6.1.算法说明

将长度为n的输入序列分为两个长度为n/2的子序列；

对这两个子序列使用归并排序；

将两个已排序的子序列合并为最终的已排序序列。

6.2. GIF演示

6.3.代码实现

/** * 合并排序* * @param array * @return */public static int[] MergeSort(int[] array) {if (array.length 2) return array;int mid=array.length/2;int[ ] 左=Arrays.copyOfRange(array, 0, mid);int[] 右=Arrays.copyOfRange(array, mid, array.length); return merge(MergeSort(left), MergeSort(right));}/** * 合并排序—— 将两个已排序数组合并为一个已排序数组* * @param left * @param right * @return */public static int[] merge (int[] left, int[] right) {int[ ] result=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 (left[i] right[j] )result[index]=right[j++];elseresult[index ]=left[i++];}返回结果；}6.4.算法分析

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

7. 快速排序

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

7.1.算法说明

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

从序列中挑选出一个元素称为“枢轴”；

对数组重新排序，使所有小于基值的元素都放在基数前面，所有大于基值的元素放在基数后面（相同的数字可以到任意一侧）。该分区退出后，碱基位于序列的中间。这称为分区操作；

对小于基值的元素子数组和大于基值的元素子数组进行递归排序。

7.2. GIF演示

7.3.代码实现

/** * 快速排序方法* @param array * @param start * @param end * @return */public static int[] QuickSort(int[] array, int start, int end) {if (array.length 1 | 1) | start 0 || end=array.length start end) return null;intsmallIndex=分区(array, start, end);if (smallIndex start)QuickSort(array, start,smallIndex - 1);if (smallIndex end) )QuickSort(array,smallIndex + 1, end);return array;}/** * 快速排序算法——partition * @param array * @param start * @param end * @return */public static int partition(int[] array , int start, int end) {int hub=(int) (start + Math.random() * (end - start + 1));intsmallIndex=start - 1;swap(array,pivot,end);for ( int i=start; i=end; i++)if (array[i]=array[end]) {smallIndex++;if (ismallIndex)swap(array, i,smallIndex);}returnsmallIndex;} /** * 交换数组中的两个元素* @param array * @param i * @param j */public static void swap(int[] array, int i, int j) {int temp=array[i];array[i]=array [j];数组[j]=temp;}7.4。算法分析

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

8. 堆排序

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

8.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，则整个排序过程完成。 8.2. GIF演示

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

9. 计数排序

计数排序的核心是将输入数据值转换为键并存储在额外开辟的数组空间中。计数排序作为一种线性时间复杂度排序，要求输入数据必须是一定范围内的整数。计数排序是一种稳定的排序算法。计数排序使用额外的数组C，其中第i个元素是要排序的数组A中值等于i的元素的个数。然后根据数组C将A中的元素排列到正确的位置。它只能对整数进行排序。

9.1.算法说明

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

9.3.代码实现

/** * 计数排序* * @param array * @return */public static int[] CountingSort(int[] array) {if (array.length==0) return array;intbias, min=array[0] , max=array[0];for (int i=1; i array.length; i++) {if (array[i] max)max=array[i];if (array[i] min)min=array[ i];}bias=0 - min;int[] bucket=new int[max - min + 1];Arrays.fill(bucket, 0);for (int i=0; i array.length; i++) {bucket [array[i] + 偏差]++;}int index=0, i=0;while (index array.length) {if (bucket[i] !=0) {array[index]=i - 偏差；bucket [i]--;index++;} elsei++;}返回数组；}9.4、算法分析

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

10. 桶排序

桶排序是计数排序的升级版本。它利用了函数的映射关系。效率的关键在于这个映射函数的确定。桶排序的工作原理：假设输入数据服从均匀分布，将数据划分到有限个桶中，然后对每个桶分别进行排序（也可以使用其他排序算法或者继续递归使用）进行排序。

10.1.算法说明

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

10.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);}intbucketCount=(max - min)/bucketSize + 1;ArrayListArrayListIntegerbucketArr=new ArrayList (bucketCount);ArrayListInteger resultArr=new ArrayList();for (int i=0; i bucketCount; i++) {bucketArr.add(new ArrayListInteger());}for (int i=0; i array.size (); i++) {bucketArr.get((array.get(i) - min)/bucketSize).add(array.get(i));}for (int i=0; i bucketCount; i++) {if ( bucketSize==1) { //如果排序后的数组中有重复的数字，感谢好友@jianfengrenranshifeng指出错误for (int j=0; j bucketArr.get(i).size(); j++)resultArr .add(降压