8.4 选择排序

一、简单选择排序
基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置
基本操作：
①首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
②再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
③重复上述操作，共进行n-1趟排序后，排序结束
算法：
void SelectSort(SqList &K){
for(i=1;ik=i
for(j=i+1;j<=L.length;j++)
if(L.r[j].keyif(k!=i) L.r[i]←→L.r[k]; //交换
}
}
时间复杂度：
记录移动次数：0
最坏情况：3(n-1)
比较次数：无论待排序列处于什么状态，选择排序所需进行的“比较”次数都相同 n(n-1)/2
算法稳定性：简单选择排序是不稳定排序
二、堆排序

从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于（大于）它的孩子结点
堆排序：若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列又建成一个堆，则得到n个元素的次小值（次大值）……如此反复，便能得到一个有序序列，这个过程称之为堆排序
问题一：如何在输出堆顶元素后，调整剩余元素为一个新的堆？
小根堆：①输出堆顶元素之后，以堆中最后一个元素代替之
②然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换
③重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”
问题二：如何由一个无序序列建成一个堆？
①单结点的二叉树是堆
②在完全二叉树所有以叶子结点为根的子树是堆
③只需将以序号为n/2,n/2-1, ……, 1的结点为根的子树均调整为堆即可，即对应由n个元素组成的无序序列，“筛选”只需从第n/2个元素开始
算法性能分析：
（1）初始堆化所需时间不超过O(n)
（2）排序阶段（不含初始堆化）
①一次重新堆化所需时间不超过O(logn)
②n-1次循环所需时间不超过O(nlogn)
堆排序的时间主要耗费在建初始堆和调整新堆时进行的反复筛选上。堆排序在最坏情况下，其时间复杂度也为O(nlog2n)，这是堆排序的最大优点。无论堆排序列中的记录是正序还是逆序排列，都不会使堆序处于“最好”或“最坏”的状态。另外，堆排序仅需一个记录大小供交换用的辅助存储空间，然而堆排序是一种不稳定的排序方法