概述

因为健忘，加上对各种排序算法理解不深刻，过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结，强行学习。首先罗列一下常见的十大排序算法：

• 直接插入排序

• 希尔排序

• 简单选择排序

• 堆排序

• 冒泡排序

• 快速排序

• 归并排序

• 基数排序

其中我们讨论的这八大排序算法它们都属于内部排序，也就是只考虑数据量较小仅需要使用内存的排序算法，他们之间关系如下：

一、直接插入排序（Insertion Sort）

插入排序的设计初衷是 往有序的数组中快速插入一个新的元素 。它的算法思想是：把要排序的数组分为了两个部分, 一部分是数组的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素. 其中第一部分的排序也是通过再次拆分为两部分来进行的.

插入排序由于操作不尽相同, 可分为 直接插入排序 折半插入排序(又称二分插入排序), 链表插入排序希尔排序我们先来看下直接插入排序。

1、基本思想

直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。

2、算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

①. 从第一个元素开始，该元素可以认为已经被排序

②. 取出下一个元素，在已经排序的元素序列中从后向前扫描

③. 如果该元素（已排序）大于新元素，将该元素移到下一位置

④. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⑤. 将新元素插入到该位置后

⑥. 重复步骤②~⑤

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序

3、代码实现

 /** 

直接插入排序复杂度如下：

平均 时间复杂度	最好情况	最坏情况	空间复杂度
O(n²)	O(n²)	O(n²)	O(1)

Tips: 由于直接插入排序每次只移动一个元素的位， 并不会改变值相同的元素之间的排序， 因此它是一种稳定排序。

二、希尔排序（Shell Sort）

第一个突破O(n^2)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素。

希尔排序，也称 递减增量排序算法 ，1959年Shell发明。是插入排序的一种高速而稳定的改进版本。

希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。

可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是 初次取数组长度的一半 为增量，之后每次再减半，直到增量为1。更好的步长序列取值可以参考维基百科。

2、算法描述

①. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（ 一般初次取数组半长，之后每次再减半，直到增量为1 ）

②. 按增量序列个数k，对序列进行k 趟排序；

③. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

3、代码实现

以下是我自己的实现，可以看到实现很幼稚，但是好处是理解起来很简单。因为没有经过任何的优化，所以不建议大家直接使用。建议对比下方的维基百科官方实现代码，特别是步长取值策略部分。

以下是 选择排序 复杂度:

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n²)	O(n²)	O(n²)	O(1)

选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。

四、堆排序（Heap Sort）

1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd) 和威廉姆斯(J．Williams) 在1964年共同发明了著名的堆排序算法(Heap Sort).

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

ki <= k(2i) 或 ki >= k(2i)

ki <= k(2i+1) ki >= k(2i+1)

把此序列对应的二维数组看成一个完全二叉树。那么堆的含义就是： 完全二叉树中任何一个非叶子节点的值均不大于（或不小于）其左，右孩子节点的值。 由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。因此我们可使用大顶堆进行升序排序, 使用小顶堆进行降序排序。

1、基本思想

此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。

2、算法描述

①. 先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.

②. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1..n-1]和有序区K[n], 且满足K[1..n-1].keys <= K[n].key

③. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n-1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.

动图效果如下所示：

3、代码实现

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆函数，二是反复调用建堆函数以选择出剩余未排元素中最大的数来实现排序的函数。

总结起来就是定义了以下几种操作：

• 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点

• 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序

• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

对于堆节点的访问：

父节点i的左子节点在位置： (2*i+1) ;

父节点i的右子节点在位置： (2*i+2) ;

子节点i的父节点在位置： floor((i-1)/2) ;

/**

* 堆排序

*

* 1. 先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.

* 2. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1..n−1]和有序区K[n], 且满足K[1..n−1].keys⩽K[n].key

* 3. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n−1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.

* @param arr 待排序数组

*/

