● 穩(wěn)定性：在排序過程中凰狞，如果有兩個元素的值相等篇裁，那么它們在排序前后的相對位置不會發(fā)生改變。
4赡若、希爾排序：是插入排序的改進版茴恰，又稱縮小增量(gap)排序。
基本思想：根據(jù)這個增量來劃分組斩熊，每一組進行插入排序，所有組排序后稱為一趟希爾排序伐庭。本質(zhì)是對數(shù)組的局部進行排序粉渠。
重復(fù)此過程：gap = len/2分冈；gap = gap/2 => 直到gap = 1，做最后一次排序霸株。（排序可以是任意一種）
5雕沉、歸并： 穩(wěn)定，時間：O(nlogn)去件，樹高度為O(logn)坡椒，每層的時間復(fù)雜度為O(n)∮攘铮空間：O(n)
C++
void merge(int a[], int b,int m, int e){
int i = b;
int j = m + 1;
// 必須從0開始授霸，因為申請的新空間是從索引0開始的巡验，復(fù)制的只是值。
int k = 0;
// 新數(shù)據(jù)可能會存在覆蓋舊數(shù)據(jù)的情況碘耳，所以必須重新開辟一個數(shù)組
vector<int> v(a, a + sizeof(a)/sizeof(int));
while(i <= m && j <= e){
if(a[i] <= a[j]) v[k++] = a[i++];
else v[k++] = a[j++];
}
while(i <= m) v[k++] = a[i++];
while(j <= e) v[k++] = a[j++];
for(int t = b;t <= e;t++){
a[t] = v[t - b];
}
}
void mergeSort(int a[], int b, int e){
if(b >= e) return;
int m = (b + e)/2;
mergeSort(a, b, m);
mergeSort(a, m + 1, e);
merge(a, b, m, e);
}
? 另：涉及到跟磁盤打交道（外部排序）显设，則需要特殊的考慮。歸并排序是天然適合外部排序的算法辛辨，可以將分割后的子數(shù)組寫到單個文件中捕捂，歸并時將小文件合并為更大的文件【利用雙指針合并】。
6愉阎、快排：不穩(wěn)定绞蹦，時間：O(nlogn)，空間：O(logn)
C++
//快排
int findPartition(int a[], int b, int e){
int base = a[b];
int i = b;
int j = e;
while(i < j){
while(i < j && base <= a[j]) j--;
a[i] = a[j];
while(i < j && base >= a[i]) i++;
a[j] = a[i];
}
a[i] = base;
return i;
}
void quickSort(int a[], int b, int e){
if(b >= e) return;
int index = findPartition(a, b, e);
quickSort(a, b, index - 1);
quickSort(a, index + 1, e);
}
快排優(yōu)化
① Tail Call（尾調(diào)用）：盡量使得函數(shù)調(diào)用發(fā)生在最后，此時父函數(shù)無需保存自身變量等等咐旧，從而節(jié)省了空間驶鹉。
普通快排選擇最左元素為基準(zhǔn)值，在數(shù)組元素完全倒序時铣墨，會導(dǎo)致遞歸棧深度到達N（即最差空間復(fù)雜度O(N)）室埋。
優(yōu)化策略：不再對左右兩個數(shù)組都進行遞歸，而是將較短的子數(shù)組遞歸，可以將最差的遞歸深度控制在O(logN)姚淆。
● 理解：當(dāng)數(shù)組完全倒序時孕蝉，下一個遞歸方法壓棧時，棧是空的（因為已經(jīng)處理好上一個遞歸方法了）腌逢，這種尾調(diào)用可使得遞歸深度更小降淮。
只需修改quickSort函數(shù)：
void quickSort(int[] nums, int l, int r) {
// 子數(shù)組長度為 1 時終止遞歸
while (l < r) { 【注意！】
// 哨兵劃分操作
int i = partition(nums, l, r);
// 僅遞歸至較短子數(shù)組搏讶，控制遞歸深度
if (i - l < r - i) {
quickSort(nums, l, i - 1);
l = i + 1; 【注意佳鳖！】
} else {
quickSort(nums, i + 1, r);
r = i - 1; 【注意！】
}
}
}
?另外：當(dāng)數(shù)據(jù)量比較大的時候先用的快排媒惕，當(dāng)數(shù)據(jù)量小的時候可以考慮用【直接插入】系吩，因為當(dāng)數(shù)據(jù)量變小時，快排中的每個部分基本有序吓笙，接近直接插入的最好情況的時間復(fù)雜度O(n)淑玫，就比快排要好一點了。
② 隨機基準(zhǔn)數(shù)：不是總選最左元素面睛，而是隨機選擇一個元素作為基準(zhǔn)數(shù)（選擇完畢后絮蒿，可跟最左元素交換位置）
只需修改partition函數(shù)：
int partition(int[] nums, int l, int r) {
// 在閉區(qū)間 [l, r] 隨機選取任意索引，并與 nums[l] 交換
int ra = (int)(l + Math.random() * (r - l + 1));
swap(nums, l, ra);
……
}
?另外：中樞選擇除了隨機叁鉴，還可以使用【三數(shù)取中】策略土涝。即知道數(shù)列的首尾后，我們便可以求出中間位置的數(shù)幌墓，我們只需要在首但壮，中，尾這三個數(shù)據(jù)中常侣，選擇一個排在中間的數(shù)據(jù)作為基準(zhǔn)值蜡饵。
7、堆排序: 不穩(wěn)定胳施，時間：O(nlogn)溯祸，空間：O(1)
C++
void heapAdjust(int a[], int len, int t){
int target = a[t];
for(int i = t * 2 + 1; i < len; i = t * 2 + 1){
if(i + 1 < len && a[i] < a[i + 1]) i++;
if(a[i] <= target) break;
else{
a[t] = a[i];
t = i;
}
}
a[t] = target;
}
void heapSort(int a[], int len){
// 構(gòu)建大根堆
for(int i = len/2 - 1; i >= 0; i--){
heapAdjust(a, len, i);
}
// 堆排序
for(int i = len - 1; i > 0; i--){
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapAdjust(a, i, 0);
}
}
8、計數(shù)排序——不基于比較的排序
基本思想：找到數(shù)組種最小和最大的元素舞肆，得到他們的差值范圍焦辅，申請額外空間。然后遍歷數(shù)組椿胯，在額外的空間中統(tǒng)計對應(yīng)位置的數(shù)量筷登。根據(jù)額外空間中的統(tǒng)計信息，根據(jù)數(shù)量打印數(shù)據(jù)哩盲。
優(yōu)勢：在對一定范圍內(nèi)的整數(shù)排序時前方，他的復(fù)雜度為O(n+k)(其中k是整數(shù)的范圍)狈醉，快于任何比較的排序算法。
劣勢：它是一種犧牲空間惠险，換取時間的做法舔糖。如果O(k)>O(nlogn)時，它的效率反而不如基于比較的排序算法莺匠。
9、桶排序（箱排序）——不基于比較的排序
基本思想：將數(shù)組分到有限數(shù)量的桶子(劃分?jǐn)?shù)據(jù)范圍)里十兢。將數(shù)組中的元素分配到這些桶中趣竣，對桶中的元素進行排序(有可能是再使用別的排序算法，或者是以遞歸的方式繼續(xù)使用桶排序)旱物。將每個桶中排好序的元素遥缕，按照桶的順序依次輸出。
10宵呛、基數(shù)排序：桶排序的擴展单匣，是一種效率高的穩(wěn)定排序法——不基于比較的排序
基本思想：根據(jù)數(shù)值的個位、十位宝穗、百位……來將數(shù)據(jù)裝入桶中户秤。確定數(shù)組中最大元素的位數(shù)(并將其他數(shù)通過高位補0的操作，達到位數(shù)對齊的目的)逮矛，這決定了裝桶操作的輪數(shù)鸡号。每一輪裝桶(從最低位個位開始)，需要判斷元素當(dāng)前位须鼎，存入對應(yīng)的桶中(共有0~9鲸伴，10個桶)。完成這一輪后晋控，出隊(按照入桶順序)汞窗，存入原數(shù)組。重復(fù)操作赡译，直至完成最大輪次仲吏。
● 如果是按照：個位→十位→百位→……，那么就是不斷迭代捶朵，將數(shù)按順序重復(fù)幾輪（數(shù)位決定了輪次）裝入0-9的桶中蜘矢；
● 如果是按照：……→百位→十位→個位，那么就是演變成桶排序综看，需要在各自的桶中繼續(xù)進行排序品腹。
