直接挿入ソートの3つの実装Java


直接挿入ソート(Insertion) Sort)の基本的な考え方は,1つのソートされるレコードを,すべてのレコードの挿入が完了するまで,そのキーワードサイズで前に並べられたサブシーケンスの適切な位置に挿入することである.
コードクリップ:
コードクリップ
package algorithm;
 
public class InsertSort {
 
    /*
     *       (Insertion  Sort)      :           ,   
                        ,          
  。 
  
    a[0…n-1]。 
1.     ,a[0]  1    ,    a[1..n-1]。 i=1 
2.   a[i]        a[0…i-1]   a[0…i]     。 
3.  i++        i==n-1。    。
     */
    public static void insertSort1(int[] a, int n) {
        int i, j, k;
        for (i = 1; i < n; i++) {
            //  a[i]    a[0...i-1]             
            for (j = i - 1; j >= 0; j--) {
                if (a[j] < a[i]) {
                    break;
                }
            }
 
            //   a[i]       
            int temp = a[i];
            for (k = i - 1; k > j; k--) {
                a[k + 1] = a[k];//    
            }
            //  a[i]       
            a[k + 1] = temp;
 
        }
    }
    /*
     *         ,    。        ,            
   。   a[i]        a[i-1]  ,  a[i] > a[i-1]  a[0…i] 
    ,    。    j=i-1,temp=a[i]。       a[j]     
     ,    a[j]a[i]) {
int temp = a[i];
for(j = i-1; j >= 0 && a[j] > temp; j--) {
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
}
/*
*さらにa[j]を のa[0...j-1]の    に  するための  を き え,データ  で える.
データの に  します。a[j]の のデータa[j-1]>a[j]の  、a[j]とa[j-1]を  し、j--a[j-1]まで  する。
<= a[j]。これにより、 しいデータを    に  に み むことも  である。
*/
public static void insertSort3(int[] a, int n) {
int i, j;
for (i = 1; i < n; i++) {
for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--) {
swap(a, j, j+1);
}
}
}
public static void main(String[] args) {
int max = 10;
int[] a = { 2, 4, 1, 5, 7, 6, 1, 9, 0, 2 };
printArray(a, max);
insertSort3(a, max);
printArray(a, max);
insertSort2(a, max);
printArray(a, max);
insertSort1(a, max);
printArray(a, max);
}
private static void printArray(int[] a, int n) {
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
private static void swap(int a[], int x, int y) {
int t = a[x];
a[x] = a[y];
a[y] = t;
}
}