排序

排序基本概念

排序（Sort），就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

排序算法的评价指标

• 时间复杂度

• 空间复杂度

• 算法的稳定性。 若待排序表中有两个元素$R_I$ 和 R j ，其对应的关键字相同即$ke{y}_i=ke{y}_j$ ，且在排序 前$R_I$ 在$R_j$ 的前⾯ 若使用某⼀排序算法排序后，$R_I$ 仍然在$R_j$ 的前⾯，则称这个排序算法是稳定 的，否则称排序算法是不稳定的。

排序类型	时间复杂度			空间复杂度	是否稳定
	最好情况	平均情况	最坏情况
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
希尔排序				$O(1)$	否
快速排序	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(n^2)$	$O(lo{g}_{2}n)$	否
堆排序	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(1)$	否
归并排序	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(n)$	是
基数排序	$O(d(n+r)$)	$O(d(n+r)$)	$O(d(n+r)$)	$O(r)$	是

分类

总结

可视化算法 (opens new window)

插入排序

算法思想：每次将⼀个待排序的记录按其关键字大小插入到前⾯已排好序的子序列中，直到全部记录插入完成。

以此类推，直到全部记录插入完成

算法实现

//直接插入排序
void InsertSort(int A[], int n) {
	int i, j, temp;
	for (i = 1; i < n; i++) { //将各元素插入已排好序的序列中
		if (A[i] < A[i - 1]) { //若A[i]关键字小于前驱
			temp = A[i]; //用temp暂存A[i]
			for (j = i - 1; j >= 0 && A[j] > temp; --j) { //检查所有前面已排好序的元素
				A[j + 1] = A[j]; //所有大于temp的元素都向后挪位
			}
			A[j + 1] = temp; //复制到插入位置
		}
	}
}

//直接插入排序（带哨兵）
void InsertSort(int A[], int n) {
	int i, j;
	for (i = 2; i <= n; i++) { //依次将A[2]~A[n]插入到前面已排序序列
		if (A[i] < A[i - 1]) { //若A[i]关键字小于其前驱，将A[i]插入有序表
			A[0] = A[i]; //复制为哨兵，A[0]不存放元素
			for (j = i - 1; A[0] < A[j]; --j) { //从后往前查找待插入位置
				A[j + 1] = A[j]; //向后挪位
			}
			A[j + 1] = A[0]; //复制到插入位置
		}
	}
}

算法效率分析

空间复杂度：$O(1)$

时间复杂度：主要来自对比关键字、移动元素若有 n 个元素，则需要 n-1 趟处理

最好情况：共 n-1 趟处理，每⼀趟只需要对比关键字 1 次，不用移动元素，最好时间复杂度 —— $O(n)$

最坏情况：第 i 趟：对比关键字 i+1 次，移动元素 i+2 次，最坏时间复杂度 ——$O(n^2)$

---

空间复杂度：$O(1)$ 最好时间复杂度（全部有序）：$O(n)$ 最坏时间复杂度（全部逆序）：$O(n^2)$ 平均时间复杂度：$O(n^2)$

算法稳定性：稳定

优化 —— 折半插入排序

思路：先用折半查找前面已经有序的元素找到应该插入的位置，再移动元素

当 low>high 时折半查找停止，应将 [low, i-1] 内的元素全部右移，并将 A [0] 复制到 low 所指位置

如果遇到相同元素呢？

当 A [mid]==A [0] 时，为了保证算法的 “稳定性”，应继续在 mid 所指位置右边寻找插入位置

当 low>high 时折半查找停止，应将 [low, i-1] 内的元素全部右移，并将 A [0] 复制到 low 所指位置

