内部排序(四)：选择排序 Selection Sorting (简单选择排序、堆排序)

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

注：C++忘得太厉害了。。算法先用C实现，等之后复习了再改成C++

简单选择排序 Simple Selection Sort

排序过程

思路：

• 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
• 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
• 重复上述操作，共进行n-1趟排序后，排序结束
  

算法实现

void Simple_selection_sort(SqList_t* list)
{
	for (int i = 1; i < list->len; ++i)
	{
		int min = i;

		for (int j = i + 1; j <= list->len; ++j)
		{
			if (list->rec[min].key > list->rec[j].key)
			{
				min = j;
			}
		}
		if (min != i)
		{
			list->rec[0] = list->rec[i];
			list->rec[i] = list->rec[min];
			list->rec[min] = list->rec[0];
		}
	}
}

算法评价

T(n)

选择排序需执行$n-1$n−1趟。第$i$i趟排序需要比较$n-i$n−i次

• 比较次数：$\sum_{i=1}^{n-1} (n-i) = \frac {n^2-n}{2}$∑i=1n−1​(n−i)=2n2−n​

若待排记录为从小到大排列(正序)

• 移动次数：$0$0

若待排记录为从大到小排列

• 移动次数：$3(n-1)$3(n−1)

$\therefore T(n)=O(n^2)$∴T(n)=O(n2)

S(n)

$S(n)=O(1)$S(n)=O(1)

是否稳定

• 不稳定

堆排序 Heap Sort

堆

概念

• 堆采用完全二叉树结构

• 使用顺序存储。即按层序存储，所用数组起始单元为1，则结点$i$i的父结点为$\lfloor \frac{i}{2}\rfloor$⌊2i​⌋，左、右孩子为$2i$2i，$2i+1$2i+1

• 最大堆 / 大顶堆 (max heap)：任一结点的值 $\geq$≥ 其子结点的值
  因此最大堆中根结点元素最大
  

• 最小堆 / 小顶堆 (min heap)：任一结点的值 $\leq$≤ 其子结点的值
  因此最小堆中根结点元素最小
  

排序过程

思路：

• 初建堆：将无序序列建成一个堆，则堆顶是关键字最小(或最大) 的记录
• 调整堆：输出堆顶记录后，将剩余的记录重新调整成一个新堆，则可得到剩余记录中的最小值(或最大值)
• 重复执行上一步 ，直到得到一个有序序列

调整堆：筛选

以最小堆为例：

• 将堆顶记录(根)与堆中最后一个记录交换位置
• 然后将根结点值与其左、右孩子进行比较，并与其中小的进行交换
• 重复上述操作，直至叶子结点，将得到新的堆，这个从堆顶至叶子的调整过程称为“筛选”

可以看出，最小堆适合于降序排序，而最大堆适合于升序排序

初建堆

从无序序列的第$\lfloor n/2\rfloor$⌊n/2⌋个元素（即此无序序列对应的完全二叉树的最后一个非叶子结点）起，至第一个元素止，进行反复筛选

算法实现

• 要进行升序排序，因此实现最大堆

void Heap_adjust(SqList_t* list, int root, int len)
{
	int  min_child;

	list->rec[0] = list->rec[root];

	while (root * 2 <= len)
	{
		min_child = root * 2;
		if (min_child + 1 <= len
			&& list->rec[min_child + 1].key > list->rec[min_child].key)
		{
			++min_child;
		}
		if (list->rec[min_child].key > list->rec[0].key)
		{
			list->rec[root] = list->rec[min_child];
			root = min_child;
		}
		else {
			break;
		}
	}
	list->rec[root] = list->rec[0];
}

void Heap_sort(SqList_t* list)
{
	//初建堆
	for (int i = list->len / 2; i >= 1; --i)
	{
		Heap_adjust(list, i, list->len);
	}
	//输出 n-1 次，调整堆 n-2 次 
	for (int i = 0; i < list->len - 1; ++i)
	{
		if(i > 0)
		{ 
			Heap_adjust(list, 1, list->len - i);
		}
		list->rec[0] = list->rec[1];
		list->rec[1] = list->rec[list->len - i];
		list->rec[list->len - i] = list->rec[0];
	}
}

算法评价

T(n)

堆排序的运行时间主要耗费在：

• 初建堆： $\lfloor n/2\rfloor$⌊n/2⌋次筛选
  对深度为$k$k的堆进行筛选时，最多进行$2(k-1)$2(k−1)次关键字比较。由于第$i$i层上的结点数最多为$2^{i-1}$2i−1，以它们为根的二叉树深度为$h-i+1$h−i+1。
  因此，初建堆时最大的比较次数为：
  $\begin{aligned} &\sum_{i=h-1}^1 2^{i-1} \cdot 2(h-i ) \\=& \sum_{i=h-1}^1 2^{i} \cdot (h-i ) \\=& \sum_{j=1}^{h-1} 2^{h-j} \cdot j \end{aligned}$==​i=h−1∑1​2i−1⋅2(h−i)i=h−1∑1​2i⋅(h−i)j=1∑h−1​2h−j⋅j​ $\because 2^{h-1}\leq n \leq 2^h-1$∵2h−1≤n≤2h−1 $\begin{aligned} \therefore &\sum_{j=1}^{h-1} 2^{h-j} \cdot j \leq (2n)\sum_{j=1}^{h-1} 2^{-j} \cdot j \leq 4n \end{aligned}$∴​j=1∑h−1​2h−j⋅j≤(2n)j=1∑h−1​2−j⋅j≤4n​$\therefore T(n)=O(n)$∴T(n)=O(n)

• 调整成新堆： $n-1$n−1 次筛选
  因为$n$n个结点的完全二叉树最大深度为$\lfloor log_2n\rfloor+1$⌊log2​n⌋+1，因此比较次数最多为：
  $\begin{aligned}2(\lfloor log_2(n-1)\rfloor + \lfloor log_2(n-2)\rfloor +...+log_22) < 2n\lfloor log_2n\rfloor \end{aligned}$2(⌊log2​(n−1)⌋+⌊log2​(n−2)⌋+...+log2​2)<2n⌊log2​n⌋​ $\therefore T(n)=O(nlog_2n)$∴T(n)=O(nlog2​n)

综上所述，堆排序即使在最坏的情况下，时间复杂度依然为$O(nlog_2n)$O(nlog2​n)

S(n)

$S(n)=O(1)$S(n)=O(1)

是否稳定

• 不稳定

总结

• 记录数较少的序列，堆排序的优越性并不明显，但对大量的记录来说堆排序是很有效的