8大ソート--ソートの挿入【直接ソートの挿入】

ソート・ポリシーの挿入:
無秩序サブシーケンスの1つまたは複数のレコードを秩序シーケンスに「挿入」し、レコードの秩序シーケンスの長さを増加させます.
ソートを直接挿入する方法は、次のとおりです.

は全部でn-1回のソートを行う.

p番目のパスでは、前のp+1要素の正しい位置が見つかるまで、位置p上の要素を左に移動します.

時間複雑度:O(n*n)
最良の場合,並べ替えられたときの時間複雑度はO(n)である.
ダイレクトコード:

package ch02;

import util.ArrayUtil;

public class InsertSort {
    //      O(n*n)
    public static void doInsertSort(int[] array){
        for(int i=1;iint tmp = array[i];
            int j;
            for(j=i;j>0&&tmp1];j--){
                array[j]=array[j-1];
            }
            array[j]=tmp;
        }
    }
    public static void main(String[] args) {
        int[] array = new int[]{58,46,72,95,84,25,37,58,63,12};
//      int[] array = new int[]{2,8,6,4,3,9,1};
        ArrayUtil.display(array);
        //      a[i]    ；         
        doInsertSort(array);
        ArrayUtil.display(array);
    }
}