//折半插入排序
void InsertSort(int A[], int n) {
	int i, j, low, high, mid;
	for (i = 2; i <= n; i++) { //依次将A[2]~A[n]插入到前面已排序序列
		A[0] = A[i]; //将A[i]暂存到A[0]
		low = 1; high = i - 1; //设置折半查找的范围
		while (low < high) { //折半查找（默认递增有序）
			mid = (low + high) / 2; //取中间点
			if (A[mid] > A[0]) { //查找左半子表
				high = mid - 1;
			} else { //查找右半子表
				low = mid + 1;
			}
		}
		for (j = i - 1; j >= high + 1; --j) {
			A[j + 1] = A[j]; //统一后移元素，空出插入位置
		}
		A[high + 1] = A[0]; //插入操作
	}
}

• 当 low>high 时折半查找停止，应将 [low, i-1] 内的元素全部右移，并将 A [0] 复制到 low 所指位置
• 当 A [mid]==A [0] 时，为了保证算法的 “稳定性”，应继续在 mid 所指位置右边寻找插入位置

比起 “直接插入排序”，比较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度依然是$O(n^2)$

对链表进行插入排序

移动元素的次数变少了，但是关键字对比的次数依然是$O(n^2)$ 数量级，整体来看时间复杂度依然是$O(n^2)$

总结

希尔排序

希尔排序：先追求表中元素部分有序，再逐渐逼近全局有序； 先将待排序表分割成若⼲形如 $L[i,i+d,i+2d,\dots ,i+kd]$ 的 “特殊” 子表，对各个子表分别进行直接插入排序。缩小增量 d，重复上述过程，直到 d=1 为止。

整个表已呈现出 “基本有序”，对整体再进行⼀次 “直接插入排序”

整合，希尔本⼈建议：每次将增量缩小⼀半

也可以将增量缩小其他值，，考试中可能遇到各种增量

算法实现

//希尔排序
void ShellSort(int A[], int n) {
	int d, i, j;
	//A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
	for (d = n / 2; d >= 1; d = d / 2) {
		for (i = d + 1; i <= n; ++i) { //步长变化
			if (A[i] < A[i - d]) {
				A[0] = A[i]; //暂存在A[0]
				for (j = i - d; j > 0 & A[0] < A[j]; j -= d) {
					A[j + d] = A[j]; //记录后移，查找插入的位置
				}
				A[j + d] = A[0]; //插入
			}
		}
	}
}

算法性能分析

时间复杂度：和增量序列 $d_1 , d_2 , d_3 … $\mathrm{的}\mathrm{选}\mathrm{择}\mathrm{有}\mathrm{关}，\mathrm{目}\mathrm{前}\ast \ast \mathrm{⽆}\mathrm{法}\mathrm{用}\mathrm{数}\mathrm{学}\mathrm{手}\mathrm{段}\mathrm{证}\mathrm{明}\mathrm{确}\mathrm{切}\mathrm{的}\mathrm{时}\mathrm{间}\mathrm{复}\mathrm{杂}\mathrm{度}\ast \ast \mathrm{最}\mathrm{坏}\mathrm{时}\mathrm{间}\mathrm{复}\mathrm{杂}\mathrm{度}\mathrm{为}$ O (n^2)$，\mathrm{当}n\mathrm{在}\mathrm{某}\mathrm{个}\mathrm{范}\mathrm{围}\mathrm{内}\mathrm{时}，\mathrm{可}\mathrm{达}$ O (n^{1.3} )$

稳定性：不稳定！

适用性：仅适用于顺序表，不适用于链表

总结

冒泡排序

基于 “交换” 的排序：根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即$A[i-1]>A[i]$），则交换它们，直到序列比较完。称这样过程为 “⼀趟” 冒泡排序。

以此类推，直到某⼀趟排序没有发⽣ “交换”

算法实现

//交换
void swap(int &a, int &b) {
	int temp = a;
	a = b;
	b = temp;
}

