直接插入排序:簡介,引言,基本思想,算法思想,排序方法,哨兵的作用,過程實例,算法

直接插入排序（Straight Insertion Sort）是一種最簡單的排序方法，其基本操作是將一條記錄插入到已排好的有序表中，從而得到一個新的、記錄數量增1的有序表。

基本介紹

中文名：直接插入排序
外文名：Straight Insertion Sort
類型：插入排序
時間複雜度：O(n^2)
空間複雜度：O(1)
穩定性：穩定

簡介,引言,基本思想,算法思想,排序方法,哨兵的作用,過程實例,算法描述,

簡介

引言

在日常生活中，經常碰到這樣一類排序問題：把新的數據插入到已經排好的數據列中。例如：一組從小到大排好順序的數據列{1,2,3,4,5,6,7,9,10}，通常稱之為有序列，我們用序號1,2,3，…表示數據的位置，欲把一個新的數據8插入到上述序列中。

完成這個工作的步驟：

①確定數據“8”在原有序列中應該占有的位置序號。數據“8”所處的位置應滿足小於或等於該位置右邊所有的數據，大於其左邊位置上所有的數據。

②將這個位置空出來，將數據“8”插進去。

直接插入排序(straight insertion sort)的做法是：

每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。

第一趟比較前兩個數，然後把第二個數按大小插入到有序表中；第二趟把第三個數據與前兩個數從後向前掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以後就完成了整個排序過程。

直接插入排序是由兩層嵌套循環組成的。外層循環標識並決定待比較的數值。內層循環為待比較數值確定其最終位置。直接插入排序是將待比較的數值與它的前一個數值進行比較，所以外層循環是從第二個數值開始的。當前一數值比待比較數值大的情況下繼續循環比較，直到找到比待比較數值小的並將待比較數值置入其後一位置，結束該次循環。

基本思想

每一趟將一個待排序的記錄，按其關鍵字的大小插入到已經排好序的一組記錄的適當位置上，直到所有待排序記錄全部插入為止。

待排序記錄 R1，R2，… ，Rn–1, Rn

第一步：R1

第二步：(R1 ), R2

第三步：(R1 , R2), R3

……

第 j 步：(R1，R2，… ，Rj–1), Rj

……

第 n 步: (R1，R2，… ，Rn–1), Rn．

例：j=5

原有序表中關鍵字比Rj大的記錄數：dj

比較次數：dj+1 移動次數： dj+2

算法思想

算法 InsertSort (R,n)

FOR j=2 TO n DO

( //每次將Rj插入到有序表R1，…，Rj–1中

K←Kj. R←Rj. i←j-1.

WHILE (i>0) AND (Ki>K) DO

(Ri+1←Ri.

i←i-1.)

Ri+1←R.

)

算法InsertSortA( R, s, e )

//引入虛擬記錄,Ks-1≤min{Ki| s≤i≤e}

ISA1 [逐一排序]

FOR j=s+1 TO e DO

( i←j-1．K←Kj. R←Rj .

WHILE K<Ki DO

( Ri+1←Ri ．

i←i-1 ．)

Ri+1←R ．

)

ISA1 [逐一排序]

FOR j=s+1 TO e DO

( i←j-1．K←Kj . R←Rj .

WHILE K<Ki DO

( Ri+1←Ri ．i←i-l ) ．

Ri+1←R )

直接插入排序的時間複雜度為 O(n2)。

排序方法

1．簡單方法

首先在當前有序區R[1..i-1]中查找R[i]的正確插入位置k(1≤k≤i-1)；然後將R[k．．i-1]中的記錄均後移一個位置，騰出k位置上的空間插入R[i]。

注意：若R[i]的關鍵字大於等於R[1．．i-1]中所有記錄的關鍵字，則R[i]就是插入原位置。

2．改進的方法

一種查找比較操作和記錄移動操作交替地進行的方法。具體做法：

將待插入記錄R[i]的關鍵字從右向左依次與有序區中記錄R[j](j=i-1，i-2，…，1)的關鍵字進行比較：

① 若R[j]的關鍵字大於R[i]的關鍵字，則將R[j]後移一個位置；

②若R[j]的關鍵字小於或等於R[i]的關鍵字，則查找過程結束，j+1即為R[i]的插入位置。

關鍵字比R[i]的關鍵字大的記錄均已後移，所以j+1的位置已經騰空，只要將R[i]直接插入此位置即可完成一趟直接插入排序。

哨兵的作用

算法中引進的附加記錄R[0]稱監視哨或哨兵(Sentinel)。

哨兵有兩個作用：

① 進人查找(插入位置)循環之前，它保存了R[i]的副本，使不致於因記錄後移而丟失R[i]的內容；

