十大排序算法比较与总结
下列表格主要来源于学习数据结构时的总结,在《Algorithm to Algorithm》一书中涉及的算法将以该书内容为准,因为Markdown并不能完美支持
在此默认排序方式为升序,即从小到大。
排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
分类 | 算法名称 | 平均 | 最好 | 最坏 | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|---|
插入 | 直接插入 | |||||
插入 | 折半插入 | |||||
插入 | 希尔排序 | |||||
交换 | 冒泡排序 | |||||
交换 | 快速排序 | |||||
选择 | 简单选择排序 | |||||
选择 | 堆排序 | |||||
归并 | 二路归并 | |||||
线性 | 基数排序 | |||||
线性 | 计数排序 | |||||
线性 | 桶排序 |
- 平均而言,快速排序最佳,最坏情况下不如堆排序与归并排序
- 直接插入排序,折半插入排序,简单选择排序,冒泡排序等时间复杂度为
的排序不适用与 较大的情况 - 一趟排序至少能保证一个关键字到达最终位置的排序:交换类(冒泡排序,快速排序),选择类排序(简单选择排序,堆排序)
- 关键字比较次数和原始序列无关的排序:简单选择排序,折半插入排序,归并排序,基数排序
- 排序趟数和原始序列有关的排序:交换类排序(冒泡排序,快速排序)
- 排序趟数与原始序列无关的排序:直接插入排序,折半插入排序,希尔排序,堆排序,二路归并排序,简单选择排序,基数排序
- 借助于比较进行排序的算法,最坏时至少为
- 直接插入和折半插入的区别仅在于查找插入位置的方式不同
- 元素的移动次数与原始序列无关的排序:基数排序
- 不稳定排序:快速排序,希尔排序,简单选择排序,堆排序
- 时间复杂度为
的排序:快速排序,希尔排序,二路归并排序,堆排序 - 计数排序不是比较排序,因此不受
的限制
TODO
- 时间复杂度的计算方法
- 未完成的算法
- 相应算法的动图
1. 插入类排序
1.1 直接插入
《Introduction to Algorithm》这本经典著作中的第一个算法例子就是
- Initialization: It is true prior to the first iteration of the loop.
- 初始化:在循环迭代中第一步是正确的
- Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
- 保持:如果循环中前一次的迭代结果时正确的,那么在下一次迭代过程中也应该是正确的。
- Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
- 终止:当循环结束时,不变量可以给我们一个能证明算法是正确的有用的特性。
就像打扑克牌补牌时的方式一样,第一张牌肯定是有序的,从二张牌开始,每次将补到的牌按大小顺序插入手牌中,这样每次能保证每次插入后的手牌都是有序的,但是很可能会存在的问题是补到的牌不大不小,正处中间,这就会导致比这张牌大的手牌将会逐个后移。
- 基本思想:将待插入的元素逐个插入到已经有序的数组中。
- 循环不变量:在插入之前已经有序的数组,在插入后数组仍然是有序的。
1 | /** |
现在,利用 循环不变量 来证明这个算法是正确的。
- 初始化:在第一次执行的时候,仅有元素
array[0]
,很显然一个数字无论从哪种排序方式看都是有序的。 - 保持:接下来需要证明在每一次循环中都能保持循环不变量成立。从非形式化的方式上看,在
for
循环中,可能要将array[i-1], array[i-2]...
的元素向后移动一个位置,直到找到array[i]
要插入的位置为止。 - 终止:当外层
for
循环结束的时候,在外层for
循环将i
替换为n
的时候,就有子数组array[0..n-1]
已经排好序了,而子数组其实正是整个数组,说明整个数组也已经排好序了,说明算法是正确的。
渐进记号
在《Introduction to Algorithm》一书中,出现最多的其实并不是大
图像比具体的数学定义更直观一些。
- 在插入排序中最好的情况是指该数组已经有序,此时代码中的
while
循环条件之中不满足,则不用交换元素,只需要遍历一遍数组,即达到下确界 - 最坏情况则是该数组已有序但是与要求的排序规则相比则是逆序,此时
while
循环每次满足, 而移动元素的次数为 次,即达到上确界 . - 所以通常情况下,该问题的规模函数介于二者之间,为
- 更加细致入微的分析还请参考《Introduction to Algorithm》一书英文版26页,下面是一张书中的截图
这里可能有人要问,为什么介于二者之间就是
在证明之前首先了解《Introduction to Algorithm》一书中三种求解问题规模的方法:
对于问题形如
一般有三种方法,分别为代入法,递归树法,主定理法
substitution method:we guess a bound and then use mathematical in- duction to prove our guess correct.
recursion-tree method:converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion. We use techniques for bounding summations to solve the recurrence.
master method:rovides bounds for recurrences of the form
为已知函数。
1.2 折半插入
折半插入排序(Binary Insertion Sort)是对插入排序算法的一种改进,由于排序算法过程中,就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列,这样我们不用按顺序依次寻找插入点,可以采用折半查找的方法来加快寻找插入点的速度。
1 | public static int[] binaryInsertionSort(int[] array) { |
- 分析:与直接插入相比,折半插入仅仅是对查找插入位置的方式进行了优化,减少了查找插入位置的时间,但是元素的移动次数并没有减少,所以总的来说时空复杂度与插入排序相同。
- 循环不变量:与插入排序一样,循环不变量为在插入数字之前已有序的数组。
1.3 希尔排序
希尔排序(Shellsort) ,也称递减增量排序算法,是插入排序的一种更高效的改进版本,但是希尔排序在高效的同时也破坏了排序元素的稳定性,是非稳定排序算法。
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为
一个更好理解的希尔排序实现:将数组列在一个表中并对列排序(用插入排序)。重复这过程,不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身仅仅对原数组进行排序(通过增加索引的步长,例如是用i += stepSize
, 而不是 i++
)。
例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
,如果我们以步长为5开始进行排序(其实就是按索引下标分组,如下标为0,5,10… 一组,而下标1,6,11…一组,下标 2,7,12… 一组),我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:
1 | // 步长为5得到 |
已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…),该序列的项来自
另一个在大数组中表现优异的步长序列是(斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列):(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)
在此选择 Shell
本人推荐使用的步长为 n/2
, 其他的步长实现待补充。
1 | public static int[] shellSort(int[] array) { |
- 分析:显然可以看到外层循环次数为
,而内层循环为 ,从而该排序方法的时间复杂度为 . - 循环不变量:元素在每一个分组之内都是有序的
2. 交换类排序
2.1 冒泡排序
冒泡排序(英语:Bubble Sort)又称为泡式排序,是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下:
- 比较相邻的元素。如果第一个比第二个大,就交换它们的位置。
- 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数,即 冒泡排序每轮结束后至少能保证一个元素处于最终位置上。
- 针对除最后一个元素外的所有元素重复以上的步骤。
1 | public int[] bubbleSort(int[] array) { |
冒泡排序是与插入排序拥有相等的运行时间,但是两种算法在需要的交换次数却很大地不同。在最坏的情况(逆序),冒泡排序需要
冒泡排序如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,也可以把最优情况下的复杂度降低到
2.2 快速排序
2.2.1 快速排序基础
上图是《Introduction to Algorithm》一书第七章对于快速排序的介绍,大意是:快速排序在问题规模为
像归并排序一样,快速排序也是基于分治(Divide And Conquer)思想的。下面是对一个典型子数组A[p..r]
排序的分治过程的的三个步骤。
- 分解:找到一个枢轴
q
将原数组划分为两个子数组A[p..q-1],A[q+1, r]
,使得前一个子数组中的所有元素都小于等于A[q]
,而后一个数组中的所有元素都大于A[q]
,下标q
也在这个划分过程中参与计算; - 解决:通过递归调用快速排序,对子数组
A[p..q-1]
和A[q+1,r]
排序; - 合并:因为两个子数组是就地排序的,将它们的合并不需要操作,整个数组已排好序。
PARTITION
总是选择数组中最右边的元素作为 枢轴 Pivot,并围绕它来划分子数组,随着该过程的进行,数组被划分为四个区域(可能有空的),在第 for
循环每次迭代的开始,每一个区域都满足特定的性质。这些性质就是我们从插入排序时就开始提到的 Loop Invariant,循环不变量。
在上图中,有
下面来证明循环不变量:
- 初始化:在循环的第一轮迭代开始之前,有
和 ,在 和 之间没有值,在 和 之间也没有值。因此,循环不变量的头两个条件显然满足。第1行中的赋值操作满足第三个条件。 - 保持:需要考虑下图中的两种情况,具体取决于第
行中测试的结果。- 第一种情况显示当
时所做的处理;循环中的唯一操作是 ,在 后,条件 对 成立,且所有其他项保持不变。 - 第二种情况显示当
时所做的处理:将 加 ,交换 和 ,再将 加1。因为进行了交换,现在 ,因而条件 满足。类似的,还有 ,因为根据循环不变量,被交换进 的项目是大于 的。
- 第一种情况显示当
- 终止:当终止时,
,于是数组中的每个元素都在循环不变量所描述的三个集合的某一个之中。也就是已经把数组中的所有元素划分到了三个集合中:一个集合包含了小于等于 的元素,第二个集合中包含了大于 的元素,还有一个只包含了 的集合。 - 此过程的运行时间为
,其中 ,暂不证明。
2.2.2 快速排序性能
快速排序的运行时间与划分是否对称有关,而是否对称又与选择哪一个元素为
- 最坏情况:每次划分的两个区域分别包含
和 个元素,运行时间递归式为:
- 最好情况:每次划分的两个子问题的大小都不可能大于
,其中的一个问题大小为 ,另一个子问题的大小为 ,运行时间递归式为:
1 | // 对自身的两次递归调用 |
最初的快排数组划分方式,由 C.R.Hoare 提出,也是国内本科教学中最常见的划分方法。
1 | /** |
无论选择何种方式实现 partition,一定要确保在 pivot 左边的 <= pivot,pivot 右边的 > pivot。
2.2.3 分析与具体证明
如上图所示,我们假设在每次划分时按
收敛速度更快的是
事实上,即使是按照
3. 选择类排序
3.1 简单选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
- 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。
- 选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对
个元素的表进行排序总共进行至多次 交换。 - 在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。
1 | 初始值: 3 1 5 7 2 4 9 6 |
算法实现:
1 | public int[] selectionSort(int[] arr) { |
最好情况即为数组已有序,最坏情况为逆序。
但是无论最好最坏情况,选择排序的比较次数都是
,仅有交换次数不同,最好情况交换 次,最坏情况交换 次。总的问题规模为
。
3.2 堆排序
上图是《Introduction to Algorithm》一书第六章对于堆排序的介绍,简单的翻译一下就是:像归并排序而不像插入排序,堆排序的运行时间为
3.2.1 堆简介
(二叉)堆 数据结构式一种数组对象,如下图所示,它可以被视为一课 完全二叉树,树中每个节点与数组中存放该节点值的那个元素对应。根据完全二叉树的定义,树种除了最后一层外,其它层一定是满的,树的根为
表示堆的数组 heap-size[A]
是存放在 heap-size[A] <= length[A]
.
在堆排序算法中,我们使用的是 大根堆,小根堆 通常用于构造 优先队列。堆可以被看作是一棵树,因为是完全二叉树,所以其高度为
MAX-HEAPIFY
:运行时间为 ,是保持大根堆性质的关键。BUILD-MAX-HEAP
:以线性时间运行,可以在无序的输入数组基础上构造出大根堆。HEAPSORT
:运行时间为 ,对一个数组原地进行排序。MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, HEAP-MAXIMUM
过程的运行时间为 ,可以让堆结构作为优先队列使用。
3.2.2 保持堆的性质
MAX-HEAPIFY
是对大根堆进行操作的重要子程序。其输入一个数组 MAX-HEAPIFY
被调用时,我们假设以 LEFT(i)
和 RIGHT(i)
为根的两个二叉树都是大根堆,但这时 MAX-HEAPIFY
让
下图描述了 MAX-HEAPIFY
的过程,在算法的每一步里, 从元素 A[i], A[LEFT(i)],A[RIGHT(i)]
中找出最大的,并将其下标存储在 MAX-HEAPIFY
。
3.2.3 建堆
我们可以自底向上地用 MAX-HEAPIFY
来将一个数组
为了证明 BUILD-MAX-HEAP
的正确性,可以使用如下的 循环不变量。
在
3.2.4 堆排序算法
开始时,对排序算法先用 BUILD-MAX-HEAP
来将输入数组 MAX-HEAPIFY(A, 0)
就可以保存这一性质,构造出大根堆,堆排序算法不断重复这个过程,堆的大小由
循环不变量:在每次
1 | public class HeapSort { |
4. 归并排序
有很多算法在结构上是递归的,为了解决一个给定的问题,算法要一次或多次地递归调用其自身来解决相关的子问题,这些算法通常采用 分治策略(Divide And Conquer):将原问题分成
分治策略在每一层上都有三个步骤:
- 分解(Divide):将原问题分解为一系列的子问题;
- 解决(Conquer): 递归地解各子问题,若子问题足够小,则直接求解;
- 合并(Combine): 将子问题的结果合并成原问题的解。
归并排序(Merge Sort) 算法完全按照上述模式,直观操作如下:
- 分解:将
个元素分成各含 个元素的子序列; - 解决:用归并排序对两个子序列递归地排序;
- 合并:合并两个已排序的子序列得到排序的结果。
在对子序列排序时,其长度为
归并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做归并,引入一个辅助过程 MERGE(A, p, q, r)
.
再举扑克牌这个例子,假如我们现在有两堆已好序的扑克牌,它们面朝上放着,最小的牌放在最上面,而我们要做的是把牌从小到大排成一副完整的牌。在刚开始时我们从两堆牌中取出最上面一张牌,然后比较二者大小,然后将其中较小的牌反面盖上,我们称其为第三堆,然后将较大的牌与另一堆最上面的的最小的牌进行比较。然后把二者较小的牌放到第三堆上,重复此过程,直到其中一堆牌全部被放到第三堆上,第一堆或者第二堆剩下的牌直接全部盖到第三堆上去,此时就完成了排序。
伪代码: 这里用
- 初始化:在
for
循环的第一轮迭代开始之前,有k = p
, 因而子数组A[p..k-1]
是空的。这个空的子数组包含了L
和R
中k - p = 0
个最小的元素。此外,又因为i = j + 1
,L[i]
和R[j]
都是各自所在数组中,尚未被副指挥数组A
中的最小元素。 - 保持:为了说明每一轮迭代中都能使循环不变式保持成立,首先架设
,那么 就是尚未被复制回数组A
中的最小元素。由于A[p..k-1]
包含了k - p
个最小的元素,因此在第 行将L[i]
复制回A[k]
中后,子数组A[p..k]
将包含k - p + 1
个最小的元素。增加k, i
的值,会为下一轮迭代重新建立 循环不变量 的值,如果这次有 ,则第 行就会执行相应的操作,以使循环不变量保持成立。 - 终止:在终止时,
k = r + 1
,根据 循环不变量,子数组A[p..k-1]
包含了 和 中k - p = r - p + 1
个最小元素,并且已经是排好序的。数组L、R
合起来包含了 个元素,除了两个最大的元素外,其余的所有元素都已被复制回数组A
中,这两个最大元素都是哨兵。
for
循环所需时间为 for
循环共有
现在,就可以将
1 | /** |
归并排序的最坏情况运行时间表达式为,由 主定理 可以求得
5. 线性时间排序
到目前为止,我们所分析过的排序算法都有一个令人感兴趣的性质:排序结果中,各元素的次序基于输入元素间的比较,我们把这类排序算法称为 比较排序。
5.0 排序算法的下界
比较排序可以被抽象地视为决策树,表示排序算法作用于给定输入所做的所有比较,而控制结构,数据移动等都被忽略了。下图对应于插入排序算法作用于三个元素的输入序列上的决策树
定理 : 任意一个比较排序算法在最坏情况下,都需要做
证明 :对于一棵每个排列都作为一个可达叶结点出现的决策树,考虑一棵高度为
对该式取对数,得到
从中也可以推论出:堆排序和归并排序都是渐进最优的比较排序算法。
5.1 计数排序
计数排序假设
计数排序的 基本思想 就是对每一个输入元素
在下面计数排序的伪代码中,我们假定输入是个数组
- 1-3 行代码:初始化,所花时间
- 4-5 行代码:检查每个输入元素,如果值为
即增加 的值,于是在第5行之后, 就存放了等于元素 的个数,所花时间 - 7-8行代码:通过在数组
中记录计数和,可以确定对每一个 ,有多少输入元素是小于等于 的,所花时间 - 10-12行代码:把每个元素
放在输出数组 中与其对应的最终位置上,所花时间
这样,总的时间就是
1 | public static int[] countingSort(int[] A) { |
5.2 基数排序
基数排序(英语:Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
它是这样实现的:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
假如我们想根据三个关键字年、月、日来对日期进行排序,我们可以先比较年,再比较月,再比较日,当然也可以先比较日,再比较月,再比较年。这也就对应了 LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
基数排序的代码是非常直观的
- 引理1:给定
个 位数,每一个数位有 种可能的值,基数排序算法能以 的时间正确地对这些数进行排序。 - 引理2:给定
个 位数和任何正整数 , 能在 的时间内正确地对这些数进行排序。
1 | // 来源于 百度百科 https://baike.baidu.com/item/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F |
基数排序是否要比基于比较的排序算法(如快速排序)要好呢?如果根据常见的情况有
5.3 桶排序
当 桶排序(bucket sort) 的输入符合均匀分布时,即可以以线性时间运行。与基数排序类似,桶排序也对输入作了某种架设,因而运行的很快。具体来说,计数排序假设输入是由一个小范围内的整数构成,而桶排序择假设输入由一个随机过程产生,该过程将元素均匀地分布在区间
桶排序的思想就是把区间
为了说明这个算法是正确的,我们假设两个元素 for
循环会将它们按适当的顺序排列;如果
除第
为了分析调用插入排序的时间代价,设
对两边的值取期望( 概率论中的期望
下式对
总之最后我们可以得出这样一个结论:即桶排序的期望运行时间为
1 | // 来源于:https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F#Java%E5%AF%A6%E7%8F%BE%E7%AE%97%E6%B3%95 |
REFERENCES
- 《Introduction to Algorithm》3rd edition
- Wikipedia