//冒泡排序
void BubbleSort(int A[], int n) {
	for (int i = 0; i < n - 1; i++) {
		bool flag = false; //表示本趟冒泡是否发生交换的标志
		for (int j = n - 1; j > i; j--) { //一趟冒泡过程
			if (A[j - 1] > A[j]) { //若为逆序，只有A[j-1]>A[j]时才交换，因此算法是稳定的
				swap(A[j - 1], A[j]); //交换
				flag = true;
			}
		}
		if (flag == false) {
			return; //本趟遍历后没有发生交换，说明表已经有序
		}
	}
}

算法性能分析

空间复杂度：$O(1)$

最好情况（有序）：比较次数 = n-1；交换次数 = 0 最好时间复杂度 =$O(n)$

最坏情况（逆序）：比较次数$=(n-1)+(n-2)+\dots +1=\frac{n(n-1)}{2}=$ 交换次数

最坏时间复杂度 =$O(n^2)$

平均时间复杂度 =$O(n^2)$

总结

快速排序

算法思想：在待排序表 L [1…n] 中任取⼀个元素 pivot 作为枢轴（或基准，通常取⾸元素），通过⼀趟排序将待排序表划分为独立的两部分 L [1…k-1] 和 L [k+1…n]，使得 L [1…k-1] 中的所有元素小于 pivot，L [k+1…n] 中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L (k) 上，这个过程称为⼀次 “划分”。然后分别递归地对两个子表重复上述过程，直⾄每部分内只有⼀个元素或空为止，即所有元素放在了其最终位置上。

以 49 作为枢轴（或基准）

以 49 为基准，将左右拆分为两个子表，重复上述步骤

右子表

算法实现

//快速排序
void QuickSort(int A[], int low, int high) {
	if (low < high) { //递归跳出的条件
		int pivotpos = Partition(A, low, high); //划分
		QuickSort(A, low, pivotpos - 1); //划分左子表
		QuickSort(A, pivotpos + 1, high); //划分右子表
	}
}

//用第一个元素将带排序序列划分成左右两个部分
int partition(int A[], int low, int high) {
	int pivot = A[low]; //第一个元素作为枢轴
	while (low < high) { //用low、high搜索枢轴的最终位置
		while (low < high && A[high] >= pivot) {
			--high;
		}
		A[low] = A[high]; //比枢轴小的元素移动到左端
		while (low < high && A[low] <= pivot) {
			++low;
		}
		A[high] = A[low]; //比枢轴大的元素移动右端
	}
	A[low] = pivot; //枢轴元素存放到最终位置
	return low; //返回存放枢轴的最终位置
}

算法效率分析

时间复杂度 = O (n * 递归层数)

空间复杂度 = O (递归层数)

把 n 个元素组织成⼆叉树，⼆叉树的层数就是递归调用的层数

最好时间复杂度 =$O(nlo{g}_2^n)$ 最坏时间复杂度 =$O(n_2)$

最好空间复杂度 =$O(lo{g}_2^n)$ 最坏空间复杂度 =$O(n)$

平均时间复杂度 =$O(nlo{g}_2^n)$

稳定性：不稳定！

最坏的情况

若每⼀次选中的 “枢轴” 将待排序序列划分为很不均匀的两个部分，则会导致递归深度增加，算法效率变低

若初始序列有序或逆序，则快速排序的性能最差（因为每次选择的都是最靠边的元素）

比较好的情况

若每⼀次选中的 “枢轴” 将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最⾼

快速排序算法优化思路：尽量选择可以把数据中分的枢轴元素。

1. 选头、中、尾三个位置的元素，取中间值作为枢轴元素；
2. 随机选⼀个元素作为枢轴元素

总结

简单选择排序

选择排序：每⼀趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列

简单选择排序：每⼀趟在待排序元素中选取关键字最小的元素加入有序子序列

算法实现

