挿入ソート:直接挿入ソート-Direct insertion sort

基本思想.
配列R[0..n-1]にソートされるレコードが格納されていると仮定する.初期時、R[0]は1つの秩序領域を形成し、無秩序領域はR[1.n−1]であった.i=1からi=n−1まで順次R[i]を現在の秩序領域R[0..i−1]に挿入し、n個のレコードを含む秩序領域を生成する.

public class InsertSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int score[] = { 100, 69, 75, 87, 89, 90, 99, 67 };
        sort(score);
        for (int i : score) {
            System.out.print(i + "\t");
        }
    }

    public static void sort(int[] array) {
        int tmp;
        for (int i = 1; i < array.length; i++) {
            tmp = array[i]; // array[i]   
            //             array[i] <         array[i-1]，
            //        array[i]        。
            if (array[i] < array[i - 1]) {
                int j = i - 1;
                while (j >= 0 && tmp < array[j]) { //          
                    array[j + 1] = array[j]; //           array[i]  array[j+1]  
                    j--;
                }
                //   array[i]>=        array[i-1]，         ，     array[i]    
                //            tmp = array[i]        
                array[j + 1] = tmp;
            }
        }
    }
}

アルゴリズム解析

最良の状況:順序付けは直接順序付けの実行過程を挿入することによって見ることができ、順序付けされる配列が適切に順序付けされている場合、n-1の大きさの無秩序領域配列から1つの要素を取り出すたびに、順序付け領域の最後の要素と比較すると、必ず最後の要素より大きく、順序付け領域の最後の要素の後ろ、すなわちその場で挿入する必要がある.比較回数はn−1回,配列要素移動回数は0回であることがわかる.

最悪の場合:無秩序領域から最初の要素を逆順序で取り出すたびに、まず秩序領域の最後の要素と比較する必要があります.次に、秩序領域の最後の要素と比較するまで、秩序領域の最初の要素を比較し、秩序領域の最初の要素に挿入します.無秩序領域から最初の要素を取り出すたびに、コピーtmpに移動して配置し、tmpを秩序領域要素と比較します.この比較プロセスの合計移動回数は、秩序領域配列サイズ、最後にコピーtmp移動を秩序領域の位置に挿入することです.この過程で、秩序領域の配列サイズが1の場合、2回比較し、3回移動する.秩序領域配列サイズが2の場合、比較3回、移動4回;......秩序領域配列サイズがn−1の場合,n回比較し,n+1回移動する.比較回数が2+3+…+n=(n+2)(n-1)/2移動の場合は:3+4+…+n+1=(n+4)(n-1)/2上記の2つのケースの解析により,直接挿入ソートの時間的複雑度はO(n 2)であることがわかる.

くうかんふくざつさ
直接ソートを挿入する過程で,挿入すべき要素を1つのtmpに一時的に格納するだけで,空間複雑度はO(1)である.
ソート安定性
直接挿入ソートは、安定したソートです.