預備知識
排序算法從功能上是對一個數據元素集合或序列重新排列成一個按數據元素某個相知有序的序列。從內存空間使用簡單上看分為內部排序和外部排序。
內部排序是數據記錄在內存中進行排序，適合不太大的元素序列。而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。
排序算法穩定性是能保證排序前2個相等的數其在序列的前後位置順序和排序後它們兩個的前後位置順序相同。比如：Ai = Aj, Ai原來在位置前，排序後Ai還是要在Aj位置前。
排序算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就 是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩定，對基於比較的排序算法而言，元素交換 的次數可能會少一些。
插入排序—直接插入排序
基本算法：
每次從無序表中取出第一個元素，把它插入到前面已經排好序的子序列中的合適位置，使有序表仍然有序。即先將序列的第1個元素看成是一個有序的子序列，然後從第2個記錄逐個進行插入，直至整個序列有序為止。
直接插入排序示例：
直接插入排序有二種實現方式，帶哨兵與不帶哨兵。
帶哨兵的插入排序中的哨兵元素有兩個作用：
1、暫時存放待插入的元素，相當於臨時存儲元素。
2、可以防止數組下標越界，當待插入的元素小於已排序的子數組中的最小元素時，j=-1,越界，而采用哨兵，arr[0]<arr[j],當j=0時，就結束循環，不會出現越界（for循環只有一次判斷，提高了效率）。
帶哨兵需要注意一個問題：有方法傳進來的數組時原始數組，則插入第一個元素時，a[0]會被覆蓋，造成最終排完序的數組缺少了原始數組的第一個元素（bug）。
解決辦法:在調用此方法之前，將數組做下處理，使其右移一個元素的位置，空出來的第0個元素初始化為0（或不做初始化）。
/**
* 帶哨所
*
* @param sortList
*/
public static void insertSort1(Integer[] sortList) {
int len = sortList.length;
for (int i = 2; i < len; i++) {
if (sortList[i] < sortList[i - 1]) {
int j = i - 1;
sortList[0] = sortList[i];// 設置哨所
while (sortList[0] < sortList[j]) {
sortList[j + 1] = sortList[j];
j--;
}
sortList[j + 1] = sortList[0];
}
}
}
/**
* 不帶哨所
*
* @param sortList
*/
public static void insertSort2(Integer[] sortList) {
int len = sortList.length;
for (int i = 1; i < len; i++) {
if (sortList[i] < sortList[i - 1]) {
int j = i - 1;
int temp = sortList[i];
while (j >= 0 && temp < sortList[j]) {
sortList[j + 1] = sortList[j];
j--;
}
sortList[j + 1] = temp;
}
}
}
算法復雜度
1、時間復雜度：O(n^2)
直接插入排序耗時的操作有：比較+後移賦值。時間復雜度如下：
1)最好情況：序列是升序排列，在這種情況下，需要進行的比較操作需（n-1）次。後移賦值操作為0次。即O(n)。
2)最壞情況：序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。後移賦值操作是比較操作的次數加上 (n-1）次。即O(n^2)。
3)漸進時間復雜度（平均時間復雜度）：O(n^2)。
2、空間復雜度：O(1)
直接插入排序是在原輸入數組上進行後移賦值操作的（稱“就地排序”），所需開辟的輔助空間跟輸入數組規模無關，所以空間復雜度為：O(1)
穩定性
直接插入排序是穩定的，不會改變相同元素的相對順序。
算法優化：
二分查找插入排序的原理：是直接插入排序的一個變種，在有序區中查找新元素插入位置時，為了減少元素比較次數提高效率，采用二分查找算法進行插入位置的確定。
/**
* 二分查找插入排序
* @param sortList
*/
public static void insertSort3(Integer[] sortList) {
int len = sortList.length;
for (int i = 1; i < len; i++) {
if (sortList[i] < sortList[i - 1]) {
//二分查找在有序區尋找插入的位置
int index = binarySearchIndex(sortList, i-1, sortList[i]);
if (i != index)
{
int temp = sortList[i];
// 後移元素，騰出arr[index]位置
for (int j = i - 1; j >= index; j--)
sortList[j + 1] = sortList[j];
// 將 arr[i] 放到正確位置上
sortList[index] = temp;
}
}
}
}
/**
* 二分查找要插入的位置得index
* @param sortList
* @param maxIndex
* @param data
* @return
*/
private static int binarySearchIndex(Integer[] sortList, int maxIndex, int data)
{
int iBegin = 0;
int iEnd = maxIndex;
int middle = -1;
while (iBegin <= iEnd)
{
middle = (iBegin + iEnd) / 2;
if (sortList[middle] > data)
{
iEnd = middle - 1;
}
else
{
iBegin = middle + 1;// 如果是相同元素，也是插入在後面的位置
}
}
return iBegin;
}
算法復雜度
1、時間復雜度：O(n^2)
二分查找插入位置，因為不是查找相等值，而是基於比較查插入合適的位置，所以必須查到最後一個元素才知道插入位置。
二分查找最壞時間復雜度：當2^X>=n時，查詢結束，所以查詢的次數就為x，而x等於log2n（以2為底，n的對數），即O(log2n)。所以，二分查找排序比較次數為：x=log2n。
二分查找插入排序耗時的操作有：比較 + 後移賦值。時間復雜度如下：
1)最好情況：查找的位置是有序區的最後一位後面一位，則無須進行後移賦值操作，其比較次數為：log2n ，即O(log2n)。
2)最壞情況：查找的位置是有序區的第一個位置，則需要的比較次數為：log2n，需要的賦值操作次數為n(n-1)/2加上 (n-1) 次，即O(n^2)。
3)漸進時間復雜度（平均時間復雜度）：O(n^2)。
2、空間復雜度：O(1)
二分查找插入排序是在原輸入數組上進行後移賦值操作的（稱“就地排序”），所需開辟的輔助空間跟輸入數組規模無關，所以空間復雜度為：O(1)。
穩定性
二分查找排序是穩定的，不會改變相同元素的相對順序。
相關附件直接插入排序下載：
------------------------------------------分割線------------------------------------------
免費下載地址在 http://linux.linuxidc.com/
用戶名與密碼都是www.linuxidc.com
具體下載目錄在 /2014年資料/12月/12日/經典（Java版）排序算法的分析及實現之一直接插入排序
下載方法見 http://www.linuxidc.com/Linux/2013-07/87684.htm
------------------------------------------分割線------------------------------------------
歸並排序的實現 http://www.linuxidc.com/Linux/2014-09/107316.htm
直接插入排序的三種實現 http://www.linuxidc.com/Linux/2014-09/107313.htm
直接選擇排序及交換二個數據的正確實現 http://www.linuxidc.com/Linux/2014-09/107315.htm
排序總結之選擇式��序 http://www.linuxidc.com/Linux/2014-09/106564.htm
算法----選擇排序（select sort）http://www.linuxidc.com/Linux/2014-11/109827.htm
