排序 - PipaHub

概念#

稳定性
内部排序外部排序
待排序的容器的物理排列方式顺序链式
时空复杂度
基于比较的排序的时间复杂度下限 $O(logn!)$ 一个不精确的下界 $O(nlogn)$

内部排序#

基于插入#

直接插入
折半插入
希尔排序

基于交换#

冒泡
快排

findpivot(arr, low, high) {
	pivot := arr[low]
	i := low
	j := high
	while i < j {
		while i < j and arr[j] >= pivot { j-- }
		arr[i] = arr[j]
		while i < j and arr[i] <= pivot { i++ }
		arr[j] = arr[i]
	}
	arr[i] = pivot
	return i
}

quicksort(arr, low = 0, high = arr.len - 1) {
	if(high <= low) return
	pivot := findpivot(arr,low,high)
	quicksort(arr,low,pivot-1)
	quicksort(arr,pivot+1,high)
}

基于选择#

选择排序
堆排序堆

其他#

归并
基数
- MSD高位优先，先根据高位关键字排序，分为若干个子序列，子序列内再用次关键字排序
- LSD优先，先对列表按次关键字排序，再按主关键字排序
计数

比较#

	空间复杂度	时间复杂度	最坏时间复杂度	最好时间复杂度	稳定性	特点	适用容器
直接插入	$O(1)$	$O(n^2)$	$O(n^2)$ ,完全逆序	$O(n)$ ,有序	O	在基本有序的情况下表现还行，第n趟后前n+1个元素有序	数组，链表
折半插入	$O(1)$	$O(n^2)$	$O(n^2)$ ,完全逆序	$O(n)$ ,有序	O	在基本有序的情况下表现还行，第n趟后前n+1个元素有序。对于规模一定的数组，比较总次数一定	数组
希尔排序	$O(1)$	$O(n^{1.3})$	$O(n^2)$		X		数组
冒泡排序	$O(1)$	$O(n^2)$	$O(n^2)$	$O(n)$	O	当某一趟没有发生交换时即可完成排序前n趟确定n个最小值放在前n个位置作为最终位置	数组链表
快速排序	跟递归深度有关平均 $O(logn)$ 最坏 $O(n)$	$O(nlogn)$	$O(n^2)$ 逆序或者顺序的情况	$O(nlogn)$	X	每一趟确定pivot的最终位置	数组
选择排序	$O(1)$	$O(n^2)$	$O(n^2)$	$O(n^2)$	X	对于规模一定的数组，比较总次数一定前n趟确定n个最小值放在前n个位置作为最终位置	数组链表
堆排序	$O(1)$	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	X	前n趟确定n个最大值放在后n个位置作为最终位置	数组
归并	$O(n)$	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	O	归并段内有序第i趟后有 $n/2^i$ 个有序归并段	数组
基数	要开辟r个队列 $O(r)$	如果关键字由d个子关键字组成，那么一共要进行d趟的分配搜集操作，分配的复杂度是 $O(n)$ ,搜集的复杂度是 $O(r)$ ,故总的复杂度是 $O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	O	不采用比较来进行排序故运行开销与初始状态无关仅适用于整形排序，整形范围不宜过大	链表
计数	-

外部排序#

排序 = IO + 内部排序生成初始归并段 + IO + 多趟内部归并 + IO
输入次数 = 输入次数 = (归并趟数量 + 1)X总磁盘块数
IO次数 = 2X(归并趟数量 + 1)X总磁盘块数
- 故归并树的深度越小IO次数越少即k路归并的k值越大IO次数越小
- 或者减少初始归并段段数量
内部归并采用败者树可以做到比较次数与k值无关
- https://oi-wiki.org/ds/loser-tree/
- 败者树的维护一定是从叶子到根的区别与堆
使用置换选择排序生成初始归并段，使得生成的初始归并段尽可能少最小的归并段长度是WA的长度，最大的归并段长度即FI的长度
最佳归并树使用置换选择排序生成的是长度不一的初始归并段，使用最佳归并树来组织归并顺序使得IO次数最少。最佳归并树是一颗K叉哈夫曼树，归并过程中的IO次数是其WPL的两倍
- 若初始归并段的数量无法恰好满足，补充长度为0的“虚段” 设采用K路归并，初始归并段数量为n，若 $(n−1)mod(k−1)=0$ ，则不用补充虚段，否则 $(n−1)mod(k−1)=u!=0$ ，补充 $(k−1)−u$ 个虚段