8.4 选择排序

8.4.1 简单选择排序

不稳定，第 i 次排序从其余的元素选择最小的与第 i 个元素交换。

比较次数$\frac{n(n-1)}{2}$

8.4.2 堆排序

时间复杂度$O\left( n\log_{2} n\right)$

如何构造初始堆？

（1）先构建堆。

（2）检查所有非终端节点，从后往前，小元素下坠。

void BuildMaxHeap(int *a, int len)
{
    for (int i = len / 2; i > 0; i--)
    {
        HeadAdjust(A, i, len);
    }
}
void HeadAdjust(int *a, int k, int len)
{
    a[0] = a[k];
    for (i = 2 * k; i <= len; i *= 2)
    {
        if (i < len && a[i] < a[i + 1])
            i++;
        if (a[0] >= [i])
            break;
        else
        {
            a[k] = a[i];
            k = i;
        }
    }
    a[k] = a[0];
}

输出堆顶元素后如何让调整新堆？

将最后一个元素移动到堆顶，然后构造初始堆。

void HeapSort(int *a, int len)
{
    BuildMaxHeap(a, len);
    for (int i = len; i > 1; i--)
    {
        Swap(a[i], a[1]);
        HeadAdjust(a, 1, i - 1);
    }
}