//简单选择排序
void SelectSort(int A[], int n) {
	for (int i = 0; i < n - 1; i++) { //一共进行n-1趟
		int min = i; //记录最小元素的位置
		for (int j = i + 1; j < n; j++) { //在A[i~n-1]中选择最小的元素
			if (A[j] < A[min]) {
				min = j; //更新最小元素位置
			}
		}
		if (min != i) {
			swap(A[i], A[min]); //封装的swap()函数共移动元素3次
		}
	}
}

//交换
void swap(int &a, int &b) {
	int temp = a;
	a = b;
	b = temp;
}

算法性能分析

空间复杂度：$O(1)$

时间复杂度：$O(n^2)$

稳定性：不稳定

总结

堆排序

若 n 个关键字序列 L [1…n] 满足下⾯某⼀条性质，则称为堆（Heap）：

• 若满足：$L (i)≥L (2i) 且 L (i)≥L (2i+1) $$（1 ≤ i ≤n/2 ）$—— 大根堆（大顶堆）
• 若满足：$L(i)\le L(2i)\mathrm{且}L(i)\le L(2i+1)$ $（1\le i\le n/2）$—— 小根堆（小顶堆）

建立大根堆

大根堆：根≥左、右

思路：把所有非终端结点都检查⼀遍，是否满足大根堆的要求，如果不满足，则进行调整

在顺序存储的完全⼆叉树中，非终端结点编号 $i\le \lfloor n/2\rfloor$

检查当前结点是否满足 根≥左、右，若不满足，将当前结点与更大的⼀个孩子互换

若元素互换破坏了下⼀级的堆，则采用相同的⽅法继续往下调整（小元素不断 “下坠”）

代码实现

//建立大根堆
void BuildMaxHeap(int A[], int len) {
	for (int i = len / 2; i > 0; i--) { //从后往前调整所有非终端结点
		HeadAdjust(A, i, len);
	}
}

//以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len) {
	A[0] = A[k]; //A[0]暂存子树的根结点
	for (int i = 2 * k; i <= len; i *= 2) { //沿key较大的子结点向下筛选
		if (i < len && A[i] < A[i + 1]) {
			i++; //取key较大的子结点下标
		}
		if (A[0] >= A[i]) { //筛选结束
			break;
		} else {
			A[k] = A[i]; //将A[i]调整到双亲结点上
			k = i; //修改k值，以便继续向下筛选
		}
	}
	A[k] = A[0]; //被筛选结点的值放入最终位置
}

基于大根堆进行排序

堆排序：每⼀趟将堆顶元素加入有序子序列（与待排序序列中的最后⼀个元素交换）

将待排序元素序列再次调整为大根堆（小元素不断 “下坠”）调用 HeadAdjust(A ,1 ,len-1)

经过调整后待排序元素序列再次构成⼀个 “大根堆

以此类推，不断与待排序序列中的最后⼀个元素交换，并将待排序元素序列再次调整为大根堆

注意：基于 “大根堆” 的堆排序得到 “递增序列”

代码实现

//建立大根堆
void BuildMaxHeap(int A[], int len) {
	for (int i = len / 2; i > 0; i--) { //从后往前调整所有非终端结点
		HeadAdjust(A, i, len);
	}
}

//以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len) {
	A[0] = A[k]; //A[0]暂存子树的根结点
	for (int i = 2 * k; i <= len; i *= 2) { //沿key较大的子结点向下筛选
		if (i < len && A[i] < A[i + 1]) {
			i++; //取key较大的子结点下标
		}
		if (A[0] >= A[i]) { //筛选结束
			break;
		} else {
			A[k] = A[i]; //将A[i]调整到双亲结点上
			k = i; //修改k值，以便继续向下筛选
		}
	}
	A[k] = A[0]; //被筛选结点的值放入最终位置
}

//堆排序的完整逻辑
void HeapSort(int A[], int len) {
	BuildMaxHeap(A, len); //初始建堆
	for (int i = len; i > 1; i--) { //n-1趟的交换和调整堆过程
		swap(A[i], A[1]); //堆顶元素和堆底元素交换
		HeadAdjust(A, 1, i - 1); //把剩下的待排序元素整理成堆
	}
}