public static void heapSort(int[] arr){

for(int i = arr.length; i > 0; i–){

max_heapify(arr, i);

int temp = arr[0]; //堆顶元素(第一个元素)与Kn交换

arr[0] = arr[i-1];

arr[i-1] = temp;

}

}

private static void max_heapify(int[] arr, int limit){

if(arr.length <= 0 || arr.length < limit) return;

int parentIdx = limit / 2;

for(; parentIdx >= 0; parentIdx–){

if(parentIdx * 2 >= limit){

continue;

}

int left = parentIdx * 2; //左子节点位置

int right = (left + 1) >= limit ? left : (left + 1); //右子节点位置，如果没有右节点，默认为左节点位置

int maxChildId = arr[left] >= arr[right] ? left : right;

if(arr[maxChildId] > arr[parentIdx]){ //交换父节点与左右子节点中的最大值

int temp = arr[parentIdx];

arr[parentIdx] = arr[maxChildId];

arr[maxChildId] = temp;

}

}

System.out.println(“Max_Heapify: ” + Arrays.toString(arr));

注: x>>1 是位运算中的右移运算, 表示右移一位, 等同于x除以2再取整, 即 x>>1 == Math.floor(x/2) .

以上,

①. 建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);

②. 调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn);

③. 堆排序的过程由n次第②步完成, 时间复杂度为O(nlgn).

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)

Tips: 由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列. 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序.

五、冒泡排序（Bubble Sort）

我想对于它每个学过C语言的都会了解，这可能是很多人接触的第一个排序算法。

1、基本思想

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的 数列 ，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2、算法描述

冒泡排序算法的运作如下：

①. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

②. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

③. 针对所有的元素重复以上的步骤，除了最后一个。

④. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。

3、代码实现

冒泡排序需要两个嵌套的循环. 其中, 外层循环 移动游标; 内层循环 遍历游标及之后(或之前)的元素, 通过两两交换的方式, 每次只确保该内循环结束位置排序正确, 然后内层循环周期结束, 交由外层循环往后(或前)移动游标, 随即开始下一轮内层循环, 以此类推, 直至循环结束.

以下是冒泡排序算法复杂度:

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n²)	O(n)	O(n²)	O(1)

冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).

Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

六、快速排序（Quick Sort）

快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。

1、基本思想

快速排序的基本思想： 挖坑填数+分治法 。

首先选一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

2、算法描述

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

①. 从数列中挑出一个元素，称为”基准”（pivot）。

②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

3、代码实现

用伪代码描述如下：

①. i = L; j = R; 将基准数挖出形成第一个坑 a[i] 。

②． j– ，由后向前找比它小的数，找到后挖出此数填前一个坑 a[i] 中。

③． i++ ，由前向后找比它大的数，找到后也挖出此数填到前一个坑 a[j] 中。

④．再重复执行②，③二步，直到 i==j ，将基准数填入 a[i] 中

/**

* 快速排序（递归）

*

* ①. 从数列中挑出一个元素，称为”基准”（pivot）。

* ②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

* ③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

* @param arr 待排序数组

* @param low 左边界

* @param high 右边界

*/

public static void quickSort(int[] arr, int low, int high){

if(arr.length <= 0) return;

if(low >= high) return;

int left = low;

int right = high;

int temp = arr[left]; //挖坑1：保存基准的值

while (left < right){

while(left < right && arr[right] >= temp){ //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中

right–;

}

arr[left] = arr[right];

while(left < right && arr[left] <= temp){ //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中

left++;

}

arr[right] = arr[left];

}

arr[left] = temp; //基准值填补到坑3中，准备分治递归快排

System.out.println(“Sorting: ” + Arrays.toString(arr));

quickSort(arr, low, left-1);

quickSort(arr, left+1, high);

}

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

以下是快速排序算法复杂度:

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(nlog₂n)	O(nlog₂n)	O(n²)	O(1)（原地分区递归版）

快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.

Tips: 同选择排序相似, 快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定.

七、归并排序（Merging Sort）

归并排序是建立在归并操作上的一种有效的排序算法，1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

1、基本思想

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

