評論(0

直接插入排序

標籤:排序

1作法

直接插入排序(straight insertion sort)的作法是:
每次從無序表中取出第一個元素,把它插入到有序表的合適位置,使有序表仍然有序。
第一趟比較前兩個數,然後把第二個數按大小插入到有序表中; 第二趟把第三個數據與前兩個數從前向後掃描,把第三個數按大小插入到有序表中;依次進行下去,進行了(n-1)趟掃描以後就完成了整個排序過程。
直接插入排序屬於穩定的排序,最壞時間複雜性為O(n^2),空間複雜度為O(1)。
直接插入排序是由兩層嵌套循環組成的。外層循環標識並決定待比較的數值。內層循環為待比較數值確定其最終位置。直接插入排序是將待比較的數值與它的前一個數值進行比較,所以外層循環是從第二個數值開始的。當前一數值比待比較數值大的情況下繼續循環比較,直到找到比待比較數值小的並將待比較數值置入其後一位置,結束該次循環。
值得注意的是,我們必需用一個存儲空間來保存當前待比較的數值,因為當一趟比較完成時,我們要將待比較數值置入比它小的數值的后一位 插入排序類似玩牌時整理手中紙牌的過程。插入排序的基本方法是:每步將一個待排序的記錄按其關鍵字的大小插到前面已經排序的序列中的適當位置,直到全部記錄插入完畢為止。

2序列

初始序列:
i=1 [46] 58 15 45 90 18 10 62
i=2 [46 58] 15 45 90 18 10 62
┌——┘
i=3 [15 46 58] 45 90 18 10 62
┌——┘
i=4 [15 45 46 58] 90 18 10 62
i=5 [15 45 46 58 90] 18 10 62
┌—————┘
i=6 [15 18 45 46 58 90] 10 62
┌————————┘
i=7 [10 15 18 45 46 5890] 62
┌—┘
i=8 [10 15 18 45 46 5862 90]
C/C++代碼實現直接插入排序:
void InsertSortArray() {    for(int i=1;i<n;i++)//循環從第二個數組元素開始,因為arr[0]作為最初已排序部分     {        int temp=arr[i];//temp標記為未排序第一個元素         int j=i-1;        while (j>=0 && arr[j]>temp)"         {             arr[j+1]=arr[j];              j--;         }         arr[j+1]=temp;     } } 
Java代碼實現直接插入排序:
public class MainTest {
public static void main(String[] args) {
int[] a = { 46, 58, 15, 45, 90, 18, 10, 62 };
int n = a.length;
int i, j;
for (i = 0; i < n; i++) {
int temp = a[i];
for (j = i; j > 0 && temp < a[j-1]; j--) {
a[j] = a[j - 1];
}
a[j] = temp;
}
for(i=0;i<n;i++){
System.out.print(a[i]+"\t");
}
}
}

3演算法描述

Objective-C實現:
+ (void)sort:(NSMutableArray *)array{    int i, y;    for (i = 0; i< [array count]-1; i++)    {        //前面一位 大於 後面一位        if ([[array objectAtIndex:i+1] intValue] < [[array objectAtIndex:i] intValue])        {            //保存後面一位            NSString *temp = [array objectAtIndex:i+1];            //從后一位開始            for (y = i+1; y>0 && [[array objectAtIndex:y-1] intValue] > [temp intValue]; y--) {                [array exchangeObjectAtIndex:y-1 withObjectAtIndex:y];            }            //[array removeObjectAtIndex:y];            //[array insertObject:temp atIndex:y];        }    }}

相關評論

同義詞:暫無同義詞