排序

总述

  • 按照升序重新排列给定列表中的数据项
  • 为了让问题有意义,列表中的数据项应该能够排序(数据之间 有一种全序关系)
  • 键:在对记录排序时,需要选取的、作为排序的依据的一段信息

目的

  • 排序可能是所求解的问题输出要求
  • 排序能够更方便的求解和列表相关的问题
    • 查找问题
  • 在其他领域的重要算法中,排序也被作为辅助步骤

发展

  • 排序领域已经有很多不错的算法,只需要做$nlog_{x}^{n}$次 比较就能完成长度为$n$的任意数组排序,且没有一种基于 值比较(相较于比较键值部分内容而言)的排序算法能 在本质上操作其,

  • 但是还是需要不断探寻新的算法虽然有些算法比其他的要好, 但是没有任何算法在任何情况下是最优的

    • 有些算法比较简单,但速度较慢
    • 有些算法适合随机排列的输入,而有些适合基本有序的列表
    • 有些算法适合驻留在快速存储器中的列表,而有些适合存储 在磁盘上的大型文件排序

评价

  • 稳定性:排序算法保留等值元素在输入中的相对顺序
    • 一般来说,将相隔很远的键交换位置的算法虽然不稳定, 但往往很快
  • 在位性:排序算法不需要额外的存储空间,除极个别存储单元外

线性表排序

选择排序

  • 每轮选择出剩余元素中最小值,放在对于位置上

顺序表算法

1
2
3
4
5
6
7
8
9
10
SelectionSort(A[0..n-1]):
// 选择排序排序数组
// 输入:可排序数组A[0..n-1]
// 输出:升序排序数组A[0..n-1]
for i = 0 to n-1 do
min = i
for j = i to n-1 do
if A[j] < A[min]
min = j
swap A[i] and A[min]
  • 扫描整个列表找到最小元素,然后和首个元素交换,将其放在 最终位置上
  • 从第2个元素开始寻找之后最小元素,和第2个元素交换,将其 放在最终位置上
  • 重复n-1次,列表有序

链表算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
SelectionSort(linked):
// 选择排序排序链表
// 输入:可排序链表linked头
// 输出:排序后链表头
if linked == NULL:
return NULL
linked_head = ListNode()
// 为方便附设头结点
linked_head.next = linked
unsorted_head = linked_head
// 未排序头结点
// 后续过程中是链表中元素

while unsorted_head.next != NULL:
cur_node = unsorted_head
min_node = unsorted_head
// 全是链表中元素
while cur_node.next != NULL:
if cur_node.next.val < min_node.next.val:
min_node = cur_node
cur_node = cur_node.next

// 若`min_node.next`就是`unsorted_start.next`,以下
// 代码中的断开、重组链表操作会出现环
// 完全切开再重组链表,则需要判断`unsorted_start`
// 是否为空
if unsorted_start.next != min_node.next:
_tmp_node = unsorted_head.next
// 记录原`unsorted_head.next`

unsorted_head.next = min_node.next
// `unsorted_head.next`断开、连接`min_node`

min_node.next = min_node.next.next
// `min_node.next`断开、跳过`min_node`重连
// 若`min_node.next`是`unsorted_start.next`
// 会断开`unsorted_start`和`min_node`

unsorted_head.next.next = _tmp_node
// 原`min_node`重连原`unsorted_head.next`

unsorted_start = unsorted_start.next

return linked_head.next

特点

  • 对任何输入,选择排序键值比较都是$\Theta(n^2)$
  • 键交换次数仅为$\Theta(n)$
    • 选择排序此特性优于许多其他排序算法

冒泡排序

  • 比较表中相邻元素,如果逆序就交换位置
  • 重复多次则最大元素被“沉到”列表最后位置
  • 第2轮比较将第2大元素“沉到”其最终位置
  • 重复比较n-1轮,列表有序

顺序表算法

1
2
3
4
5
6
7
8
BubbleSort(A[0..n-1]):
// 冒泡排序排序数组
// 输入:可排序数组A[0..n-1]
// 输出:升序排序数组A[0..n-1]
for i = 0 to n-2 do
for j = 0 to n-2-i do
if A[j+i] < A[j]
swap A[j] and A[j+1]

链表算法

1
2
3
4
BublleSort(head):
// 冒泡排序排序链表
// 输入:可排序链表首个元素
// 输出:排序后列表首个元素

特点

  • 对任何输入,冒泡排序键值比较都是$\Theta(n^2)$
  • 其交换次数取决于特定输入
    • 最坏情况是遇到降序排列数组,此时键交换次数同比较次数
  • 冒泡排序看起来就像是选择排序的一直交换+最大优先版本

