RodneyX

選擇排序的基本思想是，在待排序序列A[p...n-1]中選擇一個最值加入到A[0...p-1]中，形成更長的有序序列A[0...p]，初始時有序表僅有一個元素，對于表長為n的表，經過n-1次選擇即可排序完成，針對選擇最值方式的不同，有兩種基本的算法，一個是簡單選擇排序（暴力選擇），一個是堆排序（基于數據結構堆）

對于簡單選擇排序，實現方式非常簡單，有如下實現

#include <limits.h>

void simple_Select(int A[], int length)
{
    for (int i = 0; i < length - 1; ++i)
    {
        int min_index = -1;
        int min_val = INT_MAX;
        for (int j = length - 1; j >= i; --j)
        {
            if (A[j] < min_val)
            {
                min_val = A[j];
                min_index = j;
            }
        }
        A[min_index] = A[i];
        A[i] = min_val;
    }
}

定義堆具有如下性質：

1. 是完全二叉樹

2. 所有分支節點的值大于（小于）其左、右孩子（若存在）的值稱之為大（小）頂堆

調整堆的方法是從上向下篩選，也就是說，若分支節點不滿足堆的定義，就將這個結點與孩子節點交換，其中若為大頂堆要求這個孩子節點具有最大值，小頂堆則是取具有最小值的孩子結點交換，如此往復直到這個向下篩選的結點滿足堆定義

初始化一個堆則從最后一個分支結點開始到完全二叉樹根節點，依次調整即可

而堆排序就是先將待排序序列初始化為堆，然后交換第一個和最后一個結點（刪除堆頂元素），此時堆規模減一，然后重新調整，對于表長為n的無序表只需執行n-1次交換即可完成排序

于是我們有如下實現

/*完全二叉樹下標與結點父子關系的一個簡單例子
           0
         /   \
        1      2
       /  \   /  \
      3    4  5   6

 (1 - 1) / 2 = 0  (2 - 1) / 2 = 0
 (3 - 1) / 2 = 1  (4 - 1) / 2 = 1
 (5 - 1) / 2 = 2  (6 - 1) / 2 = 2

 parent = (pos - 1) / 2
 lchild = 2 * i + 1, rchild = lchild + 1
*/

// cannot be called by user
void _adjust_MaxHeap(int A[], int pos, int length)
{
    int adj_val = A[pos];
    int i = pos, k;
    while (i < length)  //事實上只要輸入合法，是不會出現越界訪問的，i的有效性由while循環內if語句保證，因此這里其實可以不用這么寫，直接寫個true也行
    {
        int adjusted = 0;
        k = i * 2 + 1;
        if (k + 1 < length && A[k] < A[k + 1])
            ++k;
        if (k < length && adj_val < A[k])
        {
            A[i] = A[k];
            i = k;
            adjusted = 1;
        }  //這里可以不用adjusted變量，只需要else語句塊執行break即可，因為沒有執行if語句塊表明調整完畢，直接退出循環
        if (!adjusted)
        {
            A[i] = adj_val;
            break;
        }
    }
}

// cannot be called by user
void _create_MaxHeap(int A[], int length)  //建堆從最后一個分支節點開始調整
{
    for (int i = 0; i <= (length - 2) / 2; ++i)
        _adjust_MaxHeap(A, (length - 2) / 2 - i, length);
}

void heap_Sort(int A[], int length)
{
    _create_MaxHeap(A, length);
    for (int i = length - 1; i > 0; --i)
    {
        int swap_val = A[i];
        A[i] = A[0];
        A[0] = swap_val;
        _adjust_MaxHeap(A, 0, i);  //注意參數傳遞，第二個參數是堆數組的首元素下標，第二個參數是堆的規模
    }
}

最后，堆排序的時間復雜度是O(nlogn)，這是因為建堆是線性時間，排序時每次篩選最小值是對數時間，會篩選n-1次（假設表長為n）

另外，堆的插入是插到堆尾，然后自下往上調整（不是向下篩選！）