插入排序是常見的内部排序之一。常見的插入排序包括直接插入排序、Shell排序、折半排序。本篇主要介紹這三個排序。
轉載請注明出處——http://www.cnblogs.com/zrtqsk/p/3807611.html，謝謝！
一、直接插入排序
直接插入排序大概是我們最容易了解的一類排序了。
1、原理
對于n個元素的記錄。
第一趟 ： 把第2個元素拿出來跟第1個元素對比，小的在前面、大的在後面。
第二趟 ： 把第3個元素拿出來插入到前2個元素中，使他們有序。
第三趟 ： 把第4個元素拿出來插入到前3個元素中，使他們有序。
......
第n-1趟 ： 把第n個元素拿出來插入到前n-1個元素中，排序完成。
2、Java實作
package sort;
/**
* 想法：如果要将數組集體後移，那麼必須要從後往前周遊。
*
* @ClassName: InserSort
* @Description: 插入排序
* @author qsk
* @date 2014年6月21日 下午4:06:04
*/
public class InsertSort {
public static void sort(int[] source) {
SortUtil.outputArray(source);
int size = source.length;
// 從第二個開始，周遊每一個數組元素
for (int i = 1; i < size; i++) {
// 取出來
int temp = source[i];
// 跟之前排序好的進行比較、插入
for (int j = 0; j < i; j++) {
// 如果比某一個小，
if (temp < source[j]) {
// 那麼原排序好的，集體後移
for (int k = i; k > j; k--) {
source[k] = source[k - 1];
}
source[j] = temp;
//輸出
SortUtil.outputArray(source);
// 集體後移後，跳出循環
break;
}
}
}
}
// 改進後的
public static void sort1(int[] source) {
SortUtil.outputArray(source);
int size = source.length;
// 從第二個開始，周遊每一個數組元素
for (int i = 1; i < size; i++) {
// 取出來
int temp = source[i];
// 從後往前周遊，找到插入位置
int j;
for (j = i - 1; j >= 0 && temp < source[j]; j--) {
source[j + 1] = source[j];
}
// 由于上面的循環完畢之後執行了j--,是以這裡給source[j+1]指派
source[j + 1] = temp;
//輸出
SortUtil.outputArray(source);
}
}
public static void main(String[] args) {
sort1(SortUtil.getRandomArray());
}
} 如上，有2個實作，sort()是我很快寫出來的，很明顯，3個嵌套循環非常麻煩。這裡我們可以發現，周遊一個數組結構的時候，向前和向後周遊都很講究，要想清楚處理邏輯再決定選擇向前還是向後周遊。注釋解釋的很清楚了，不必多說。結果如下：
[6, 22, 71, 64, 33, 57, 38, 30, 42, 14]
[6, 22, 71, 64, 33, 57, 38, 30, 42, 14]
[6, 22, 71, 64, 33, 57, 38, 30, 42, 14]
[6, 22, 64, 71, 33, 57, 38, 30, 42, 14]
[6, 22, 33, 64, 71, 57, 38, 30, 42, 14]
[6, 22, 33, 57, 64, 71, 38, 30, 42, 14]
[6, 22, 33, 38, 57, 64, 71, 30, 42, 14]
[6, 22, 30, 33, 38, 57, 64, 71, 42, 14]
[6, 22, 30, 33, 38, 42, 57, 64, 71, 14]
[6, 14, 22, 30, 33, 38, 42, 57, 64, 71] 3、時間複雜度和穩定性
直接插入排序的時間複雜度是O(N2)。
假設被排序的數列中有N個數。周遊一趟的時間複雜度是O(N)，需要周遊多少次呢？N-1！是以，直接插入排序的時間複雜度是O(N2)。
直接插入排序是穩定的算法，它滿足穩定算法的定義。
二、折半插入排序
折半插入排序是對直接插入排序的改進。
我們看直接插入排序的步驟簡單而言其實就2步，第1步是從已經排好序的數組中找到該插入的點，第2步是将資料插入，然後後面的資料整體後移。那麼直接插入排序是如何找到該插入的點的呢？是無腦式的從頭到尾的周遊。問題是被插入的數組是排好序的，根本沒有必要從頭到尾周遊。折半插入排序就是改進了第1步——從已經排好序的數組中找到該插入的點。
折半插入排序是怎麼做的呢？非常簡單。取已經排好序的數組的中間元素，與插入的資料進行比較，如果比插入的資料大，那麼插入的資料肯定屬于前半部分，否則屬于後半部分。這樣，不斷周遊縮小範圍，很快就能确定需要插入的位置。這就是所謂“折半”。
(Arrays類的binarySearch()方法就是折半查找的實作)
package sort;
public class HalfInsertSort {
public static void sort(int[] source) {
int size = source.length;
for (int i = 1; i < size; i++) {
// 拿出來
int temp = source[i];
int begin = 0; // 标記排好序的數組的頭部
int end = i - 1; // 标記排好序數組的尾部
// 隻要頭部一直小于尾部，說明temp還在2個标記範圍内
while (begin <= end) {
// 取2個标記的中間資料的值
int mid = (begin + end) / 2;
// 比較，若比中間值大，則範圍縮小一半
if (temp > source[mid]) {
begin = mid + 1;
// 否則，範圍也是縮小一半
} else {
end = mid - 1;
}
// 循環結束時，end<begin,即i應該插入到begin所在的索引
}
// 從begin到i，集體後移
for (int j = i; j > begin; j--) {
source[j] = source[j - 1];
}
// 插入i
source[begin] = temp;
SortUtil.outputArray(source);
}
}
public static void main(String[] args) {
sort(SortUtil.getRandomArray());
}
} 如上，注釋已經非常清楚了。結果如下：
[4, 11, 4, 41, 61, 83, 86, 81, 35, 90]
[4, 4, 11, 41, 61, 83, 86, 81, 35, 90]
[4, 4, 11, 41, 61, 83, 86, 81, 35, 90]
[4, 4, 11, 41, 61, 83, 86, 81, 35, 90]
[4, 4, 11, 41, 61, 83, 86, 81, 35, 90]
[4, 4, 11, 41, 61, 83, 86, 81, 35, 90]
[4, 4, 11, 41, 61, 81, 83, 86, 35, 90]
[4, 4, 11, 35, 41, 61, 81, 83, 86, 90]
[4, 4, 11, 35, 41, 61, 81, 83, 86, 90] 折半插入排序的時間複雜度是O(N2)。
折半插入排序算法是一種穩定的排序算法，比直接插入算法明顯減少了關鍵字之間比較的次數，是以速度比直接插入排序算法快，但記錄移動的次數沒有變，是以折半插入排序算法的時間複雜度仍然為O(n^2)，與直接插入排序算法相同。
折半插入排序是穩定的算法，它滿足穩定算法的定義。
三、Shell排序
Shell排序也是對直接插入排序的改進。它實質上是一種分組插入方法。可以這麼簡單了解：
對于n個元素的數組，假設增量為 h：
第一趟 ： 從第1個元素開始，每隔h取一個元素，那麼最後可以得到n/h個元素，一邊取，一邊通過直接插入将這h個元素排序
第二趟 ： 從第2個元素開始，每隔h取一個元素，跟第一趟一樣。
...
第h趟 ： 從第h個元素開始，每隔h取一個元素，跟第一趟一樣。
（此時，整個數組還不是有序的）
然後，減少h的值，重複上面的操作，直到h減小為1，排序完成。
package sort;
/**
* @ClassName: ShellSort
* @Description: 折半排序
* @author qsk
* @date 2014年6月22日 下午3:48:01
*/
public class ShellSort {
public static void sort(int[] source) {
// 排序前先輸出
SortUtil.outputArray(source);
int size = source.length;
// 增量
int h = 1;
// 得到增量的最大值
while (h <= size / 3) {
h = h * 3 + 1;
}
while (h > 0) {
System.out.println("h的值為" + h);
// 因為每個i都要跟i-h比較，是以從h到size周遊了每個數組元素
for (int i = h; i < size; i++) {
// 取值
int temp = source[i];
// 取i之前h距離的索引為j
int j = i - h;
// 如果temp比j對應的值小
if (temp < source[j]) {
// 從j開始往前每隔h取一個值，如果這個值比temp要大，那麼把這個值後移h個機關。
for (; j >= 0 && source[j] > temp; j -= h) {
source[j + h] = source[j];
}
// 最後将temp的值插入合适位置
source[j + h] = temp;
SortUtil.outputArray(source);
}
}
h = (h - 1) / 3;
}
}
public static void sort1(int[] source) {
// 排序前先輸出
SortUtil.outputArray(source);
int size = source.length;
// 增量
int h = 1;
// 得到增量的最大值
while (h <= size / 3) {
h = h * 3 + 1;
}
while (h > 0) {
System.out.println("h的值是" + h);
// 0到h的周遊
for (int x = 0; x < h; x++) {
// i每次遞增h，這兩個for循環，周遊了所有數組元素
for (int i = x + h; i < source.length; i = i + h) {
// 用temp記錄i的值
int temp = source[i];
int j;
// 從j開始往前，每隔h取一個值與temp進行比較，若比temp大則向後移動h個機關
for (j = i - h; j >= 0 && source[j] > temp; j = j - h) {
source[j + h] = source[j];
}
source[j + h] = temp;
}
// 每一趟排序後輸出
SortUtil.outputArray(source);
}
h = (h - 1) / 3;
}
}
public static void main(String[] args) {
sort1(SortUtil.getRandomArray());
}
} 這裡有2個算法實作，第二個sort1()方法，用了3個for循環嵌套，比較容易了解，不過實在不夠優雅。而sort1()将其進行了改進，使用2個for循環實作。
我們知道，Shell排序的關鍵是确定增量 h 的值，以及 h 如何減少。上文的 h 值算法由Knuth提出，是比較常用的取h值的算法。經常可以看到許多人實作shell排序，取h的時候，直接減半，這樣，數組項移動的距離很長，不過移動元素的個數較少，相對而言沒有Knuth的算法有效率。
上面的結果如下：
h的值是4
[4, 9, 89, 85, 36, 5, 85, 44, 96, 96]
[4, 5, 89, 85, 36, 9, 85, 44, 96, 96]
[4, 5, 85, 85, 36, 9, 89, 44, 96, 96]
[4, 5, 85, 44, 36, 9, 89, 85, 96, 96]
h的值是1
[4, 5, 9, 36, 44, 85, 85, 89, 96, 96] Shell排序的時間複雜度是根據增量h的不同而不同，當增量為1時，希爾排序退化成了直接插入排序，此時的時間複雜度為O(N²)。Shell排序的時間複雜度在O(n3/2)-O(n7/6)之間。
Shell排序算法是一種不穩定的排序算法。
參考：《Java程式員的基本修養》
http://www.cnblogs.com/skywang12345/p/3597597.html
/**
* ————————如果覺得本博文還行，别忘了推薦一下哦，謝謝！
* 作者：錢書康
* 歡迎轉載，請保留此段聲明。
* 出處：http://www.cnblogs.com/zrtqsk/
*/