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

0.2 术语解释

稳定：如果a本来在b前面，且a=b，则排序后a仍然在b前面；不稳定：如果a本来在b前面，且a=b，则排序后a可能会出现在b后面；内部排序：所有排序操作都在内存中完成；外部排序：由于数据太大，所以将数据放在磁盘上，只能通过磁盘和内存之间的数据传输来进行排序；时间复杂度：描述算法运行时间的函数，用大O表示法表示；空间复杂度：描述算法所需的内存空间量。 0.3 算法总结

图片名词解释：

n: 数据大小

k: “桶”的数量

in-place:占用恒定内存，不占用额外内存

Out-place: 占用额外内存

0.5 算法分类

0.6 比较排序和非比较排序的区别

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

在冒泡排序等排序中，问题大小为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){for(int i=0;iarray.length;i++) { for(int j=0;jarray.length - 1 - i;j++){if(array[j] array[j+1]){int temp=array[j];array[j]=array[j+ 1] ;array[j+1]=temp;}}}}return array;}1.4 算法分析

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

2、选择排序（Selection Sort）

最稳定的排序算法之一，因为无论输入什么数据，时间复杂度都是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){for(int i=0;iarray.length;i++){ int minIndex=i;for(int j=i;jarray.length;j++){//遍历剩余未排序元素，继续寻找最小元素if(array[j] array[minIndex]){minIndex=j;} } if(minIndex !=i){int temp=array[minIndex];array[minIndex]=array[i];array[i]=temp;}}}return array;}2.4 算法分析

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

3、插入排序（Insertion Sort）

插入排序（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){for(int i=0;iarray.length - 1;i++ ){int 当前=array[i+1];int index=i;while(index=0 当前array[index]){array[index + 1]=array[index]; index--;}array[index+1]=current;}}返回数组；}3.4 算法分析

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

4、希尔排序（Shell Sort）

希尔排序是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){ if(array.length 0){ int len=array.length; int 间隙=len/2 ； while(间隙0){ for(int i=间隙；i len;i++){ int temp=array[i]; int 索引=i - 间隙； while(索引=0 数组[索引]临时){ 数组[索引+ 间隙]=数组[索引];指数-=缺口； } 数组[索引+间隙]=临时； } 间隙/=2;返回数组； }4.4 算法分析

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

5、归并排序（Merge Sort）

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

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

5.1 算法描述

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

5.3 代码实现

/** * 2路合并算法* @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);return merge(MergeSort(left),MergeSort(right)); } public static int[] merge(int[] left,int[] right){int[] result=new int[left.length + right.length];for(int index=0,i=0, j=0 ; 索引结果.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++];}else{result[index]=left[i++];}}返回结果；}5. 4 算法分析

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

6、快速排序（Quick Sort）

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

6.1 算法描述

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

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

6.3 代码实现

/** * 快速排序算法* @param array * @param low * @param hight */public static void QuickSort(int[] array,int low,int hight){//if (array.length 1 || low 0 || hight=array.length || low hight) return null;if(low hight){int privotpos=分区(array,low,hight);QuickSort(array,low,privotpos - 1);QuickSort(array,privotpos + 1,hight);}}公共静态int 分区(int[] array,int low,int hight){int privot=array[low];while(low hight){while(low hight array[hight]=privot) - -hight;array[low]=array[hight];while(low hight array[low]=privot) ++low;array[hight]=array[low];}array[low]=privot;返回low;} 6.4 算法分析

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

7、堆排序（Heap Sort）

堆的定义如下： 当且仅当满足以下条件时，n 个元素的序列{k1, k2, kn} 称为堆。

堆可以被认为是一棵完全二叉树。而且，每个节点的值都大于或等于其左右子节点的值，称为大顶堆；或者每个节点的值小于或等于其左右子节点的值，称为小顶堆。

堆排序是一种使用堆进行排序的方法。基本思想是：将要排序的序列构造成大顶堆（或小顶堆）。整个序列的最大值（或最小值）就是堆顶的根节点。根节点的值被添加到堆数组的末尾。元素交换，此时最后一个元素为最大值（或最小值），然后将剩余的n-1个序列重构为堆，这样n个元素中的第二大值（或第二小值）将得到， 如此反复，最终得到一个有序序列。

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 代码实现

/** * 调整堆* @param array * @param index * @param length */public static void heapAdjust(int[] array,int index,int length){//保存当前节点的下标int max=index ;//当前节点左子节点的下标int lchild=2*index;//当前节点右子节点的下标int rchild=2*index + 1;if(length lchild array[max ] array[lchild]) {max=lchild;}if(length rchild array[max] array[rchild]){max=rchild;}//如果这个节点小于它的左右孩子的值，则交换它使用最大值并调整堆if (max !=index){int temp=array[index];array[index]=array[max];array[max]=temp;heapAdjust(array,max,length); }}/** * 堆排序* @param array * @return */public static int[] heapSort(int[] array){int len=array.length;//初始化堆并构造最大堆(int i=(len/2 - 1); i=0;i--){heapAdjust(array,i,len);}//将堆顶元素与最后一个元素交换，重新调整堆for(int i=len - 1;i 0;i- -){int temp=array[i];array[i]=array[0];array[0]=temp;heapAdjust(array,0,i );}返回数组；}7.4 算法分析

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

8、计数排序（Counting Sort）

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

计数排序是一种稳定的排序算法。计数排序使用额外的数组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;}intbias ,min=array[0 ],max=array[0];//求最小值和最大值for(int i=0;i array.length;i++){if(array[i] min){min=array[i]; } if(array[i] max){max=array[i];}}//bias bias=0 - min;//打开一个新数组int[] bucket=new int[max - min +1];//数据初始化为0Arrays.fill(bucket, 0);for(int i=0;i array.length;i++){bucket[array[i] +bias] +=1;} int index=0;for (int i=0;ibucket.length;i++){int len=bucket[i];while(len 0){array[index++]=i - 偏差；len --;}} 返回数组；}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、桶排序（Bucket Sort）

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

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

9.1 算法描述

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

9.

10、基数排序（Radix Sort）