改进

  • 如果对列表比较一轮后没有交换任何元素,说明列表有序,可以 结束算法

Insertion Sort

插入排序:利用减一技术对数组$A[0..n-1]$进行排序

算法

  • 假设对较小数组$A[0..i-2]$排序已经解决
  • 从右至左(方便将将元素右移)扫描有序子数组,直到遇到首个 小于等于$A[i-1]$元素,将$A[i-1]$插入其后
1
2
3
4
5
6
7
8
9
10
11
12
InsertionSort(A[0..n-1])
// 用插入排序对给定数组排序
// 输入:n个可排序元素构成数组
// 输出:非降序排序数组
for i = 1 to n-1 do
v = A[i]
j = i - 1
while j >= 0 and A[j] > v do
A[j+1] = A[j]
j = j - 1
A[j+1] = v
// 上一步比较元素已经赋值给其后,所以应该覆盖其值

特点

  • 插入排序是自顶向下基于递归思想,但是自底向上使用迭代实现 算法效率更高

  • 算法时间效率

    • 算法基本操作是键值比较,比较次数依赖于特定输入
    • 最坏情况(递减数组)下:每轮比较次数都到达最大,此时 键值比较次数$\in \Theta(n^2)$
    • 最优情况(递增数组)下:每轮比较次数仅为1,此时键值 比较次数$\in \Theta(n)$
    • 对随机序列:比较次数$\in \Theta(n^2)$
    • 许多应用中都会遇到基本有序的文件,插入排序能保证良好 性能
  • 减常量法

Shell Sort

插入排序的扩展,Shell排序基于h有序

H有序

数组中任意间隔为h的元素都是有序的,对应的数组称为h有序数组

  • h有序数组:就是h个互相独立的有序数组编织在一起数组
  • h有序数组具有分离、局部有序的特点

算法

  • 使用插入排序对h子数组独立排序,每次交换相隔h的元素
  • h逐渐减小到1,shell排序退化(最后一轮)为插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ShellSort(A[0..n-1])
// 用插入排序对给定数组排序
// 输入:n个可排序元素构成数组
// 输出:非降序排序数组
h = 1
while h < n/3
h = h*3 + 1
// 获取初始h值,之后每轮h变为1/3
while h >= 1:
for i = h to n-1:
v = A[i]
j = i - h
while j >= 0 and A[j] > v do
A[j] = A[j-h]
j = j - h
A[j+h] = v
h = h/3

特点

  • Shell排序全衡量子数组规模、有序性,更加高效

  • h递增序列

    • 子数组部分有序程度取决于h递增序列的选择
    • 不同的h递增序列对算法效率有常数倍的变动,但是在实际 应用中效果不明显
  • Shell排序是唯一无法准确描述其对于乱序数组性能特征的排序 方法

  • 减常量法

归并排序

Mergesort

  • 将需要排序的数组A[0..n-1]均分的
  • 对两个子数组递归排序,然后把排序后的子数组合并为有序 数组
1
2
3
4
5
6
7
8
9
10
Mergesort(A[0..n-1]):
// 递归调用MergeSort对数组排序
// 输入:可排序数组A[0..n-1]
// 输出:非降序排列数组A[0..n-1]
if n > 1:
copy A[0..floor(n/2)-1] to B[0..floor(n/2)-1]
copy A[floor(n/2)..n-1] to C[0..ceiling(n/2)-1]
Mergesort(B[0..floor(n/2)-1])
Mergesort(C[0..ceiling(n/2)-11])
Merge(B, C, A)

Merge

  • 初始两只指针指向待合并数组首个元素
  • 比较两个元素大小,将较小元素添加到新数组中,被复制元素 的数组指针右移
  • 重复直到某一数组处理完毕,将未处理完数组复制到新数组尾部
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Merge(B[0..p-1], C[0..q-1], A[0..p+q-1]):
// 将两个有序数组合并为新的有序数组
// 输入:有序数组B[0..p-1]、C[0..q-1]
// 输出:存放有B、C中元素的有序数组A[0..p+q-1]
while i < p and j < q:
if B[i] <= C[j]
A[k] = B[i]
i = i + 1
else:
A[k] = C[j]
j = j + 1
k = k + 1
if i == p:
copy C[j..q-1] to A[k..p+q-1]
else:
copy B[i..p-1] to A[k..p+q-1]

