8.4 数据结构——选择排序

8.4.1 简单选择排序

基本思想：在待排序的数据中选出最大（小）的元素放在其开始的位置。

基本操作：

（1）首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个交换；

（2）再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个交换；

（3）重复上述操作，共进行n-1趟排序后，排序结束。

简单选择排序算法：

void Select_Sort(SQList *L)
{
    int k;
    for (int i = 1; i < L->length; i++)
    {
        k = i;
        for (int j = i+1; j <= L->length; j++)
        {
            if (L->r[j].key < L->r[k].key)
            {
                k = j;
            }
        }
        if (k != i)
        {
            RedType tmp = L->r[i];
            L->r[i] = L->r[k];
            L->r[k] = tmp;
        }
    }
}

8.4.2 堆排序

堆的定义：若n个元素的序列{a1,a2,...,an}满足：

则分别称该序列{a1,a2,...,an} 为小根堆和大根堆。

从堆的定义可以看出：堆使之是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于（大于）它的孩子结点。

堆排序：若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重新建立一个堆，则得到n个元素的次小值（次大值）……如此重复，使能得到一个有序序列，这个过程称之为堆排序。

堆的调整：

如何在输出堆顶元素后，调整剩余元素成为新的堆？

（1）输出堆顶元素后，以堆中最后一个元素代替之；

（2）然后将根结点值与左、右子树的根结点进行比较，并与其中最小值进行交换；

（3）重复上述操作，直至叶子结点，将得到新的堆，成这个从堆顶至叶子的调整过程称为“筛选”。

如何建立堆？

例：{49，38，65，97，76，13，27，49}