排序

总述

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

目的

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

发展

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

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

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

评价

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

线性表排序

选择排序

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

顺序表算法

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次，列表有序

链表算法

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轮，列表有序

顺序表算法

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]

链表算法

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

特点

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

改进

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

Insertion Sort

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

算法

• 假设对较小数组$A[0..i-2]$排序已经解决
• 从右至左（方便将将元素右移）扫描有序子数组，直到遇到首个 小于等于$A[i-1]$元素，将$A[i-1]$插入其后

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排序退化（最后一轮）为插入排序

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]均分的
• 对两个子数组递归排序，然后把排序后的子数组合并为有序 数组

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

• 初始两只指针指向待合并数组首个元素
• 比较两个元素大小，将较小元素添加到新数组中，被复制元素 的数组指针右移
• 重复直到某一数组处理完毕，将未处理完数组复制到新数组尾部

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]左右子数组进行排序

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段，小于、等于、大于中轴元素

比较计数排序

算法

• 遍历待排序列表中每个元素
• 计算、记录列表中小于该元素的元素个数
• 更新大于其的元素的小于元素的元素个数

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]$中
• 再次扫描列表，根据值填入相应位置

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小元素
• 这样就得到规模更小的问题实例

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元素段

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

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

三路划分

算法