欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-04 09:52:34
...

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

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

简单选择排序 Simple Selection Sort

排序过程

思路:

  • 首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换
  • 再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换
  • 重复上述操作,共进行n-1趟排序后,排序结束
    内部排序(四):选择排序 Selection Sorting (简单选择排序、堆排序)

算法实现

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)

选择排序需执行n1n-1趟。第ii趟排序需要比较nin-i

  • 比较次数:i=1n1(ni)=n2n2\sum_{i=1}^{n-1} (n-i) = \frac {n^2-n}{2}

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

  • 移动次数:00

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

  • 移动次数:3(n1)3(n-1)

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

S(n)

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

是否稳定

  • 不稳定

堆排序 Heap Sort

概念

  • 堆采用完全二叉树结构

  • 使用顺序存储。即按层序存储,所用数组起始单元为1,则结点ii的父结点为i2\lfloor \frac{i}{2}\rfloor,左、右孩子为2i2i2i+12i+1

  • 最大堆 / 大顶堆 (max heap):任一结点的值 \geq 其子结点的值
    因此最大堆中根结点元素最大
    内部排序(四):选择排序 Selection Sorting (简单选择排序、堆排序)

  • 最小堆 / 小顶堆 (min heap):任一结点的值 \leq 其子结点的值
    因此最小堆中根结点元素最小
    内部排序(四):选择排序 Selection Sorting (简单选择排序、堆排序)

排序过程

思路:

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

调整堆:筛选

以最小堆为例:

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

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

初建堆

从无序序列的第n/2\lfloor n/2\rfloor个元素(即此无序序列对应的完全二叉树的最后一个非叶子结点)起,至第一个元素止,进行反复筛选
内部排序(四):选择排序 Selection Sorting (简单选择排序、堆排序)

算法实现

  • 要进行升序排序,因此实现最大堆
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)

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

  • 初建堆: n/2\lfloor n/2\rfloor次筛选
    对深度为kk的堆进行筛选时,最多进行2(k1)2(k-1)次关键字比较。由于第ii层上的结点数最多为2i12^{i-1},以它们为根的二叉树深度为hi+1h-i+1
    因此,初建堆时最大的比较次数为:
    i=h112i12(hi)=i=h112i(hi)=j=1h12hjj\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} 2h1n2h1\because 2^{h-1}\leq n \leq 2^h-1 j=1h12hjj(2n)j=1h12jj4n\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}T(n)=O(n)\therefore T(n)=O(n)

  • 调整成新堆: n1n-1 次筛选
    因为nn个结点的完全二叉树最大深度为log2n+1\lfloor log_2n\rfloor+1,因此比较次数最多为:
    2(log2(n1)+log2(n2)+...+log22)<2nlog2n\begin{aligned}2(\lfloor log_2(n-1)\rfloor + \lfloor log_2(n-2)\rfloor +...+log_22) < 2n\lfloor log_2n\rfloor \end{aligned} T(n)=O(nlog2n)\therefore T(n)=O(nlog_2n)

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

S(n)

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

是否稳定

  • 不稳定

总结

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