前言：
排序算法應該算是算法入門級的東西了，這裡重新學習算法，先暫時歸納下個人對插入排序與歸並排序兩種算法的理解。
插入排序：
插入排序可以對應到現實生活中的排隊去停車場停車的場景。假設某家飯店的飯菜十分好吃（流口水），導致來這裡吃飯的人特別多，後面來吃飯准備停車的車排起了長隊。每次只允許一輛車過去找位置，找到位置之後才允許下一輛車進入，依此類推，直到所有的車都停好。轉換成專業的數學模型就是：現有一個無序數組 A[n],要想對其進行排序。我們先從一個數開始考慮，A0肯定是排好序的。現在假設有A1，那麼這時候應該將A1和A0 進行比較排序。這時候假設再來A2，A2需要與前面排好隊的A0、A1 再進行比較排序。這裡需要注意的是在排序的過程中可能會產生數組的移動。下面是java代碼實現的升序排列的整數版本：
public static void main(String[] args) {
int[] arr = {2, 1, 23, 22, 15, 76, 43, 36};
ascInsertionSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 升序插入排列
* @param arr 傳入的數組
*/
private static void ascInsertionSort(int[] arr) {
int key = 0;
for (int j=1; j<arr.length; j++) { // 因為如果只有一個元素根本不需要排序，所以帶插入的元素的下邊從1開始
key = arr[j]; // 用key表示當前用來插入到已排序數組中的值
int i = j-1;
for (; i>=0; i--)
{
// 如果已排完序的數組的最後一個數比當前待插入的數小，說明不需要移動，直接break，否則需要交換兩個比較值的元素的位置
if (arr[i] > arr[i+1])
{
arr[i+1] = arr[i];
arr[i] = key;
}
else
{
break;
}
}
}
}
AscInsertionSort
很容易算出該算法的耗時主要是兩層for循環嵌套導致的，第一層for循環循環的次數為n次。第二層for循環每次運行的最壞的結果是需要把前面排序好的數組再全部循環一次，為：
1 + 2 + 3 + ... + (n-1) = (n2-1)/2。 我們知道對於n的多項式，隨著n的增長，對多項式結果影響結果最大的其實是最高的次數的那個項。所以不難得到該算法的時間復雜度為：θ(n2)。
選擇排序：
既然講了插入排序，順便講講選擇排序。選擇排序簡而言之就是每次選最帥的，選到最不帥的終結排序。
java實現的代碼如下：
/**
* 升序選擇排序
*
* @param arr
*/
private static void ascSelectionSort(int[] arr) {
int min;
int minIndex;
for (int i = 0; i < arr.length - 1; i++) {
min = arr[i]; // 假設最小的元素是當前就在該位置的元素
minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < min) // 如果有元素比最小的元素小，則將該元素的值作為最小元素的值，依次查找下去，最終找到最小元素所在的下表
{
min = arr[j];
minIndex = j;
}
}
// 循環完發現最小元素的位置不是當前在該位置的元素，則交換兩個元素的位置
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
ascSelectionSort
可以發現一個很悲傷的事實，這個算法的時間復雜度也為：θ(n2)。
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2016-04/129799p2.htm