算法效率分析

建堆过程

⼀个结点，每 “下坠” ⼀层，最多只需对比关键字 2 次

若树⾼为 h，某结点在第 i 层，则将这个结点向下调整最多只需要 “下坠”$ h-i$ 层，关键字对比次数不超过 $2(h-i)$

---

排序过程

总共需要$n-1$ 趟，每⼀趟交换后都需要将根节点 “下坠” 调整

根节点最多 “下坠” h-1 层，每下坠⼀层

⽽每 “下坠” ⼀层，最多只需对比关键字 2 次，因此每⼀趟排序复杂度不超过 $O(h)=O(lo{g}_{2}n)$

共 $n-1 $\mathrm{趟}，\mathrm{总}\mathrm{的}\mathrm{时}\mathrm{间}\mathrm{复}\mathrm{杂}\mathrm{度}$ = O (nlog_2 n)$

堆排序的时间复杂度 $=O(n)+O(nlo{g}_{2}n)=O(nlo{g}_{2}n)$ 堆排序的空间复杂度 $=O(1)$

稳定性

if (i < len && A[i] < A[i + 1]) {
    i++; //取key较大的子结点下标
}

注意：若左右孩子⼀样大，则优先和左孩子交换

结论：堆排序是不稳定的

总结

堆插入删除

在堆中插入新元素

对于小根堆，新元素放到表尾，与⽗节点对比，若新元素比⽗节点更小，则将⼆者互换。新元素就这样⼀路 “上升”，直到⽆法继续上升为止

插入 13 元素

对比关键字的次数 = 3 次

在堆中删除元素

删除 13 元素

被删除的元素用堆底元素替代，然后让该元素不断 “下坠”，直到⽆法下坠为止

对比关键字的次数 = 4 次

总结

归并排序

归并：把两个或多个已经有序的序列合并成⼀个

只剩⼀个子表未合并时，可以将该表中剩余元素全部加到总表

2 路归并

归并：把两个或多个已经有序的序列合并成⼀个

“2 路” 归并 —— 每选出⼀个小元素注需对比关键字 1 次

4 路归并

“4 路” 归并 —— 每选出⼀个小元素注需对比关键字 3 次

结论：m 路归并，每选出⼀个元素需要对比关键字 m-1 次

归并排序（手算模拟）

在内部排序中⼀般采用 2 路归并

核⼼操作：把数组内的两个有序序列归并为⼀个

代码实现

int *B = (int *)malloc(n*sizeof(int)); //辅助数组B

//A[low~mid]和A[mid+1~high]各自有序，将两个部分归并
void Merge(int A[], int low, int mid, int high) {
	int i, j, k;
	for (k = low; k <= high; k++) {
		B[k] = A[k]; //将A中所有元素复制到B中
	}
	for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
		if (B[i] <= B[j]) {
			A[k] = B[i++]; //将较小值赋值到A中
		} else {
			A[k] = B[j++];
		}
	}
	while (i <= mid) {
		A[k++] = B[i++];
	}
	while (j <= high) {
		A[k++] = B[j++];
	}
}

void MergeSort(int A[], int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2; //从中间划分
		MergeSort(A, low, mid); //对左半部分归并排序
		MergeSort(A, mid + 1, high); //对右半部分归并排序
		MergeSort(A, mid, high); //归并
	}
}

下面是一趟合并的过程

没有归并完的部分复制到尾部

算法效率分析

2 路归并的 “归并树”—— 形态上就是⼀棵倒立的⼆叉树

⼆叉树的第 h 层最多有 $2^{h-1}$ 个结点，若树⾼为 h，则应满足$n\le 2^{h-1}$，即$h-1=\lceil lo{g}_{2}n\rceil$

