插入排序法

插入排序法 所謂插入排序法乃是將一個數目插入該占據的位置。 假設我們輸入的是 “5，1，4，2，3” 我們從第二個數字開始，這個數字是1，我們的任務只要看看1有沒有正確的位置，我們的做法是和這個數字左邊的數字來比，因此我們比較1和5，1比5小，所以我們就交換1和5，原來的排列就變成了“1，5，4，2，3 ” 接下來，我們看第3個數字有沒有在正確的位置。這個數字是4，它的左邊數字是5，4比5小，所以我們將4和5交換，排列變成了 “1，4，5，2，3 "我們必須繼續看4有沒有在正確的位置，4的左邊是1，1比4小，4就維持不動了。 再來看第四個數字，這個數字是2，我們將2和它左邊的數字相比，都比2大，所以就將2一路往左移動，一直移到2的左邊是1，這時候排序變成了 “1，2，4，5，3 ” 最後，我們檢查第五個數字，這個數字是3，3必須往左移，一直移到3的左邊是2為止，所以我們的排列就變成了 “1，2，3，4，5 ”排序因此完成了。 所謂插入排序法，就是檢查第i個數字，如果在它的左邊的數字比它大，進行交換，這個動作一直繼續下去，直到這個數字的左邊數字比它還要小，就可以停止了。插入排序法主要的迴圈有兩個變數：i和j，每一次執行這個迴圈，就會將第i個數字放到左邊恰當的位置去。

基本思想

輸入一個元素，檢查數組列表中的每個元素，將其插入到一個已經排好序的數列中的適當位置，使數列依然有序，當最後一個元素放入合適位置時，該數組排序完畢。

程式描述

例1：輸入一個數，插入一個各元素已經按照升序排列的數組中，插入後使數組中元素仍然是按照升序排列的。思想：把欲插入的數與數組中各數逐個比較， 當找到第一個比插入數大的元素i時，該元素之前即為插入位置。然後從數組最後一個元素開始到該元素為止，逐個後移一個單元。最後把插入數賦予元素a[i]即可。如果被插入數比所有的元素值都小則插入最前位置。

C語言：

例2：輸入一個數，插入一個各元素已經按照降序排列的數組中，插入後使數組中元素仍然是按照降序排列的。思想：把欲插入的數與數組中各數逐個比較， 當找到第一個比插入數小的元素i時。如果被插入數比所有的元素值都小則插入最後位置。

C語言：