要說排序算法里面比較簡單的，我覺得直接插入排序算是一個。

直接插入排序的原理很簡單，就是把一個數字插入到一個有序的數組中。

比如有這么一個數組：

1，3，5，7

然后要把 4 插進去。

過程不難，4跟 7 比，7大，把 7 往后移動；

4跟 5 比，5大，把 5 往后移動；

4跟 3 比，3小，于是直接把4放到第三個位置上。

但是問題又來了，去哪找一個有序的數組，排序本來就是沒有順序的。

于是就有了一個理論，如果一個數組中只有一個元素，那么它一定是有序的。

比如有這么一個數組：

6 4 5 3 7

先把 6 當作一個單獨的數組，那么它一定是有序的。

把 4 插入到這個有序的數組中，先把 4 記下來，4跟 6 比，6向后移動，然后把 4 放到第一個位置。

4 6 5 3 7

接下來再把 5 插入到4 6這個有序的數組中，過程一樣。

4 5 6 3 7

循環下去，最終一定會得到一個有序的數組。

代碼也不難。

#include 
#include 
#include 


#define SIZE     100000


void insert_sort(int *a, int size)
{
    int i, j, num;
    for (i = 1; i < size; i++)
    {   
        num = a[i];
        for (j = i - 1; j >= 0; j--)
        {   
            if (num < a[j])
            {   
                a[j + 1] = a[j];
            }
            else
            {
                break;
            }
        }
        a[j + 1] = num;
    }
}


int main()
{
    int num, arr[SIZE] = {0}, i;


    //隨機產生數組
    srand(time(NULL));
    for (i = 0; i < SIZE; i++)
    {
        arr[i] = rand() % 100;
    }


    insert_sort(arr, SIZE);


    for (i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("
");


    return 0;
}

直接插入排序的效率很低，基本上跟冒泡是一個級別。 問題就出在移動的次數太多。

6 4 5 3 7

比如 3 這個元素，最終應該放在 6 這個位置上，但是這個過程需要跟每個數字比較并且向后移動。

于是有個叫做希爾的人就提出了改進思路，如果能讓 3 跳著來，速度就會提高很多。

后來就有了希爾排序。

第一步，先選取 2 作為步長，就是長度的一半，把原數組分成了兩個數組，一個是6 5 7，一個是4 3，對這兩個數組分別做直接插入排序。

6  5  7
 4  3

你會發現，這一次 3 直接和 4 交換了位置，一下子跳了兩步。

第二步，步長再縮減一半，就是1。

其實就是對整個數組做直接插入排序。

有些同學可能會有疑問，既然最終也是對整個數組做直接插入排序，為什么不一開始就這樣？

隨著步長的逐漸的縮減，數組會變得基本有序，雖然最后一步也是直接插入排序，但是移動的元素會很少。

希爾排序的效率要比直接插入排序高很多。

代碼也只需要做簡單的修改。

#include 
#include 
#include 


#define SIZE     100000


void shell_sort(int *a, int size)
{
    int i, j, num, h;
    for (h = size / 2; h > 0; h /= 2)
    {   
        for (i = h; i < size; i++)
        {   
            num = a[i];
            for (j = i - h; j >= 0; j = j - h)
            {   
                if (num < a[j])
                {
                    a[j + h] = a[j];
                }
                else
                {
                    break;
                }
            }
            a[j + h] = num;
        }
    }
}


int main()
{
    int num, arr[SIZE] = {0}, i;


    //隨機產生數組
    srand(time(NULL));
    for (i = 0; i < SIZE; i++)
    {
        arr[i] = rand() % 100;
    }


    shell_sort(arr, SIZE);


    for (i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("
");


    return 0;
}

最后來試下 5 萬個數據排序，兩者的差距肉眼可見。

root@Turbo:test# time ./insert_sort 


real  0m1.740s
user  0m1.724s
sys  0m0.000s
root@Turbo:test# time ./shell_sort 


real  0m0.008s
user  0m0.004s
sys  0m0.004s
root@Turbo:test#

審核編輯：劉清