排序算法淺析——插入排序

插入排序

平時學的一些總容易忘，是以記錄一下，加強記憶。本文主要介紹直接插入排序和希爾排序。

1、插入排序—直接插入排序(Straight Insertion Sort)

算法描述

》将一條記錄插入到已排序好的有序表中，進而得到一個新的有序表，記錄數增1的有序表。即：先将序列的第1個記錄看成是一個有序的子序列，然後從第2個記錄逐個進行插入，直至整個序列有序為止。

》要點：設立哨兵，作為臨時存儲和判斷數組邊界之用。

》具體過程如圖所示：

算法分析

平均時間複雜度：O(n2)

空間複雜度：O(1) (用于記錄需要插入的資料)

穩定性：穩定

算法實作

public class StraightInsertionSort {

    public static int[] Straight(int[] sort) {
        if (sort.length == ) {
            return sort;
        }

        for (int i = ; i < sort.length; i++) {
            int flagTemp = sort[i];
            if (flagTemp > sort[i - ]) {
                continue;
            }
            int j = (i - );
            while (j >= ) {
                if (sort[j] > flagTemp) {
                    sort[j + ] = sort[j];
                } else {
                    break;
                }
                j--;
            }
            sort[j + ] = flagTemp;
        }

        return sort;
    }

    public static void main(String[] args) {
        int[] test = { , , , , , , ,  };
        int[] test2 = StraightInsertionSort.Straight(test);
        for (int result : test2) {
            System.out.print(result + " ");
        }
    }

}
           

2、插入排序—希爾排序（Shell`s Sort）

算法描述

》把整個待排序的記錄按下标的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，算法便終止。

》具體過程如圖所示：

算法分析

平均時間複雜度：O(Nlog2N)（取決于增量的選取，優于直接插入排序）

空間複雜度：O(1)

穩定性：不穩定

算法實作

其中增量dk直接初始為序列長度的一半，并不停的縮小為dk/2，步長的選擇是希爾排序的重要部分。隻要最終步長為1任何步長序列都可以工作，并且選取不同的步長也關系着時間複雜度，這裡我隻簡單的實作，想了解步長的選擇可以檢視其它資料。

public class ShellSort {

    public static int[] shell(int[] sort){
        int dk = sort.length / ;
        while(dk >= ){
            for(int i=; i<sort.length - dk; i++){
                if(sort[i] > sort[i+dk]){
                    int temp = sort[i];
                    sort[i] = sort[i+dk];
                    sort[i+dk] = temp;
                }
            }
            dk = dk / ;
        }
        return sort;
    }

    public static void main(String[] args) {
        int[] test = { , , , , , , ,  };
        int[] test2 = ShellSort.shell(test);
        for (int result : test2) {
            System.out.print(result + " ");
        }
    }

}
           

參考：

http://www.cnblogs.com/jingmoxukong/p/4303279.html

http://blog.csdn.net/hguisu/article/details/7776068