接著上一篇文章常用的排序，繼續(xù)說排序，剩下的還有直接插入排序，直接選擇排序和堆排序，默認排序順序仍是遞增排序。廢話不多說了，開始進入正題。

插入排序其實分為：直接插入排序，二分插入排序（或折半插入排序），希爾排序，其基本思想就是：每次將一個待排序的記錄，按其關鍵字的大小插入到前面已經排好序的子表中的適當位置，直到全部記錄插入完成為止。在這里只介紹直接插入排序。

直接插入排序

直接先來代碼好了。

void InsertSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    for (int i = 1; i < n; i++)
    {
        tmp = R[i];
        j = i - 1;
        while(j >= 0 && tmp.key < R[j].key)
        {
            R[j+1] = R[j];
            j--;
        }
        R[j+1] = tmp;
    }
}

此排序的操作過程為：假設有一序列為（6，3，7，5，1，4，2，9），剛開始時i = 1，j = 0，有序區(qū)暫時只有R[0]一個記錄。從6起，從右向左查找，3小于6，將6右移一個位置，j-- 后while條件不滿足了，結束while循環(huán)，將3插入R[0]的位置，此時序列變?yōu)椋?，6，7，5，1，4，2，9），第一趟排序結束。接下來第二趟排序，i = 2，待插入的記錄為R[2] = 7，從6開始從右向左查找。7大于6，while條件不滿足，所以7的位置不變。此時序列變?yōu)椋?，6，7，5，1，4，2，9），第三趟排序...以此類推，直到所有記錄都有序為止。

初始序列：6 3 7 5 1 4 2

i = 1： <b><u>3</u></b> 6 7 5 1 4 2 9
i = 2： 3 6 <b> <u>7</u></b> 5 1 4 2 9
i = 3： 3 <b><u>5</u></b> 6 7 1 4 2 9
i = 4： <b><u>1</u></b> 3 5 6 7 4 2 9
i = 5： 1 3 <b> <u>4</u></b> 5 6 7 2 9
i = 6： 1 <b><u>2</u></b> 3 4 5 6 7 9
i = 7： 1 2 3 4 5 6 7 <b> <u>9</u></b>

選擇排序的基本思想是：每一趟排序是從待排序的記錄中選出關鍵字最小的記錄，順序放在已排好序的記錄序列的末尾，直到全部記錄排序完畢。常用的選擇排序方法有直接選擇排序（或簡單選擇排序）以及 堆排序。

直接選擇排序

void selectSort(RecType R[],int n)
{
    int i,j,k;
    RecType tmp;
    for (int i = 0; i < n - 1; i++)
    {
        k = i;
        for (int j = i + 1; j < n; j++)
            if (R[j].key < R[k].key)
                k = j;
        if (k != i)
        {
            tmp = R[i];
            R[i] = R[k];
            R[k] = tmp;
        }
    }
}               

此排序的操作過程為：還是以序列為（6，3，7，5，1，4，2，9）的例子來說吧。剛開始時 i = 0，假設i = 0這個位置對應的關鍵字是最小的，從i+1開始，在6后面的序列中找到最小的那個記錄，用 k 記下第一趟排序后目前找到的最小的關鍵字所在的位置，判斷 k 是否等于 i，不相等，說明最小值的位置發(fā)生了變化，需要交換下R[i] 和 R[k]，此時序列為（1，3，7，5，6，4，2，9）。接著第二趟排序開始...以此類推，經過n - 1趟排序后，整個序列遞增有序。

初始序列：6 3 7 5 1 4 2 ，排序過程如下所示：

selectionSort.png

堆排序

待續(xù) O(∩_∩)O