特点

  • 算法时间效率

    • 最坏情况下比较次数$\in \Theta(nlogn)$,为 $nlog_2n-n+1$,十分接近基于比较的排序算法理论上能够 达到的最少次数
  • 相较于快排、堆排序

    • 合并排序比较稳定,缺点在于需要线性额外空间
    • 虽然能做到在位,但是算法过于复杂,只具有理论上意义
  • 算法可以自底向上合并数组的元素对,再合并有序对

    • 这可以避免使用堆栈递归调用时时空开销
  • 可以把数组划分为待排序的多个部分,再对其递归排序,最后 合并在一起

    • 这尤其适合对存在二级存储空间的文件进行排序
    • 也称为Multiway Mergesort
  • 分治算法

快速排序

相较于合并排序按照元素在数组中的位置进行划分,快速排序按照 元素值对其进行划分

Quicksort

  • 对数组中元素重新排列,使得A[s]左边元素均小于A[s],A[s] 右边元素都大于等于A[s]
    • 此时A[s]已经位于它在有序数组中的最终位置
  • 接下来对A[s]左右子数组进行排序
1
2
3
4
5
6
7
8
Quicksort(A[l..]r)
// 对给定可比较数组进行排序
// 输入:可比较数组A[0..n-1]子数组A[l..r]
// 输出:非降序排序的子数组A[l..r]
if l<r
s = partition(A[l..r])
Quicksort(A[l..s-1])
Quicksort(A[s+1..r])

特点

  • 需要选择合适的划分算法J

    • LomutoPartition
    • HoarePartition
  • 算法效率

    • 最优情况:分裂点都位于数组中点,算法比较次数为 $nlog_2n$
    • 最差情况:分裂点都趋于极端(逆序输入),算法比较 次数$\in \Theta(n^2)$
    • 平均:比较次数为$2nlnn \approx 1.39nlog_2n$
    • 且算法内层循环效率非常高,在处理随机排列数组时,速度 比合并排序快
  • 快速排序缺点

    • 不稳定
    • 需要堆栈存储未被排序的子数组参数,尽管可以先对较短 子数组排序使得堆栈大小降低到$O(logn)$,但是还是比 堆排序的$O(1)$差
    • 仍然存在最差情况出现的可能性,即使有很多巧妙地中轴 选择办法
    • 对随机数组排序性能的好坏,不仅与算法具体实现有关, 还和计算机系统结构、数据类型有关
  • 分治算法

算法改良

  • 更好的中轴选择方法

    • randomized quicksort:随机快速排序,使用随机元素作为 中轴
    • median-of-three method:三平均划分法,以数组最左边、 最右边、最中间的中位数作为中轴
  • 子数组足够小时(5~15),改用插入排序;或者直接不对小数组 排序,而是在快速排序结束后使用插入排序对整个近似有序的 数组进行排序

  • 改进划分方法

    • 三路划分:将数组划分为3段,小于、等于、大于中轴元素

比较计数排序

算法

  • 遍历待排序列表中每个元素
  • 计算、记录列表中小于该元素的元素个数
  • 更新大于其的元素的小于元素的元素个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ComparisonCountingSort(A[0..n-1])
// 用比较计数法排序
// 输入:可排序数组A[0..n-1]
// 输出:将A中可排序数组按照升序排列数组
for i = 0 to n-1 do
count[i] = 0
for i = 0 to n-2 do
for j = i+1 to n-1 do
if A[i] < A[j]
count[j] += 1
else
count[i] += 1
for i = 0 to n-1 do
S[count[i]] = A[i]

特点

  • 算法效率

    • 算法比较次数为$n(n-1)/2$
    • 占用了线性数量的额外空间
  • 算法使得键值的可能移动次数最小化,能够直接将键值放在在 有序数组最终位置

  • 输入增强

分布计数排序

  • 待排序元素来自于某个已知小集合$[l..u]$

算法

  • 扫描列表,计算、存储列表中元素出现频率于数组$F[l..u]$中
  • 再次扫描列表,根据值填入相应位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
DistributionCountingSort(A[0..n-1], l, u):
// 分布计数法排序,对元素来自有限范围整数的数组排序
// 输入:数组[0..n-1],数组中整数位于l、u间
// 输出:A中元素构成非降序数组S[0..n-1]
for j = 0 to u-l do
D[j] = 0
for i = 0 to n=1 do
D[A[i]-l] += 1
for j = 1 to u-l do
D[j] += D[j-1]
// 存储各元素最后出现索引+1
for i = n-1 downto 0 do
j = A[i] - l
S[D[j]-1] = A[i]
D[j] -= 1
// 更新应该存储的位置,类似于压栈
return S

