C語言中文網 目錄

插入排序算法,C語言插入排序算法詳解

插入排序的算法特別好理解,與我們的日常生活緊密相連,或者說它來源于對日常生活的感悟。插入排序也是用得最多的一種排序方法。但原因不是因為它好理解,而是因為在實際編程中數據往往都是已經排好序的,所以一般都是往排好序的序列中按順序插入一個數據。此時用插入排序就會特別快。

那么插入排序到底是怎樣的呢?比如有十個人從左往右無序地排列,現在要你按身高從低到高排列,你會怎么排?

首先第二個人和第一個人比,如果第二個人比第一個人矮,那么它們互換位置,否則不動,此時前兩個人的順序就排好了;然后第三個人再與前兩個已經排好的比,怎么比?第三個人先站出來,看看前面在哪個位置中自己比左邊的高比右邊的矮,然后就插進去,如果自己與前面的人相比是最高的,那么就不動,此時前三個人的順序就排好了……就這樣一直往后比較。

那么怎么找比左邊高比右邊矮的那個位置呢?因為左邊都是已經排好序的,所以依次與左邊的比,直到遇到一個比他矮的,那么那個位置就是比左邊高比右邊矮的位置。如果沒找到一個比他矮的那么他就是最矮的,那么他就排在最左邊。那么是怎么插入的呢?因為每個與左邊一個一個比較的那個人都是先站出來的,所以他的那個位置是空的。這時在找到比他矮的那個人之前,每比完一個,與他進行比較的那個人就往右挪一個位置,將空依次補上。直到找到比他矮的人,那時比他矮的那個人的前面就空出了一個位置,然后他就可以插進去。所以在程序中要先用一個變量保存這個“站出來的”數。

下面來寫一個插入排序的算法實現從小到大排序。
# include <stdio.h>
int main(void)
{
    int i, j;
    int temp;  //用于存儲站出來的數
    int a[] = {900, 2, 3, -58, 34, 76, 32, 43, 56, -70, 35, -234, 532, 543, 2500};
    int n = sizeof(a) / sizeof(a[0]);  //存放數組a中元素的個數
    for (i=1; i<n; i++)  /*i從1開始, 即從第二個人開始比, 每循環一次比較一輪*/
    {
        temp = a[i]; 
        j = i - 1;  //與它前一個數比較
        while ((j>=0) && (a[j]>temp))  /*與左邊所有人都比完了或找到一個比他矮的為止*/
        {
            a[j+1] = a[j];  //與他比完之后比它高的向右挪一個位置
            --j;  /*最經典的地方, 每次減1, 再與前一個比較, 直到與左邊所有的都比完或比到有一個數小于等于它為止, while循環退出, 此時左邊形成一個新的有序序列*/
        }
        if (j != i-1)  /*這句也很經典, j != i-1說明執行過上面的while, 并且找到位置了, 那么就插進去;如果j = i-1, 則說明沒有執行過while, 說明他和左邊的相比是最高的, 則不用換位置*/
        {
            a[j+1] = temp;  /*之所以j要加1是因為while在退出之前又執行了一次--j*/
        }
    }
    for (i=0; i <15; ++i)
    {
        printf("%d\x20", a[i]);
    }
    printf("\n");
    return 0;   
}
輸出結果是:
-234 -70 -58 2 3 32 34 35 43 56 76 532 543 900 2500

總結

冒泡排序是從左往右比,而插入排序是從右往左比,但也是一輪一輪地比較。原序列中從左邊第二個數開始,每輪比較一個數。每個數依次與它左邊的所有數相比較,左邊的都是已經排好的序列,該數與這些排好的序列逐個比較,然后插入其中,形成一個新的排好的序列。

從程序中也可以看出,如果是將一個數據插入已經排好的序列中,使用插入排序無疑是最好的選擇。此時計算量只不過是冒泡排序的一輪比較而已。比如向序列“1 3 4 5 7 9 11 13 20”插入一個 6,用插入排序就非常簡單了。程序如下:
# include <stdio.h>
int main(void)
{
    int a[10] = {1, 3, 4, 5, 7, 9, 11, 13, 20};
    int i = 8;  //存儲數組有效數據的最大下標
    int data = 0;  //存儲要插進來的數
    printf("請輸入要插進來的數:");
    scanf("%d", &data);
    while ((i>=0) && (a[i]>data))  /*找到data應該插入的位置, 并把那個位置空出來*/
    {
        a[i+1] = a[i];
        --i;
    }
    a[i+1] = data;  //將data插入那個位置
    for (i=0; i<10; ++i)
    {
        printf("%d\x20", a[i]);
    }
    printf("\n");
    return 0;   
}
輸出結果是:
請輸入要插進來的數:6
1 3 4 5 6 7 9 11 13 20

需要注意的是,前面的程序中數組的長度都沒有手動指定,而上面這個程序是手動指定了數組的長度為 10。這是為什么?

這是因為,如果不手動給定還是寫成“int a[]={1,3,4,5,7,9,11,13,20};”這種形式的話,那么系統就會根據初始化數據的個數認為該數組的長度為 9。但是現在要往該數組中插入一個元素,那么數組的長度至少是 10,不然插入數據后,數組的最后一個元素就會向后覆蓋一個 int 型的未分配給它的內存空間。

所以為了避免這種情況的發生,就只能手動指定數組的長度。但是這樣的話就意味著不能再通過 sizeof(a)/sizeof(a[0]) 來計算數組中存放的有意義的數據的長度,因為 sizeof(a)/sizeof(a[0]) 計算的是數組的總長度。這也就意味著只能通過手動的方式指定數組中存放有意義的數據的元素的最大下標 i。

綜上所述,這種情況就需要程序員自己手動維護數組的長度。這也從某一方面體現出了數組的缺陷,即它無法動態地擴充長度。動態數組和鏈表就不存在數組的這個缺陷,這兩種結構后續會講。

精美而實用的網站,提供C語言、C++、STL、Linux、Shell、Java、Go語言等教程,以及socket、GCC、vi、Swing、設計模式、JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo
极速pk10开户