顺便聊一下排序——选择排序

选择排序


简单选择排序

基本思想

  • 每一趟在后面 n-i +1个中选出关键码最小的对象, 作为有序序列的第 i 个记录

算法实现

void SelectSort(SqList &L){
	// 对记录序列R[1.. L.length]作简单选择排序
	for(i = 1; i <= L.length; i++){
		// 选择第 i 小的记录,并交换到位
		k = i;
		for(j = i + 1; j <= L.length; ++j)
			if(L.r[j].key < L.r[k].key) k = j;
		if(k != i) Swap(L.r[i], L.r[k]);  // 交换
	}
}

算法分析

  • 时间复杂度:O(n^2)
    – 移动次数:
    – 最好情况:0
    – 最坏情况:3(n-1)
  • 空间复杂度: O(1)
  • 稳定性: 稳定

树形选择排序

基本思想

  • 取得 n 个对象的关键码,进行两两比较,得到 n/2 个比较的优胜者(关键码小者),作为第一步比较的结果保留下来。
  • 这 n/2 个对象再进行关键码的两两比较,…,如此重复,直到选出一个关键码最小的对象为止。

算法分析

  • 含有n个叶子节点的完全二叉树的深度为log2 n+1,则选择排序的每一趟都需作log2n次比较,排序的时间复杂度O(nlog2n)
  • 需要辅助存储空间较多(n-1),和最大值作多余的比较等等。

改进:简单选择排序没有利用上次选择的结果,是造成速度满的重要原因。如果,能够加以改进,将会提高排序的速度。


堆排序

  • 堆:把待排序的数据元素存放在数组中r1…n,把r看成是一棵完全二叉树,每个结点表示一个记录。ri结点的左孩子是r2i,右孩子是r2i+1。
  • ri.key<=r2i.key,并且 ri.key<=r2i+1.key,则称此完全二叉树为堆。(小根堆)
  • ri.key>=r2i.key,并且 ri.key>=r2i+1.key,则称此完全二叉树为堆。(大根堆)
在这里插入图片描述

基本思想

  • 将无序序列建成一个堆
  • 输出堆顶的最小(大)值
  • 使剩余的n-1个元素又调整成一个堆,则可得到n个元素的次小值
  • 重复执行,得到一个有序序列

无序序列建成堆

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

如何在输出堆顶元素后调整,使之成为新堆?

  • 输出堆顶元素后,以堆中最后一个元素替代之
  • 将根结点与左、右子树根结点比较,并与小者交换
  • 重复直至叶子结点,得到新的堆
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

算法实现

void HeapAdjust(HeapType &H, int s, int m){
	// 已知 H.r [s..m]中记录的关键字除 H.r [s] 之外均
    // 满足堆的特征,本函数自上而下调整 H.r [s] 的
    // 关键字,使 H.r [s..m] 也成为一个大顶堆。
    rc = H.r[s];  // 暂存 H.r [s]
    for(j = 2 * s; j <= m; j *= 2){
    	 // j 初值指向左孩子
    	// 自上而下的筛选过程;
    	if(j < m && H.r[j].key < H.r[j + 1].key) ++j;
    	// 左/右“子树根”之间先进行相互比较
        // 令 j 指示关键字较大记录的位置
        if ( rc.key >= H.r[j].key )  break; 
        // 再作“根”和“子树根”之间的比较,
        // 若“>=”成立,则说明已找到 rc 的插
        // 入位置 s ,不需要继续往下调整
        H.r[s] = H.r[j];   s = j;    
        // 否则记录上移,尚需继续往下调整

    }
    H.r[s] = rc;  // 将调整前的堆顶记录插入到 s 位置
}

void HeapSort ( HeapType &H ) {
	// 对顺序表 H 进行堆排序
	for(i = H.length / 2; i > 0; --i)
		HeapAdjust(H, i, H.length);  // 建大顶堆
	for(i = H.length; i > 1; --i){
		Swap(H.r[1], H.r[i])           
		// 将堆顶记录和当前未经排序子序列
		// H.r[1..i]中最后一个记录相互交换
		HeapAdjust(H, 1, i-1);  // 将H.r[1...i-1]重新调整为大顶堆
	}
}

算法分析

  • 时间效率:O(nlog2n)
  • 空间效率:O(1)
  • 稳定性:不稳定适用于n 较大的情况
正文完