Java插入排序實現

插入排序的思想是：每次將一個待排序的記錄，按其大小插入到前面已經排序的子序列的合適位置，直到全部插入。本文是插入排序的JAVA實現，包括直接插入排序，二分法插入排序和希爾排序。

package org.rev.algorithm;

/**

插入排序：每次將一個待排序的記錄，按其大小插入到前面已經排序的子序列的合適位置，直到全部插入。


直接插入排序：和已經排序的部分逐一比較找到合適位置




二分插入排序：使用二分法找到合適的位置




希爾排序（Shell Sort）：分組的直接插入排序


*/
public class InsertionSort {
public static void main(String[] args) {
 int[] data = {11, 39, 38, 55, 86, 5, 37, 12, 4, 11, 18};
 InsertionSort is = new InsertionSort();
 is.directInsertionSort(data); // 直接插入排序
 // is.binaryInsertionSort(data); // 二分法插入排序
 // is.ShellSort(data); // 希爾排序
 is.print(data); // 輸出排序后的數組
}
/**

直接插入排序，時間復雜度復雜度O(n^2)


第1個元素是一個length為1的有序數列，第2-第n元素為待排序的數列。




從第2個元素開始，和前面的有序數列中的元素比較（從后向前），找到合適的位置，并插入。




直到第n個元素插入完畢。



@param data 待排序的數列
*/
public void directInsertionSort(int[] data) {
for (int i = 1; i < data.length; i++) {
int tmp = data[i];
 int j;
 // data[0]--data[j]是有序數列
 for (j = i - 1; j >= 0; j--) {
   if (tmp < data[j]) { // 比tmp大都往后挪一下

 data[j + 1] = data[j];

} else {

 break;

}
 }
 // 把tmp插進前面空出的位置。
 data[j + 1] = tmp;
}


}


/**


二分法插入排序，時間復雜度復雜度O(n^2)

思想和直接插入一樣，只是找合適的插入位置的方式采用二分法查找，可以減少比較的次數。

@param data 待排序的數列
*/
public void binaryInsertionSort(int[] data) {
for (int i = 0; i < data.length; i++) {
 int tmp = data[i];
 // data[0] -- data[i-1]是有序數列
 int left = 0;
 int right = i - 1;
int mid = 0; // 中間值，初始為0
// 通過二分法找到要插入的位置，即left
 while (left <= right) {
   mid = (left + right) / 2;
   if (tmp < data[mid]) { // 如果小于中數

 right = mid - 1;

} else { // 如果大于等于中間的數

 left = mid + 1;

}
 }
 // 大家都往后挪一下，一人挪一下
 for (int j = i - 1; j >= left; j--) {
   data[j + 1] = data[j];
 }
 // 插進去
 data[left] = tmp;
}
}


/**

希爾排序，實質上是分組插入算法。

對于數列a1……an


取小于n的整數d作為第一個增量，把序列分成d個組，形如 {a[1],a[d+1],a[2d+1]),…}， {a[2],a[d+2],a[2d+2]),…}




分別在各個組內進行直接插入排序，完成第一次排序。




再取第二個增量d2（d2 < d），把序列分成d2 個組，分別在各個組中進行直接插入排序。




直到增量等于1。



@param data 待排序的數列
*/
public void ShellSort(int[] data) {
int d = data.length;
while (d > 1) {
 d = d / 2; // 取一個小于length的整數
 for (int x = 0; x < d; x++) { // 分成d個組
   // 組內直接插入排序
   for (int i = x + d; i < data.length; i = i + d) {
 int tmp = data[i];
 int j;
 for (j = i - d; j >= 0 && data[j] > tmp; j = j - d) {
   data[j + d] = data[j];
 }
 data[j + d] = tmp;

   }
 }
}
}

/*

打印輸出數組中的數據
*/
private void print(int[] data) {
for (int i = 0; i < data.length; i++) {
 System.out.print(data[i] + "\t");
}
System.out.println();
}

}</pre> 


   三種插入排序之間的比較： 
 
    1. 直接插入排序： 穩定排序，在數列相對有序的時候比二分插入塊。 
 
    2. 二分插入排序：穩定排序，當n較大時，對無序數列排序比直接插入要快。 
 
    3. 希爾排序：改進的直接插入算法，速度快，但不是穩定排序。