2、算法描述

归并排序可通过两种方式实现：

• 自上而下的递归

• 自下而上的迭代

一、递归法 （假设序列共有n个元素）：

①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；

②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；

③. 重复步骤②，直到所有元素排序完毕。

二、迭代法

①. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

②. 设定两个指针，最初位置分别为两个已经排序序列的起始位置

③. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

④. 重复步骤③直到某一指针到达序列尾

⑤. 将另一序列剩下的所有元素直接复制到合并序列尾

3、代码实现

归并排序其实要做两件事：

• 分解：将序列每次折半拆分

• 合并：将划分后的序列段两两排序合并

因此，归并排序实际上就是两个操作，拆分+合并

如何合并？

L[first…mid]为第一段，L[mid+1…last]为第二段，并且两端已经有序，现在我们要将两端合成达到L[first…last]并且也有序。

首先依次从第一段与第二段中取出元素比较，将较小的元素赋值给temp[]

重复执行上一步，当某一段赋值结束，则将另一段剩下的元素赋值给temp[]

此时将temp[]中的元素复制给L[]，则得到的L[first…last]有序

如何分解？

在这里，我们采用递归的方法，首先将待排序列分成A,B两组；然后重复对A、B序列

分组；直到分组后组内只有一个元素，此时我们认为组内所有元素有序，则分组结束。

这里我写了递归算法如下：

由上, 长度为n的数组, 最终会调用mergeSort函数2n-1次。 通过自上而下的递归实现的归并排序, 将存在堆栈溢出的风险。

以下是归并排序算法复杂度:

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(n)

从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn，, 又每步都是一个普通的合并子数组的过程， 时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(n log n）
的时间复杂度。代价是需要额外的内存空间。

八、基数排序（Radix Sort）

它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序按照优先从高位或低位来排序有两种实现方案：

• MSD（Most significant digital） 从最左侧高位开始进行排序 。先按k1排序分组, 同一组中记录, 关键码k1相等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来, 便得到一个有序序列。MSD方式适用于位数多的序列。

• LSD （Least significant digital）从最右侧低位开始进行排序 。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。

2、算法描述

我们以LSD为例，从最低位开始，具体算法描述如下：

①. 取得数组中的最大数，并取得位数；

②. arr为原始数组，从最低位开始取每个位组成radix数组；

③. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

3、代码实现

基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。

• 分配 ：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中

• 收集 ：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[]。对新形成的序列L[]重复执行分配和收集元素中的十位、百位…直到分配完该序列中的最高位，则排序结束

以下是基数排序算法复杂度:

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n * k)	O(n * k)	O(n * k)	O(k+N)

基数排序更适合用于对时间, 字符串等这些 整体权值未知的数据 进行排序。

Tips: 基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

1. 基数排序：根据键值的每位数字来分配桶

2. 计数排序：每个桶只存储单一键值

3. 桶排序：每个桶存储一定范围的数值

总结

---

各种排序性能对比如下，有些排序未详细介绍，暂且放到这里:

排序类型	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
直接插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
折半插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
希尔排序	O(n^1.3)	O(nlogn)	O(n²)	O(1)	不稳定
归并排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(n)	稳定
快速排序	O(nlog₂n)	O(nlog₂n)	O(n²)	O(nlog₂n)	不稳定
堆排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定
桶排序	O(n+k)	O(n+k)	O(n²)	O(n+k)	(不)稳定
基数排序	O(d(n+k))	O(d(n+k))	O(d(n+kd))	O(n+kd)	稳定

从时间复杂度来说：

(1). 平方阶O(n²)排序： 各类简单排序：直接插入、直接选择和冒泡排序 ；

(2). 线性对数阶O(nlog₂n)排序： 快速排序、堆排序和归并排序 ；

(3). O(n1+§))排序，§是介于0和1之间的常数： 希尔排序

(4). 线性阶O(n)排序： 基数排序，此外还有桶、箱排序 。

说明

• 当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

• 而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；

• 原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大