内部排序(一)：各种内部排序方法的比较

作为数据结构的课程笔记，以便查阅。如有出错的地方，还请多多指正！

各种内部排序方法的比较

• $n$n较小/基本有序：可采用简单排序方法(直接插入、简单选择、冒泡排序)

• $n$n较大：可采用快排、堆排。若要求稳定性，则采用归并排序

• 从平均时间性能上看，快排最佳，但快排在最坏情况下的时间性能不如堆排和归并排序

• $n$n较大时，归并排序比堆排序用时少，但所需的辅助存储量多

• 基数排序适用于$n$n很大，关键字个数较少的序列。若关键字个数较多，而序列中大多数记录的最高为关键字均不同，则可先按最高为关键字将序列分为若干子序列，然后进行直接插入排序

地址排序

在顺序存储结构上进行排序需要移动大量记录。当记录很大时，时间耗费很多，此时可用静态链表。

但是快排、堆排等无法实现表排序，这种情况下可以使用地址排序，即另设一个地址向量指示相应记录，在排序过程中不移动记录而移动地址向量中相应分量的内容。在排序结束后，地址向量中的值指示排序后的记录次序。
例如：对记录r[8]附设向量adr(1:8)，开始排序时令adr[i]=i。排序中的r[i]=r[j]操作均以adr[i]=adr[j]代替。排序结束后r[adr[8]]即为关键字最大的记录，r[adr[1]]即为关键字最小的记录
r(1:8)： 49 65 38 27 97 13 76 49*
adr(1:8)：6 4 3 1 8 2 7 5

最后可根据需要按adr的值来重排记录的物理位置，重排算法如下：

• 从i=1起，检查每个分量位置上的记录是否在正确位置
• 若adr[i]=i，则位置正确，不需要调整
• 若adr[i]=k$\neq$​=i，则说明r[i]上应该存放r[k]。可以先暂存r[i]，然后将r[k]移至r[i]。然后继续检查位置k，若adr[k]$\neq$​=k，则将r[adr[k]]移至r[k]。直至找到j=adr[adr[...adr[k]...]]使adr[j]=i，将暂存记录移至r[j]

//根据地址数组对实际物理地址进行重排
void Rearrange(SqList_t* list, int adr[])
{
	for (int i = 1; i <= list->len; ++i)
	{
		if (adr[i] != i)
		{
			int j, k;
			list->rec[0] = list->rec[i]; //暂存记录
			for (j = i; adr[j] != i; j = k)//找到位置i应该存放的记录
			{
				k = adr[j]; //位置j处应该存放记录k
				list->rec[j] = list->rec[k];
				adr[j] = j; //改变地址数组
			}
			//位置i上的元素实际应该存放在位置j
			list->rec[j] = list->rec[0];
			adr[j] = j;
		}
	}
}

(基于关键字比较的)内部排序在最坏情况下的最快速度

考虑一棵比较3个关键字K1,K2,K3的判定树，它表示了直接插入排序的过程。每个非终端结点表示两个关键字的一次比较，叶结点表示6种排序结果。而每一个初始序列经排序达到有序所需的比较次数，则为从根到对应叶结点的路径长。判定树深度为4，则在最坏情况下，对3个记录排序至少要3次比较。

推广至$n$n个记录的情况：含$n$n个记录的序列可能出现$n!$n!个初始状态，对应的判定树有$n!$n!个叶结点。又因为高度为$h$h的二叉树，叶结点个数$\leq2^{h-1}$≤2h−1。因此若有$x$x个叶结点，则$h\geq\lceil log_2x \rceil+1$h≥⌈log2​x⌉+1。也就是说，$n!$n!个叶结点的判定树必定存在一条$\lceil log_2n! \rceil$⌈log2​n!⌉的路径。根据斯特林公式，$\lceil log_2n! \rceil=O(nlogn)$⌈log2​n!⌉=O(nlogn)

因此，基于关键字比较的内部排序在最坏情况下的最好时间复杂度为$O(nlogn)$O(nlogn)