並べ替えアルゴリズムの2つ――並べ替えを挿入する2つの実現思想

http://blog.csdn.net/morewindows/article/details/6665714 https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
並べ替えを挿入する(英語:Insertion Sort)は簡単で直感的な並べ替えアルゴリズムです.その動作原理は、順序付けされたシーケンスを構築することによって、順序付けされていないデータに対して、順序付けされたシーケンスの中で後方から前へスキャンし、対応する位置を見つけて挿入することである.挿入順序付けは、実装では、一般的に、in-place順序付け(すなわち、O(1)までの追加の空間の順序付けのみを使用することができる)を使用しているので、後から前へスキャンする過程で、順序付けされた要素を逐次後方へ移動させ、最新の要素に挿入空間を提供する必要がある.
配列をa[0...n-1]に設定します.

の初期の時、a[0]は1つの順序区になり、無秩序区はa[1.n-1]である.令i=1

は、a［i］を現在の順序領域a［0…i−1］に組み込んでa［0…i］の順序区間を形成する.

i++は、i=n-1までの第二のステップを繰り返す.並べ替えが完了しました

Javaコード:

// j           
// arr[j]    arr[0]...arr[i - 1] 
public static void insertion_sort( int[] arr ) {
    for( int i=0; i<arr.length-1; i++ ) {   
        for( int j=i+1; j>0; j-- ) {
            if( arr[j-1] <= arr[j] )
                break;
            int temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }
    }
}

Javaの別のバージョン:

// i           
//  arr[i]    arr[0]...arr[i - 1] 
    public static void insertion_sort(int[] arr)
    {
        for (int i = 1; i < arr.length; i++ ) {
            int temp = arr[i];
            for (int j = i - 1; j >= 0 && arr[j] > temp; j-- ) {
                arr[j + 1] = arr[j];
                arr[j + 1] = temp;
            }
        }
    }