② 它的主要作用是：在查找循環中"監視"下標變數j是否越界。一旦越界(即j=0)，因為R[0].可以和自己比較，循環判定條件不成立使得查找循環結束，從而避免了在該循環內的每一次均要檢測j是否越界(即省略了循環判定條件"j>=1")。

注意：

① 實際上，一切為簡化邊界條件而引入的附加結點(元素)均可稱為哨兵。

【例】單鍊表中的頭結點實際上是一個哨兵

② 引入哨兵後使得測試查找循環條件的時間大約減少了一半，所以對於記錄數較大的檔案節約的時間就相當可觀。對於類似於排序這樣使用頻率非常高的算法，要儘可能地減少其運行時間。所以不能把上述算法中的哨兵視為雕蟲小技，而應該深刻理解並掌握這種技巧。

過程實例

例：

原有序表：(9 15 23 28 37) 20

找插入位置 : (9 15 ^ 23 28 37) 20

新有序表: (9 15 20 23 28 37)

設待排序的檔案有8個記錄，其關鍵字分別為：49，38，65，97，76，13，27，49。為了區別兩個相同的關鍵字49，後一個49的下方加了一下劃線以示區別。其排序過程見

算法描述

Python 代碼實現

def insertSort(relist):    len_ = len(relist)    for i in range(1,len_):          for j in range(i):            if relist[i] < relist[j]:                relist.insert(j,relist[i])  # 首先碰到第一個比自己大的數字，趕緊剎車，停在那，所以選擇insert                relist.pop(i+1)  # 因為前面的insert操作，所以後面位數+1，這個位置的數已經insert到前面去了，所以pop彈出                break    return relist

C/C++代碼實現直接插入排序

#include<iostream>using namespace std;int main(){    int a[]={98,76,109,34,67,190,80,12,14,89,1};    int k=sizeof(a)/sizeof(a[0]);    int i,j;    for(i=1;i<k;i++)//循環從第2個元素開始    {        if(a[i]<a[i-1])        {            int temp=a[i];            for(j=i-1;j>=0 && a[j]>temp;j--)            {                a[j+1]=a[j];            }            a[j+1]=temp;//此處就是a[j+1]=temp;        }    }    for(int f=0;f<k;f++)    {        cout<<a[f]<<"  ";    }    return 0;}

Objective-C實現

+(void)sort:(NSMutableArray*)array{inti,y;for(i=0;i<[arraycount]-1;i++){//前面一位大於後面一位if([[arrayobjectAtIndex:i+1]intValue]<[[arrayobjectAtIndex:i]intValue]){//保存後面一位NSString*temp=[arrayobjectAtIndex:i+1];//從後一位開始for(y=i+1;y>0&&[[arrayobjectAtIndex:y-1]intValue]>[tempintValue];y--){[arrayexchangeObjectAtIndex:y-1withObjectAtIndex:y];}//[arrayremoveObjectAtIndex:y];//[arrayinsertObject:tempatIndex:y];}}}

JAVA實現

public class InsertSort{        public void insertSort(int[] array){        for(int i=1;i<array.length;i++)//第0位獨自作為有序數列，從第1位開始向後遍歷        {            if(array[i]<array[i-1])//0~i-1位為有序，若第i位小於i-1位，繼續尋位並插入，否則認為0~i位也是有序的，忽略此次循環，相當於continue            {                int temp=array[i];//保存第i位的值                int k = i - 1;                for(int j=k;j>=0 && temp<array[j];j--)//從第i-1位向前遍歷並移位，直至找到小於第i位值停止                {                    array[j+1]=array[j];                    k--;                }                array[k+1]=temp;//插入第i位的值            }        }     }        public static void printArray(int[] array) {          for (int i = 0; i < array.length; i++) {               System.out.print(array[i]);               if (i != array.length - 1) {                System.out.print(",");               }          }     }    }

C#實現

public void Action(int[]array){    for(int i=1; i<array.Length; i++)    {        if(array[i]<array[i-1])        {            int temp=array[i];            int j=0;            for(j=i-1;j>=0 && temp<array[j];j--)            {                array[j+1]=array[j];            }            array[j+1]=temp;        }    }}    PHP實現function Insert_Sort($myarr){    $temp=0;    for($i=1;$i<count($myarr);$i++)    {        $temp=$myarr[$i];        $j=$i-1;        while($j>=0&&$temp<$myarr[$j])        {            $myarr[$j+1]=$myarr[$j];            $j--;        }        $myarr[$j+1]=$temp;    }}print_r($myarr);echo '<hr>';Insert_Sort($myarr);

直接插入排序