简述
将无序的数组排序是面试中最常见的工具性算法。
因为单纯的数组排序论难度可能并不配在面试中单独成为一道算法题,所以大多时候排序算法的使用是为了辅佐其他的算法,譬如二分搜索和贪心。 但也有面试官热衷于让面试者现场手搓Quick Sort算法,这种情况下如果问到了却写不出来,那基本上面试也就可以结束了。
这篇笔记简单记录一下10种经典排序算法,和2种不是特别常见,但是很实用的排序算法。
稳定性
很多资料和文档在讲排序时都会提到稳定性的概念,稳定性是什么？有什么用？
稳定性
稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
譬如,数组[3,7,3',2]排序的过程中,如果在排序后,3和3'的顺序发生了改变,那么这个排序就是不稳定的。
稳定性的意义
- 能够节约时间,稳定性算法会减少一次交换时间
- 从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用
稳定的排序算法
- 基数排序、计数排序、插入排序、冒泡排序、归并排序
不稳定的排序算法
- 选择排序、堆排序、快速排序、希尔排序
站在初学者的角度来说,排序算法稳不稳定确实难以引起重视,这是完全可以理解的(因为我曾经也这么认为),因为初学者可能更关注一个排序算法的 过程,而在刷了大量Leetcode但没怎么接触实际应用的情况下,往往会错误地认为时间复杂度和空间复杂度是评估排序算法性能的唯二指标。
但其实,在某些应用场景中,稳定性是非常重要的,例如当目标数组在排序前的原始顺序已经具有意义的情况下,那么不稳定的算法可能会破坏这个顺序。
E.g.
"一个班的学生已经按照学号大小排好序了,现在需要按照年龄从小到大再排个序,如果年龄相同,则必须按照学号从小到大的顺序排列。"
在这种情况下,如果使用不稳定的排序算法对年龄进行排序,排序完了后年龄相同的一组学生学号就乱了,得重复执行一遍学号的排序。 但如果排序算法是稳定的,按照年龄排一遍任务就已经完成了。"
算法一: 选择排序
选择排序是最简单直观的排序算法,它的工作原理是每次找出第i小的元素,然后将这个元素和第i位的元素交换。 只要能确保i从0到n单调递增,则能确保完成排序。
稳定性
由于选择排序中采用了交换两个元素的操作(swap),因此选择排序是一种不稳定的排序算法
时间复杂度
O(n^2)
代码实例(Python3)
def bubble_sort(a, n):
flag = True
while flag:
flag = False
for i in range(1, n):
if a[i] > a[i + 1]:
flag = True
a[i], a[i + 1] = a[i + 1], a[i]
算法二: 冒泡排序
冒泡排序是一种最简单的排序算法之一。之所以叫冒泡排序,是因为算法的排序逻辑就是让较小/大的元素如同气泡一般,从水中慢慢上浮到数列的顶端。
执行流程
不断检查相邻的两个元素,如果前面的元素与后面的元素违背了排序原则,就将两个元素交换。
停止条件: 当某一轮遍历中,没有相邻的元素需要交换时,排序就完成了。
排序逻辑: 第i轮扫描要把第i大/小的元素放到正确的位置
稳定性
冒泡排序是一种稳定的排序算法。
时间复杂度
若数组已经有序,则冒泡排序相当于只是遍历了一遍数组,没有执行任何交换,所以复杂度为: O(n)
最坏的情况下复杂度为: O(n^2)
代码实例(Python3)
def bubble_sort(a, n):
flag = True
while flag:
flag = False
for i in range(1, n):
if a[i] > a[i + 1]:
flag = True
a[i], a[i + 1] = a[i + 1], a[i]
冒泡排序 VS 选择排序
首先,从排序逻辑的角度出发,冒泡排序与选择排序是相同的逻辑,但是执行顺序是相反的(选择排序左侧数组先有序,冒泡排序右侧数组先有序)。
两者的主要区别在于它们对元素比较和交换的机制上,这形成了经典的稳定性和交换次数的tradeoff。
- 冒泡排序依赖相邻比较和交换,保证了稳定性,但可能需要更多轮次的交换。
- 选择排序则通过遍历寻找未排序部分的极值后进行置换,可以减少交换次数,但牺牲了稳定性。
算法三: 插入排序
插入排序同样是一种非常直观简单的排序算法,对于平常热衷于打牌的人来说(比如我),插入排序是最简单的算法, 因为我们拿到一副牌的时候理牌过程其实就是在进行插入排序: 从桌面抓一张牌,按牌面大小插到手牌后,再抓下一张牌。。
抽象一点来讲,插入排序的工作原理其实可以总结为: 将待排列元素划分为「已排序」和「未排序」两部分,每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
稳定性
插入排序是一种稳定的排序算法。
时间复杂度
若数组已经有序,或者接近有序,则效率很高。因为插入排序相当于只是遍历了一遍原数组,并永远在新数组末尾执行插入操作,不需要重排,所以复杂度为: O(n)
最坏的情况下复杂度为: O(n^2)
代码实例(Python3)
def insertion_sort(arr, n):
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key
进阶:二分插入排序法
也被称为折半插入排序。旨在通过二分算法优化性能,在排序元素数量较多时优化的效果比较明显。
不过因为二分插入排序与直接插入排序的基本思想是一致的,折半插入排序仅对插入排序时间复杂度中的常数进行了优化,所以 优化后的时间复杂度仍然不变。
代码实例(Python3)
def insertion_sort(arr, n):
if n < 2: return
for i in range(1, n):
key = arr[i]
index = bisect.bisect_right(arr[:i], key)
arr[indx+1:i+1] = arr[index:i]
arr[index] = key
算法四: 计数排序
计数排序是一种线性时间的排序算法。 线性的时间复杂度是通过牺牲空间换的。计数排序的过程中会用到一个额外的数组,姑且称之为C,原始的数组称之为A。在遍历A的过程中, 直接将A[i]的值当作下标去C中找到对应的位置,随后加一。
通过这个方式,只需要依靠依照下标遍历一遍C数组,所有的值就已经自然排序了。最后只需要记得根据计数确保重复的值不遗漏就行。
稳定性
计数排序是一种稳定的排序算法。
时间复杂度
计数排序的时间复杂度是线性的。
最坏的情况下复杂度为: O(n + w), w是辅助数组的大小
代码实例(Python3)
min_value, max_value = 0, 100
cnt = [0] * max_value
def counting_sort(arr, n):
for i in range(n):
cnt[arr[i]] += 1
sorted_index = 0
for i in range(max_value):
while cnt[i] > 0:
arr[sorted_index] = i
cnt[i] -= 1
sorted_index += 1
算法五: 基数排序
上个模块讲到的计数排序有一个致命的缺陷,就是辅助数组的空间完全受限于最大最小值。一个极端点的例子,如果对数组[100000,1]进行计数排序, 需要至少创建一个长度为100001的辅助数组,太浪费了。而基数排序一定程度上解决了这个问题。
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。 通过这种方式可以控制辅助数组的大小,这种大小可控的辅助数组也被称为"桶", 无论是基数排序、计数排序、还是之后要讲的桶排序,都利用了"桶"的概念。
由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数,所以基数排序也不是只能使用于整数。
E.g. 对一个最大值为50的数组进行基数排序。
第一轮先建立一个值域为[0, 9]的"桶",对个位数关键字进行排序。
第二轮还是建立一个值域为[0, 9]的"桶",对十位数关键字进行排序,并最终完成整体的排序。
基数排序的分类
- 如果是从第 1 关键字到第 k 关键字顺序进行比较,则该基数排序称为 MSD（Most Significant Digit first）基数排序
- 如果是从第 k 关键字到第 1 关键字顺序进行比较,则该基数排序称为 LSD（Least Significant Digit first）基数排序。
稳定性
单独看任何一层关键字的排序,和计数排序一样,都是稳定的排序。
但是第二层关键字的排序不能保证第一层排序后的稳定性还会维持。
反过来也可以这么说:
如果对内层关键字的排序是稳定的,则 MSD 基数排序和 LSD 基数排序都是稳定的排序算法。
时间复杂度
因为关键字值域难以界定,所以最坏情况的探讨优点太广泛,但基本可以理解为O(kn + kw), 其中k是关键字的位数, w是关键字的值域(我们假设每一位的关键字都有相同的值域)。
通常而言,基数排序比基于比较的排序算法（比如快速排序）要快。
代码实例(Python3)
def radix_sort(arr, max_digit):
mod = 10
dev = 1
for i in range(max_digit):
counter = [[] for _ in range(10)]
for num in arr:
bucket = (num % mod) // dev
counter[bucket].append(num)
pos = 0
for bucket in counter:
for num in bucket:
arr[pos] = num
pos += 1
dev *= 10
mod *= 10
return arr
算法六: 桶排序
在基数排序中提到了,桶排序都用到了"桶"的概念,基本的排序思路是一致的,而桶排序比较适用于待排序数据值域较大但分布比较均匀的情况。
执行流程
桶排序按下列步骤进行:
- 设置一个定量的数组当作空桶
- 遍历序列,并将元素一个个放到对应的桶中
- 对每个不是空的桶进行排序
- 从不是空的桶里把元素再放回原来的序列中
稳定性
和基数排序类似,如果能够保证内层的排序是稳定的,那么桶排序也是桶排序。
当然了,这也基于一定前提,因为桶排序不同于基数排序,每个元素插入到对应的桶中时也有可能会改变相同元素间的顺序。 一般来说,每块元素不多的话,可以使用插入排序,那么此时的桶排序就是一种稳定的排序算法。
时间复杂度
整体来说时间复杂度应该是: O(n + n^2/k + k) (将值域平均分成 n 块 + 排序 + 重新合并元素)
- 当n远大于k时,趋近于O(n^2)。
- 当k远大于n时 (几率很小), 趋近于O(k)
- 当n约等于k时, 时间复杂度趋近于线性 O(n)
- 桶排序的最坏时间复杂度为 O(n^2)。
代码实例(Python3)
N = 100010
w = n = 0
a = [0] * N
bucket = [[] for i in range(N)]
def insertion_sort(A):
for i in range(1, len(A)):
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j -= 1
A[j + 1] = key
def bucket_sort():
bucket_size = int(w / n + 1)
for i in range(0, n):
bucket[i].clear()
for i in range(1, n + 1):
bucket[int(a[i] / bucket_size)].append(a[i])
p = 0
for i in range(0, n):
insertion_sort(bucket[i])
for j in range(0, len(bucket[i])):
a[p] = bucket[i][j]
p += 1
基数排序 vs 计数排序 vs 桶排序
- 基数排序: 根据键值的每位数字来分配桶
- 计数排序: 每个桶只存储单一键值
- 桶排序: 每个桶存储一定范围的数值
算法七: 归并排序
归并排序是劝退很多算法初学者的排序算法,因为它是基于分治思想将数组分段排序后合并, 所以想要掌握这个算法的理解门槛其实是略高的。
执行流程
分治法实现归并排序,可以在递归过程中遵循以下操作:
- 当数组长度为 1 时,该数组就已经是有序的,不用再分解。
- 当数组长度大于 1 时,该数组很可能不是有序的。此时将该数组分为两段,再分别检查两个数组是否有序（用第 1 条）。
- 如果有序,则将它们合并为一个有序数组
- 否则,不有序的数组重复第 2 条,再合并
分割
为保证排序的复杂度,通常将数组分为尽量等长的两段: mid = floor((l+r) / 2)
合并
从实现的角度出发,归并排序最核心的部分是合并(merge)过程
要将两个有序的数组 a[i] 和 b[j] 合并为一个有序数组 c[k]。
这其实完全可以通过双指针的方法轻松解决: 从左往右枚举 a[i] 和 b[j],找出最小的值并放入数组 c[k]；重复上述过程直到 a[i] 和 b[j] 有一个为空时,将另一个数组剩下的元素放入 c[k]。
稳定性
只要合并的时候能确保用的是<=判断,就可以避免数字重复时,右侧数字先于左侧数字被插入最终数组。 那么此时的归并排序就是稳定的。
时间复杂度
平均时间复杂度是: O(nlog(n))
代码实例(Python3)
def merge(a, b):
i, j = 0, 0
c = []
while i < len(a) and j < len(b):
if b[j] < a[i]:
c.append(b[j])
j += 1
else:
c.append(a[i])
i += 1
c.extend(a[i:])
c.extend(b[j:])
return c
def merge_sort(a, ll, rr):
if rr - ll <= 1:
return
mid = (rr + ll) // 2
merge_sort(a, ll, mid)
merge_sort(a, mid, rr)
a[ll:rr] = merge(a[ll:mid], a[mid:rr])
算法八: 快速排序
快速排序,也被称为"分区交换排序",是目前应用最广泛的排序算法。更是面试中最有概率考到的排序算法。
执行流程
和归并排序相似,快速排序的工作原理也是通过 分治 的方式来将一个数组排序。
但是和归并排序不同的是: 第一步并不是直接分成前后两个序列,而是在分的过程中要保证相对大小关系。
具体来说,第一步要是要把数列分成两个部分,然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度, 一般是随机选择一个数 m 来当做两个子数列的分界。(因此数组中的元素可以快速归类: 大于m 或 小于m)
之后,维护一前一后两个指针 p 和 q,依次考虑当前的数是否放在了应该放的位置(前还是后)。如果当前的数没放对, 比如说如果后面的指针 q 遇到了一个比 m 小的数,那么可以交换 p 和 q 位置上的数,再把 p 向后移一位。 当前的数的位置全放对后,再移动指针继续处理,直到两个指针相遇。
其实,快速排序没有指定应如何具体实现第一步,不论是选择 m 的过程还是划分的过程,都有不止一种实现方法。
快速排序分为三个过程:
- 将数列划分为两部分（要求保证相对大小关系）
- 递归到两个子序列中分别进行快速排序
- 不用合并,因为此时数列已经完全有序
稳定性
快速排序是一种不稳定的排序算法。
时间复杂度
- 最优时间复杂度是: O(nlog(n)) (每一次选择的分界值都是序列的中位数)
- 平均时间复杂度是: O(nlog(n))
- 最坏时间复杂度为: O(n^2) (每一次选择的分界值都是序列的最值)
代码实例(Python3)
def quick_sort(alist, first, last):
if first >= last:
return
mid_value = alist[first]
low = first
high = last
while low < high:
while low < high and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]
while low < high and alist[low] < mid_value:
low += 1
alist[high] = alist[low]
alist[low] = mid_value
quick_sort(alist, first, low - 1)
quick_sort(alist, low + 1, last)
算法九: 堆排序
堆排序是利用 二叉堆 这种特定数据结构所设计的一种排序算法,最开始我感觉其实是有点跑题的,毕竟这篇笔记虽然是我用来梳理排序算法的, 但名义上还是属于《数组篇》。但是转念一想,堆本身就可以在数组上建立,而且尽管他的排序本质是建立在堆上的选择排序,但是不妨碍它可以排序数组, 无非就是多了一个堆的创建和排序数组的重构。
执行流程
- 首先根据排序需求建立大顶堆或者小顶堆,然后将堆顶的元素取出,作为最大值,与数组尾部的元素交换,并维持残余堆的性质。
- 之后将堆顶的元素取出,作为次大值,与数组倒数第二位元素交换,并维持残余堆的性质。
- 以此类推,在第n-1次操作后,当堆空了,数组自然也就完成了排序。
关于"堆"
在排序算法的章节我不准备具体展开 二叉堆 的内容,因为之后准备系统性地整理堆和栈这些常用数据结构。不过可以基本提一嘴为什么二叉堆不需要建立特定的树形数据结构,而是可以直接在数组上创建的原因。
通过观察树形态的二叉堆,人们可以发现二叉堆中的每个节点,从根节点自上而下,从左至右计数,在该节点之前的节点总数正好是他父节点的计数的两倍,左子节点要算上自己本身(+1),右子节点要加上自身和左子节点(+2)。
这个关系可以直接应用到数组中的下标倍数关系。
iParent(i) = (i - 1) / 2; iLeftChild(i) = 2 * i + 1; iRightChild(i) = 2 * i + 2;
稳定性
同选择排序一样,由于其中交换位置的操作,所以是不稳定的排序算法。
时间复杂度
看到二叉堆,时间复杂度则直接 O(nlogn)
代码实例(Python3)
def sift_down(arr, start, end):
parent = int(start)
child = int(parent * 2 + 1)
while child <= end:
if child + 1 <= end and arr[child] < arr[child + 1]:
child += 1
if arr[parent] >= arr[child]:
return
else:
arr[parent], arr[child] = arr[child], arr[parent]
parent = child
child = int(parent * 2 + 1)
def heap_sort(arr, len):
i = (len - 1 - 1) / 2
while i >= 0:
sift_down(arr, i, len - 1)
i -= 1
i = len - 1
while i > 0:
arr[0], arr[i] = arr[i], arr[0]
sift_down(arr, 0, i - 1)
i -= 1
算法十: 希尔排序
希尔排序,也被称为缩小增量排序法,是 插入排序 的一种改进版本。也是上个世纪中期冲破O(n^2)的第一批算法之一
它的发明者Donald Shell基于插入排序的以下两点性质而提出改进方法
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
执行流程
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序；随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止
排序对不相邻的记录进行比较和移动:
- 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）
- 对这些子序列进行插入排序
- 减小每个子序列中元素之间的间距,重复上述过程直至间距减少为 1
流程图解
稳定性
希尔排序是不稳定的排序算法。
时间复杂度
希尔排序的最优时间复杂度为 O(n)。
但是希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取有关:
- 当间距序列选的足够不合适时, 会使得排序算法的复杂度降为O(n^2)
希尔排序本身并不复杂,但是时间复杂度是有一套完善且复杂的证明方式的,这也是Donald Shell在1959年改进该算法后的主要工作。 证明时间复杂度的具体过程以及使用的引理和定理就不在这里具体展开了。感兴趣的可以在此处查看。
代码实例(Python3)
import math
def shellSort(arr):
gap=1
while(gap < len(arr)/3):
gap = gap*3+1
while gap > 0:
for i in range(gap,len(arr)):
temp = arr[i]
j = i-gap
while j >=0 and arr[j] > temp:
arr[j+gap]=arr[j]
j-=gap
arr[j+gap] = temp
gap = math.floor(gap/3)
return arr
算法十一: 锦标赛排序
锦标赛排序的名字来源于单败淘汰制的竞赛形式。在这种赛制中有许多选手参与比赛,他们两两比较,胜者进入下一轮比赛,这种淘汰方式可以画成完全二叉树的形式,只需要看root就能够知道谁才是number 1。
乍一看非常类似堆排序,但是其实差别很大,因为堆排序推出堆顶元素后,新的堆顶就是第二大/小的元素。但是锦标赛的排序方式,在最后一轮比赛中被第一名淘汰的选手不一定是第二好的,因为他可能不如先前被淘汰的选手(e.g. 第二名在第一轮就被第一名淘汰了)。
因此,锦标赛排序,又被称为树形选择排序,其实是在选择排序的基础上使用堆排序的思想(优先队列)查找下一个该选择的元素。是 选择排序 的优化版本,堆排序 的一种变体(均采用完全二叉树)。
执行流程
以[7,2,3,4,6,10,8,5]为例,执行最小锦标赛排序,那锦标赛排序树应该如下图所示:
很显然,2就是最小的元素,可以先拿出来。完成一次「锦标赛」后需要将被选出的元素去除。直接将其设置为+INF (最大排序就用-INF),然后再次举行「锦标赛」选出次小的元素。
之后一直重复这个操作,直至所有元素有序。
稳定性
锦标赛排序是不稳定的排序算法。
时间复杂度
优时间复杂度、平均时间复杂度和最坏时间复杂度均为O(nlogn)
初始化锦标赛树只需要O(n)的时间,每一轮「锦标赛」用O(logn)的时间,需要重复n次。
代码实力就略过了,思路不复杂,但是需要实现「初始化」,「竞赛」,「重复比赛」的功能。
算法十二: Tim排序
Tim排序是归并排序和插入排序的结合。是我目前接触到最牛掰的排序算法。 由 Tim Peters 于 2002 年用 Python 实现,而且Tim排序是 Python 的标准排序算法, 且被 Java SE7 用于对非原始类型的数组排序。
执行流程
归并排序是先将数组划分为两部分,然后递归地对两个子数组进行归并排序,最后合并两个子数组。这样一来,归并排序合并操作的最小单位就是单个元素。
但数组中可能原本就存在连续且有序的子数组,归并排序无法利用这个特性。
RUN单位
Tim排序为了利用数组中本身就存在的连续且有序的子数组,以 RUN 作为合并操作的最小单位。其中,RUN 是一个满足以下性质的子数组
- 一个 RUN 要么是非降序的,要么是严格升序的。
- 一个 RUN 存在一个长度的下限
Tim排序的过程就是一个类似归并排序的过程,将数组划分为多个 RUN,然后以某种规则不断地合并两个 RUN,直到数组有序
稳定性
Tim排序是稳定的排序算法。
时间复杂度
- 最好情况下的时间复杂度为
O(n) - 最差情况下的时间复杂度为 O(nlogn)
代码实例(Java)
以下是Java SE7中的实现。
class TimSort implements SortAlgorithm {
private static final int SUB_ARRAY_SIZE = 32;
private Comparable[] aux;
@Override
public <T extends Comparable<T>> T[] sort(T[] a) {
int n = a.length;
InsertionSort insertionSort = new InsertionSort();
for (int i = 0; i < n; i += SUB_ARRAY_SIZE) {
insertionSort.sort(a, i, Math.min(i + SUB_ARRAY_SIZE, n));
}
aux = new Comparable[n];
for (int sz = SUB_ARRAY_SIZE; sz < n; sz = sz + sz) {
for (int lo = 0; lo < n - sz; lo += sz + sz) {
merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, n - 1));
}
}
return a;
}
private <T extends Comparable<T>> void merge(T[] a, int lo, int mid, int hi) {
int i = lo;
int j = mid + 1;
System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
for (int k = lo; k <= hi; k++) {
if (j > hi) {
a[k] = (T) aux[i++];
} else if (i > mid) {
a[k] = (T) aux[j++];
} else if (less(aux[j], aux[i])) {
a[k] = (T) aux[j++];
} else {
a[k] = (T) aux[i++];
}
}
}
}