特点

  • 算法效率

    • 如果元素值范围固定,效率为线性(不是基于比较的排序, $nlogn$没有限制)
    • 用空间换时间,其实可以看作是hash
    • 利用了输入列表独特自然属性
  • 变治法(输入增强)

应用

  • 判断线性表元素是否唯一
  • 寻找线性表众数
  • 快速查找

线性表顺序统计量

寻找列表中第k小的元素

  • 也即:求出给定列表中k个最小元素问题

  • 采用partitioning的思路,需要将给定列表根据某个值先行划分

    • Lumuto划分算法

QuickSelect算法

算法

  • 对划分完后出数组,s为分割位置
    • 若:s == k-1,则中轴p就是第k小元素
    • 若:s < k-1,则应该是数组右边划分第k-s小元素
    • 若:s > k-1,则应该是数组左边划分第k小元素
  • 这样就得到规模更小的问题实例
1
2
3
4
5
6
7
8
9
10
11
QuickSelect(A[l..r], k)
// 用基于划分递归算法解决选择问题
// 输入:可排序数组A[0..n-1]的子数组A[l..r]、整数k
// 输出:A[l..r]中第k小元素
s = Partition(A[l..r])
if s = l+k-1
return A[s]
elif s > l+k-1
QuickSelect(A[l..s-1], k)
else
QuickSelect(A[s+1..r], l+k-1-s)

特点

  • 时间效率:和划分算法有关(对Lomuto算法)

    • 最好情况下只需要划分一次即找到,需要比较$n-1$次
    • 最坏情况下需要比较$n(n-1)/2$次,这比直接基于排序更差
    • 数学分析表明,基于划分的算法平均情况下效率是线性的
  • 已经找到复杂算法替代Lomuto算法用于在快速选择中选出 中轴,在最坏情况下仍保持线性时间效率

  • QuickSelect算法可以不用递归实现,且非递归版本中甚至 不需要调整参数k值,只需要最后s == k-1即可

  • 减可变规模:Lomuto算法性质

线性表有序划分

LomutoPartition

算法

  • 考虑子数组A[l..r]分为三段,按顺序排在中轴p之后

    • 小于p的元素,最后元素索引记为s
    • 大于等于p的元素,最后元素索引记为i
    • 未同p比较过元素
  • 从左至右扫描A[l..r],比较其中元素和p大小

    • A[i] >= p,扩大大于等于p元素段
    • A[i] < p,需要扩大小于等于p元素段
1
2
3
4
5
6
7
8
9
10
11
12
LomutoPartition(A[l..r])
// 采用Lomuto算法,用首个元素作中轴划分数组
// 输入:可排序数组A[0..n-1]的子数组A[l..r]
// 输出:A[l..r]的划分、中轴位置
p = A[l]
s = l
for i = l+1 to r
if A[i] < p
s = s+1
swap(A[s], A[i])
swap(A[l], A[s])
return s

HoarePartition

算法

  • 选择一个元素p作为中轴(最简单的,首个元素p=A[l])

  • 从数组A[l..r]两端进行扫描,将扫描到的元素同中轴比较

    • 从左至右的扫描忽略小于中轴元素,直到遇到大于等于中轴 元素停止(从第二个元素开始i=l+1)
    • 从右至左的扫描忽略大于中轴元素,直到遇到小于等于中轴 元素停止(j=r-1)
  • 若扫描停止后

    • 两指针不相交i < j,交换A[i]、A[j],i=i+1、j=j-1, 继续扫描
    • 若指针相交i > j,把中轴和A[j]交换即得到数组一个划分 ,分裂点为s=j
    • 如果指针重合i==j,此元素一定等于p,也得到数组的一个 划分,分裂点为s==i==j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
HoarePartition(A[l..r])
// 以首元素为中轴,对数组进行划分
// 输入:可排序数组A[1..n]的子数组A[l..r]
// 输出:A[l..r]的一个划分,返回分裂点位置
p = A[l]
i = l
j = r+1
repeat
repeat i = i+1 until A[i] >= p
// 这里i有可能越界,可以添加一个限位器
repeat j = j-1 until j[i] <= p
// 从左右两端都是遇到等于p的元素就停止扫描
// 这样可以保证即使数组中有许多和p相等的元素
// 也能够将数组划分得比较均匀
swap(A[i], A[j])
// 这样写没有关系,不需要在这里给调整i、j
// 因为循环下一步就是调整i、j
until i >= j
swap(A[i], A[j])
// 撤销算法最后一次交换
swap(A[l], A[j])
return j

三路划分

算法

Author

UBeaRLy

Posted on

2019-04-18

Updated on

2019-04-18

Licensed under

Comments