最好o(n)，最壞時間o(n^2)，較穩定
基本思想：在要排序的一組數中，假設前面(n-1) [n>=2] 個數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這n個數也是排好順序的。如此反複循環，直到全部排好順序。
時間複雜度：o(n*log(n))，不穩定
由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，是以shell排序是不穩定的。
直接插入排序的的步長是為1的，而希爾排序向前比較是以一定步長向前比較。
最好：o(n^2)，最壞：o(n^2)，不穩定
基本思想：在要排序的一組數中，選出最小的一個數與第一個位置的數交換；然後在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最後一個數比較為止。
最好：nlog(n)，最壞：nlog(n)，不穩定
堆排序的基本思想是：将待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。将其與末尾元素進行交換，此時末尾就為最大值。然後将剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反複執行，便能得到一個有序序列了
初建堆：
将一個任意序列看成是對應的完全二叉樹，由于葉結點可以視為單元素的堆，因而可以反複利用上述調整的算法，自底向上逐層把所有子樹調整為堆，直到整個完全二叉樹為堆。最後一個非葉節點位于n/2(向下取整)個位置，n為二叉樹結點數目，是以，篩選從n/2(向下取整)個結點開始，逐層向上倒退，知道根節點。
調整堆：
這是為了保持堆的特性而做的一個操作。對某一個節點為根的子樹做堆調整，其實就是将該根節點進行“下沉”操作(具體是通過和子節點交換完成的)，一直下沉到合适的位置，使得剛才的子樹滿足堆的性質。
在對應的數組元素a[i], 左孩子a[left(i)], 和右孩子a[right(i)]中找到最大的那一個，将其下标存儲在largest中。
如果a[i]已經就是最大的元素，則程式直接結束。
否則，i的某個子結點為最大的元素，将a[largest]與a[i]交換。
再從交換的子節點開始，重複1,2,3步，直至葉子節點，算完成一次堆調整。
這裡需要提一下的是，一般做一次堆調整的時間複雜度為log(n)。
堆排序：
數組儲存成堆的形式之後，第一次将a[0]與a[n - 1]交換，再對a[0…n-2]重新恢複堆。第二次将a[0]與a[n-2]交換，再對a[0…n-3]重新恢複堆，重複這樣的操作直到a[0]與a[1]交換。由于每次都是将最小的資料并入到後面的有序區間，故操作完成後整個數組就有序了。
view code
o(n^2)，穩定
基本思想：在要排序的一組數中，對目前還未排好序的範圍内的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較後發現它們的排序與排序要求相反時，就将它們互換。
雙向冒泡排序算法步驟
比較相鄰兩個元素的大小。如果前一個元素比後一個元素大，則兩元素位置交換
對數組中所有元素的組合進行第1步的比較
奇數趟時從左向右進行比較和交換
偶數趟時從右向左進行比較和交換、
當從左端開始周遊的指針與從右端開始周遊的指針相遇時，排序結束
最好：o(nlog(n))，最壞：o(n^2)，不穩定
基本思想：選擇一個基準元素,通常選擇第一個元素或者最後一個元素,通過一趟掃描，将待排序列分成兩部分,一部分比基準元素小,一部分大于等于基準元素,此時基準元素在其排好序後的正确位置,然後再用同樣的方法遞歸地排序劃分的兩部分。
假設待劃分的序列為a[left]，a[left+1]......a[right]，首先将基準記錄a[left]移緻變量x中，使a[left]相當于空單元，然後反複進行如下兩個掃描過程，知道left和right相遇。
1.left從右向左掃描，直到a[right]<x，将a[right]移至空單元a[left]中，此時a[right]相當于空單元
2.left從左向右掃描，直到a[left]>x，将a[left]移到空單元a[right]，此時a[left]相當于空單元。
當left和right相遇時，a[left]或a[right]相當于空單元，且a[left]左邊均比它小，右邊均比它大，最後将基準記錄移至a[left]中，完成了一次劃分，再對a[left]的左子表和右子表進行同樣的劃分。
三路快排
在排序過程中分為比基準元素小的部分：[left,lt]，等于基準元素的部分：[lt+1,i)，大于基準元素的部分：[gt,r]
單連結清單快排
slow指針及左邊的元素都小于基準元素，fast指針用來周遊，當遇到比基準元素小的時候先slow後移，此時slow指向的肯定比基準元素大，在交換slow和fast指向的元素的值，相當于slow向右擴充。
最好：o(nlog(n))，最壞：o(nlog(n))，穩定
算法思想：
假設初始序列含有n個記錄，首先将這n個記錄看成n個有序的子序列，每個子序列的長度為1，然後兩兩歸并，得到n/2（向上取整）個長度為的有序子序列，在此基礎上，在對長度為2的有序子序列進行兩兩歸并，得到若幹個長度為4的子序列，重複，知道得到長度為n的有序序列為止。
tmp存放在歸并時完成歸并的數組，然後再将其指派給原數組。
單連結清單歸并
平均時間複雜度：o(n)，最好：o(n)，最壞：o(n)，穩定
基本思想：
将所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後,數列就變成一個有序序列。
整個算法過程描述如下：
1、将所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。
2、從最低位開始，依次進行一次排序。
3、這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。
基數排序的時間複雜度是 o(k•n)，其中n是排序元素個數，k是數字位數。
平均時間複雜度：o(n)，最好：o(n)，最壞：o(n)，不穩定
算法描述和分析
設定一個定量的數組當作空桶子。
尋訪串行，并且把項目一個一個放到對應的桶子去。
對每個不是空的桶子進行排序。
從不是空的桶子裡把項目再放回原來的串行中。
算法簡介
計數排序(counting sort)是一種穩定的排序算法。計數排序使用一個額外的數組c，其中第i個元素是待排序數組a中值等于i+min的元素的個數。然後根據數組c來将a中的元素排到正确的位置。它隻能對整數進行排序。
找出待排序的數組中最大和最小的元素
統計數組中每個值為i的元素出現的次數，存入數組c的第i項
對所有的計數累加（從c中的第一個元素開始，每一項和前一項相加）
反向填充目标數組：将每個元素i放在新數組的第c(i)項，每放一個元素就将c(i)減去1
計數排序是一種以空間換時間的排序算法，并且隻适用于待排序列中所有的數較為集中時，比如一組序列中的資料為0 1 2 3 4 999;就得開辟1000個輔助空間。
1.将待查找關鍵字k與索引表中的關鍵字進行比較，已确定待查找記錄所在的塊，可用折半查找或順序查找
2.進一步用順序查找，在相應的塊内查找關鍵字為k的元素。