直接挿入ソートの3つの実装Java
2225 ワード
直接挿入ソート(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;
}
}