一文看懂直接插入排序和希爾排序

要說(shuō)排序算法里面比較簡(jiǎn)單的，我覺得直接插入排序算是一個(gè)。

直接插入排序的原理很簡(jiǎn)單，就是把一個(gè)數(shù)字插入到一個(gè)有序的數(shù)組中。

比如有這么一個(gè)數(shù)組：

1，3，5，7

然后要把 4 插進(jìn)去。

過(guò)程不難，4跟 7 比，7大，把 7 往后移動(dòng)；

4跟 5 比，5大，把 5 往后移動(dòng)；

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

但是問(wèn)題又來(lái)了，去哪找一個(gè)有序的數(shù)組，排序本來(lái)就是沒(méi)有順序的。

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

比如有這么一個(gè)數(shù)組：

6 4 5 3 7

先把 6 當(dāng)作一個(gè)單獨(dú)的數(shù)組，那么它一定是有序的。

把 4 插入到這個(gè)有序的數(shù)組中，先把 4 記下來(lái)，4跟 6 比，6向后移動(dòng)，然后把 4 放到第一個(gè)位置。

4 6 5 3 7

接下來(lái)再把 5 插入到4 6這個(gè)有序的數(shù)組中，過(guò)程一樣。

4 5 6 3 7

循環(huán)下去，最終一定會(huì)得到一個(gè)有序的數(shù)組。

代碼也不難。

#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;


    //隨機(jī)產(chǎn)生數(shù)組
    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;
}

直接插入排序的效率很低，基本上跟冒泡是一個(gè)級(jí)別。 問(wèn)題就出在移動(dòng)的次數(shù)太多。

6 4 5 3 7

比如 3 這個(gè)元素，最終應(yīng)該放在 6 這個(gè)位置上，但是這個(gè)過(guò)程需要跟每個(gè)數(shù)字比較并且向后移動(dòng)。

于是有個(gè)叫做希爾的人就提出了改進(jìn)思路，如果能讓 3 跳著來(lái)，速度就會(huì)提高很多。

后來(lái)就有了希爾排序。

第一步，先選取 2 作為步長(zhǎng)，就是長(zhǎng)度的一半，把原數(shù)組分成了兩個(gè)數(shù)組，一個(gè)是6 5 7，一個(gè)是4 3，對(duì)這兩個(gè)數(shù)組分別做直接插入排序。

6  5  7
 4  3

你會(huì)發(fā)現(xiàn)，這一次 3 直接和 4 交換了位置，一下子跳了兩步。

第二步，步長(zhǎng)再縮減一半，就是1。

其實(shí)就是對(duì)整個(gè)數(shù)組做直接插入排序。

有些同學(xué)可能會(huì)有疑問(wèn)，既然最終也是對(duì)整個(gè)數(shù)組做直接插入排序，為什么不一開始就這樣？

隨著步長(zhǎng)的逐漸的縮減，數(shù)組會(huì)變得基本有序，雖然最后一步也是直接插入排序，但是移動(dòng)的元素會(huì)很少。

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

代碼也只需要做簡(jiǎn)單的修改。

#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;


    //隨機(jī)產(chǎn)生數(shù)組
    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;
}

最后來(lái)試下 5 萬(wàn)個(gè)數(shù)據(jù)排序，兩者的差距肉眼可見。

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#

審核編輯：劉清