结论：n 个元素进行 2 路归并排序，归并趟数$\lceil lo{g}_{2}n\rceil$

每趟归并时间复杂度为$O(n)$ ，则算法时间复杂度为 $O(nlo{g}_{2}n)$，空间复杂度$=O(n)$ ，来⾃于辅助数组 B

总结

基数排序

第⼀趟：以 “个位” 进行 “分配”

第⼀趟 “收集”

第⼀趟 “收集” 结束：得到按 “个位” 递减排序的序列

第⼆趟：以 “⼗位” 进行 “分配”

第⼆趟 “收集”：

第⼆趟 “收集” 结束：得到按 “⼗位” 递减排序的序列，“⼗位” 相同的按 “个位” 递减排序

第三趟 “收集”

第三趟按 “百位” 分配、收集：得到⼀个按 “百位” 递减排列的序列，若 “百位” 相同则按 “⼗位” 递减排列，若 “⼗位” 还相同则按 “个位” 递减排列

---

基数排序得到递减序列的过程如下：

• 初始化： 设置 r 个空队列，$Q_{r-1},Q_{r-2},\dots ,Q_0$
• 按照各个 关键字位 权重递增的次序（个、⼗、百），对 d 个关键字位分别做 “分配” 和 “收集”
• 分配：顺序扫描各个元素，若当前处理的关键字位 = x，则将元素插入 $Q_x$ 队尾
• 收集：把 $Q_{r-1},Q_{r-2},\dots ,Q_0$ 各个队列中的结点依次出队并链接

注意：基数排序不是基于 “比较” 的排序算法

基数排序得到递增序列的过程如下：

• 初始化： 设置 r 个空队列，$Q_0,Q_1,\dots ,Q_{r-1}$
• 按照各个 关键字位 权重递增的次序（个、⼗、百），对 d 个关键字位分别做 “分配” 和 “收集”
• 分配：顺序扫描各个元素，若当前处理的关键字位 = x，则将元素插入 $Q_x$ 队尾
• 收集：把 $Q_0,Q_1,\dots ,Q_{r-1}$ 各个队列中的结点依次出队并链接

算法效率分析

需要 r 个辅助队列，空间复杂度 $=O(r)$

