"啃下"插入排序

插入排序法基本原理

　　插入排序法較冒泡排序法和選擇排序法更貼近生活，應該來說理解起來更快。如果你現在能夠得到一副麻將，請把裡面的“一萬”到“六萬”拿出來，打亂順序，再重新排好，就像打麻將開始那樣。是否需要拿出某個麻將拿出來再插入其它麻將之間？這就是插入排序了。不過電腦沒有你那麼聰明，你只要小小幾步就可以將麻將排序好，而電腦還要一個一個地比較，但是，它超快的速度使你根本不知道它的笨拙！同樣，你也可以用撲克牌來試試，但是，這不是整個排序演算法的重點，重點要看下麵這幅圖，如果不理解，就看文章末尾附的《演算法導論》中的圖（原數組(int []){5,6,3,2,1,4} ，每個數組都是排列好之後的，插入的元素就是沒有排列好之前i所指的元素）：

　　array[i]指向數組第2~最後一個元素，我們用array[j]表示第0~i之前的最後一個元素，通過依次比較array[i]與array[j],array[j - 1],...直到比較到比它小的元素。因為終止比較時，array[j]指向一個比要插入的元素小的元素，而array[j + 1]和array[j + 2]是內容相同的元素，因此，我們要把array[i]插入到array[j + 1]。

　　再來結合上圖看代碼（仔細分析，認真理解）：

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

int main(int argc, char * argv[]){
    int i, j, temp, array[SIZE] = {5,1,8,9,4,6,3,2,7,0};
    
    for(i = 1; i < SIZE; i++){ //排序開始,把i初值定為數組第二個元素
        temp = array[i]; //保存這個元素,然後方便比較和排序
        for(j = i - 1; j >= 0 && array[j] > temp; j--)
        //j最初表示i的前一個元素，通過與array[i]大小後，找到一個可插入的位置array[j + 1]
            array[j + 1] = array[j];//大的元素向後移，關鍵！
        array[j + 1] = temp; //插入！！！
    }
    
    for(i = 0; i < SIZE; i++)
        printf("%-5d",array[i]);
        
    getch();
    return 0;
}

　　這裡需要註意的是，通過上圖觀察到array[0]~array[i]是已經排序好的數組，我們稱它為子數組，將array[i]後面的元素依次插入子數組直到沒有元素可以插入，這個子數組就是整個數組，排序完成。

　　有些地方出現的代碼和上面的代碼可能會不同，第二個迴圈我們用的是for而不是while。因為冒泡，選擇，排序這樣簡單的排序演算法都可以用一個for迴圈嵌套另一個for迴圈表示，為了方便記憶，我使用了前者。這裡給出第二個迴圈用的是while的代碼：

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

int main(int argc, char * argv[]){
    int i, j, temp, array[SIZE] = {5,1,8,9,4,6,3,2,7,0};
    
    for(i = 1; i < SIZE; i++){ //道理是一樣的
        j = i - 1;
        temp = array[i];
        while(j >= 0 && array[j] > temp){
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp; 
    }
    
    for(i = 0; i < SIZE; i++)
        printf("%-5d",array[i]);
        
    getch();
    return 0;
}

　　如果不理解，請照著代碼把麻將或撲克牌排序幾遍！

運行結果：

附：演算法導論對插入排序法的介紹