插入排序法

插入排序法 所謂插入排序法乃是將一個數目插入該占據的位置。

假設我們輸入的是 “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個數字放到左邊恰當的位置去。

基本介紹

• 中文名：插入排序法
• 領域：計算機
• 套用：數列排序
• 釋義：將一個數目插入該占據的位置

基本思想

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

程式描述

 function insertSort(&$arr){        for ($i=1; $i <count($arr) ; $i++) {            $insertValue=$arr[$i];            $insertKey=$i-1;             while ( $insertkey>=0 && $insertValue<$arr[$insertkey]) {                $arr[$insertKey+1]=$arr[$insertKey];                                $insertkey--;           }           $arr[$insertkey+1]=$insertValue;        }    }內容擴充 內容擴充 

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

C語言：

#include "stdio.h"void main(){    int    m, i, j;    int    a[11] = { 2, 6, 7, 9, 13, 16, 19, 21, 25, 29 }; /* 由於後面有插入1個元素的操作，故數組長度定為11（雖然數組中只有10個元素） */    scanf( "%d", &m );    for ( i = 0; i < 10; i++ )        if ( m < a[i] )            break;    {        for ( j = 9; j >= i; j-- )            a[j + 1] = a[j];    }    a[i] = m;    for ( i = 0; i < 11; i++ )        printf( "%d\t", a[i] );}

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

C語言：

#include <stdio.h>void main(){    int    i, j, p, q, s, n;    int    a[11] = { 162, 127, 105, 87, 68, 54, 28, 18, 6, 3 };    printf( "input number:\n" );    scanf( "%d", &n );    for ( i = 0; i < 10; i++ )        if ( n > a[i] )            break;    {        for ( s = 9; s >= i; s-- )            a[s + 1] = a[s];    }    a[i] = n;    for ( i = 0; i <= 10; i++ )        printf( "%d ", a[i] );    printf( "\n" );}/*eg.3 * 使用插入排序對一個隨機序列進行排序*/void charupx( int before[], int m )                             /* 獲取一個數組，m表示它的元素個數 */{    int varout, varin, temp;    for ( varout = 1; varout < m; varout++ )    {        temp    = before[varout];                       /* 這是目標數（假設的） */        varin    = varout - 1 ；             while ( varin >= 0 && temp < before[varin] )        {            before[varin + 1] = before[varin];      /* 所有數組下標向後一個，值不變 */            varin--;                                /*看前一個數是否還要移動 */        }        before[varin + 1] = temp;                       /* 插入 */    }}