算法概述：
插入排序（Insertion Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間。
插入排序主要分為三種，即直接插入，二分插入（利用二分法來減少比較次數），希爾排序（又稱縮小增量排序）
插入的主要步驟：
1，從第一個元素開始，該元素可以認為已經被排序
2，取出下一個元素，在已經排序的元素序列中從後向前掃描
3，如果該元素（已排序）大於新元素，將該元素移到下一位置
4，重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
5，將新元素插入到該位置後
6，重復步驟2~5
復雜度分析：
直接插入復雜度：
二分插入復雜度：
插入每個記錄需要O(log i)比較，最多移動i+1次，最少2次
最佳情況O(nlog n)，最差和平均情況O(n^2)。
希爾排序復雜度：
代碼示例：
package com.louxue.sort;
import java.util.Arrays;
/**
* 插入排序
* @author louxuezheng 2014年3月10日
*/
public class InsertSort {
public static void main(String... args) {
int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62,
99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };
// new InsertSort().insertSort(a);// 直接插入排序
// new InsertSort().shellSort(a);
// new InsertSort().shellSort2(a);
new InsertSort().binaryInsertSort(a);
System.out.println(Arrays.toString(a));
}
/**
* 直接插入排序是穩定的排序
* 基本思想：在要排序的一組數中，假設前面(n-1)[n>=2] 個數已經是排 好順序的，
* 現在要把第n個數插到前面的有序數中，使得這n個數 也是排好順序的。
* 如此反復循環，直到全部排好順序。
* @param a
*/
private void insertSort(int[] a) {
int temp = 0;
for(int i=1;i<a.length;i++){
int j=i-1;
temp = a[i];// 要被插入的第i個數，這個數與前面的排好序的數進行比較。比它大的整體都向後移動
while (j >= 0 && temp < a[j]) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
/**
* shell排序是不穩定的。
* 基本思想：算法先將要排序的一組數按某個增量d（n/2,n為要排序數的個數）分成若干組，
* 每組中記錄的下標相差d. 對每組中全部元素進行直接插入排序，然後再用一個較小的增量
* （d/2）對它進行分組，在每組中再進行直接插入排序。當增量減到1時，進行直接插入排序後，排序完成。
*
* @param a
*/
private void shellSort(int[] a) {
double d1 = a.length;
int temp = 0;
while (true) {
d1 = Math.ceil(d1 / 2);// 向上取整計算，它返回的是大於或等於函數參數，並且與之最接近的整數。
int d = (int) d1;
for (int x = 0; x < d; x++) {
for (int i = x + d; i < a.length; i += d) {
int j = i - d;
temp = a[i];
for (; j >= 0 && temp < a[j]; j -= d) {
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
if (d == 1)
break;
}
}
/**
* Knuth 提出的d=[d/3]+1，下取整。
*
* @param a
*/
private void shellSort2(int[] a) {
int d = a.length;
int temp = 0;
do {
d=d/3+1;
for (int x = 0; x < d; x++) {
for (int i = x + d; i < a.length; i += d) {
int j = i - d;
temp = a[i];
for (; j >= 0 && temp < a[j]; j -= d) {
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
} while (d > 1);
}
/**
* 折半插入排序是穩定的排序
* 又稱為二分插入排序，基本思想：設在數組中前i-1個元素是已經排好序的，
* 在插入a[i]時，利用二分搜索的方法找到a[i]的位置插入。
* @param a
*/
private void binaryInsertSort(int[] a) {
int temp = 0;
int i, low, high, middle, k;
for (i = 1; i < a.length; i++) {
temp = a[i];
low = 0;
high = i - 1;
while (low <= high) {
middle = (low + high) / 2;
if (temp < a[middle]) {
high = middle - 1;
} else
low = middle + 1;
}
for (k = i - 1; k >= low; k--)
a[k + 1] = a[k];// 成塊移動空出插入位置
a[low] = temp;
}
}
}