⼀趟分配$O(n)$，⼀趟收集$O(r)$，总共 d 趟分配、收集，总的时间复杂度$=O(d(n+r)）$

稳定性

基数排序的应用

基数排序擅长解决的问题：

1. 数据元素的关键字可以⽅便地拆分为 d 组，且 d 较小
2. 每组关键字的取值范围不大，即 r 较小
3. 数据元素个数 n 较大；如给⼗亿⼈的身份证号排序

总结

外部排序

外存、内存之间的数据交换

操作系统以 “块” 为单位对磁盘存储空间进行管理，如：每块大小 1KB 各个磁盘块内存放着各种各样的数据

申请缓冲区

读取块到缓冲区中，磁盘的读 / 写以 “块” 为单位数据读入内存后才能被修改修改完了还要写回磁盘

修改缓冲区数据

以块为单位，重新写入磁盘

或者写入其他块

外部排序原理

外部排序：数据元素太多，⽆法⼀次全部读入内存进行排序

使用 “归并排序” 的⽅法，最少只需在内存中分配 3 块大小的缓冲区即可对任意⼀个大⽂件进行排序

构造初始 “归并段”

“归并排序” 要求各个子序列有序，每次读入两个块的内容，进行内部排序后写回磁盘

这样的步骤就完成了⼀个有序的 “归并段”，重复上述步骤直到将上述 16 个块完成内部有序。

第⼀趟归并

把 8 个有序子序列（初始归并段）两两归并，将两个有序归并段归并为⼀个

写回外存

缓冲区 1 空了就要立即用归并段 1 的下⼀块补上

缓冲区 2 空了就要立即用归并段 2 的下⼀块补上

重复上述步骤两两归并，指定将八个归并段完成两两内部有序

第⼆趟归并

把 4 个有序子序列（归并段）两两归并

不断重复读取归并写入，指定将两个归并段合成为一个有序的归并段

注意：虽然我们图中外存写入位置是原位置，但在计算机底层中我们是开辟了另外的空间写入，而原先空间归还给系统，具体底层在计算机操作系统课程中。

第三趟归并

把 2 个有序子序列（归并段）归并

时间开销分析

外部排序时间开销 = 读写外存的时间 + 内部排序所需时间 + 内部归并所需时间

优化 - 多路归并

重要结论：采用多路归并可以减少归并趟数，从⽽减少磁盘 I/O (读写) 次数

多路归并带来的负⾯影响：

1. k 路归并时，需要开辟 k 个输入缓冲区，内存开销增加。
2. 每挑选⼀个关键字需要对比关键字$（k-1）$次，内部归并所需时间增加

优化 - 减少初始归并段数量

⽣成初始归并段的 “内存⼯作区” 越大，初始归并段越长

结论：若能增加初始归并段的长度，则可减少初始归并段数量 r

总结

纠正：什么是多路平衡归并？

k 路平衡归并：

1. 最多只能有 k 个段归并为⼀个；
2. 每⼀趟归并中，若有 m 个归并段参与归并，则经过这⼀趟处理得到 个新的归并段$\lceil m/k\rceil$

败者树

多路平衡归并带来的问题

外部排序时间开销 = 读写外存的时间 + 内部排序所需时间 + 内部归并所需时间

归并趟数$S=\lceil lo{g}_{k}r\rceil$ ，归并路数 k 增加，归并趟数 S 减小，读写磁盘总次数减少，归并路数 k 增加，归并趟数 S 减小，读写磁盘总次数减少

使用 k 路平衡归并策略，选出⼀个最小元素需要对比关键字 （k-1）次，导致内部归并所需时间增加

eg：8 路平衡归并，从⼋个归并段中选出⼀个最小元素需要对比关键字 7 次

败者树

失败者留在这⼀回合，胜利者进入下⼀回合比拼

败者树 —— 可视为⼀棵完全⼆叉树（多了⼀个头头）。k 个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的 “失败者”，⽽让胜者往上继续进行比较，⼀直到根结点。

败者树在多路平衡归并中的应用

对于 k 路归并，第⼀次构造败者树需要对比关键字 k-1 次

选出当前最小值 1

头头结点记录的是归并段 3，所以下一个元素从归并段 3 中选出，并替代原来 1 位置的叶子节点

重新对比

更新败者树中的归并段

有了败者树，选出最小元素，只需对比关键字$\lceil lo{g}_{2}k\rceil$ 次

败者树的实现思路

总结

败者树解决的问题：使用多路平衡归并可减少归并趟数，但是用⽼土⽅法从 k 个归并段选出⼀个最小 / 最大元素需要对比关键字 k-1 次，构造败者树可以使关键字对比次数减少到 $\lceil lo{g}_{2}k\rceil$

败者树可视为⼀棵完全⼆叉树（多了⼀个头头）。k 个叶结点分别对应 k 个归并段中当前参加比较的元素，非叶子结点用来记忆左右子树中的 “失败者”，⽽让胜者往上继续进行比较，⼀直到根结点。

置换 - 选择排序

土办法构造初始归并段

置换 - 选择排序

将当前内存工作区最小的元素置换出去，并用变量 MINMAX 记录值

从带排序文件中读取

以此类推，重复读取代排序文件中的元素放入内存工作区，置换最小元素并更新 MINMAX

当出现当前内存工作区中最小元素比 MINMAX 更小的情况，不能把 10 置换出去，只能选择比 MINMAX 大并在内存工作区考前的元素（即 14）

若 WA 内的关键字都比 MINIMAX 更小，则该归并段在此截止

重复上述步骤，直到 WA 内的关键字都比 MINMAX 更小，然后截取归并段。

总结

设初始待排⽂件为 FI，初始归并段输出⽂件为 FO，内存⼯作区为 WA，FO 和 WA 的初始状态为空，WA 可容纳 w 个记录。置换 - 选择算法的步骤如下：

1. 从 FI 输入 w 个记录到⼯作区 WA。
2. 从 WA 中选出其中关键字取最小值的记录，记为 MINIMAX 记录。
3. 将 MINIMAX 记录输出到 FO 中去。
4. 若 FI 不空，则从 FI 输入下⼀个记录到 WA 中。
5. 从 WA 中所有关键字比 MINIMAX 记录的关键字大的记录中选出最小关键字记录，作为新的 MINIMAX 记录。
6. 重复 3～5，直⾄在 WA 中选不出新的 MINIMAX 记录为止，由此得到⼀个初始归并段，输出⼀个归并段的结束标志到 FO 中去。
7. 重复 2～6，直⾄ WA 为空。由此得到全部初始归并段。

最佳归并树

归并树的神秘性质

每个初始归并段看作⼀个叶子结点，归并段的长度作为结点权值，则这棵归并树的带权路径长度 $WPL=2\ast 1+(5+1+6+2)\ast 3=44=$ 读磁盘的次数 $=$ 写磁盘的次数

重要结论 ：归并过程中的磁盘 I/O 次数 = 归并树的 WPL * 2

要让磁盘 I/O 次数最少，就要使归并树 WPL 最小 —— 哈夫曼树！

构造 2 路归并的最佳归并树

最佳归并树 $WP{L}_{min}=(1+2)\ast 4+2\ast 3+5\ast 2+6\ast 1=34$

读磁盘次数 = 写磁盘次数 = 34 次；总的磁盘 I/O 次数 = 68

多路归并的情况

$WPL=(9+30+12+18+3+17+2+6+24)\ast 2=242$

归并过程中 磁盘 I/O 总次数 = 484 次

多路归并的最佳归并树

上图这棵就是 3 路归并的最佳归并树

$WP{L}_{min}=(2+3+6)\ast 3+(9+12+17+24+18)\ast 2+30\ast 1=223$

归并过程中 磁盘 I/O 总次数 = 446 次

如果减少⼀个归并段

上图这个不是最佳归并树

$WPL=(2+3+6)\ast 3+(9+12+17+24+18)\ast 2=193$

归并过程中 磁盘 I/O 总次数 = 386 次

正确的做法

对于 k 叉归并，若初始归并段的数量⽆法构成严格的 k 叉归并树，则需要补充⼏个长度为 0 的 “虚段”，再进行 k 叉哈夫曼树的构造。

上图这棵就是 3 路归并的最佳归并树

$WP{L}_{min}=(2+3+0)\ast 3+(6+9+12+17+18)\ast 2+24\ast 1=163$

归并过程中 磁盘 I/O 总次数 = 326 次

添加虚段的数量

k 叉的最佳归并树⼀定是⼀棵严格的 k 叉树，即树中只包含度为 k、度为 0 的结点。

设度为 k 的结点有 $ n_k$ 个，度为 0 的结点有 $n_0$ 个 ，归并树总结点数 = n 则：

初始归并段数量 + 虚段数量 =$n_0$

1. 若$（\mathrm{初}\mathrm{始}\mathrm{归}\mathrm{并}\mathrm{段}\mathrm{数}\mathrm{量}-1）\mathrm{\%}（k-1）=0$，说明刚好可以构成严格 k 叉树，此时不需要添加虚段
2. 若$（\mathrm{初}\mathrm{始}\mathrm{归}\mathrm{并}\mathrm{段}\mathrm{数}\mathrm{量}-1）\mathrm{\%}（k-1）=u\ne 0$，则需要补充 $(k-1) - u $ 个虚段

总结