題記：
? 直接插入排序（穩(wěn)定）-->希爾排序? ： 屬于插入排序
? 簡單選擇排序（穩(wěn)定）-->堆排序 ：屬于選擇排序
? 冒泡排序算法（穩(wěn)定）-->快速排序? ：屬于交換排序
?? 歸并排序（穩(wěn)定）
一.直接插入排序----O(n^2)-----穩(wěn)定的
? ? ? ? 直接插入排序：是一種將一個記錄插入到已經(jīng)安排好序的有序表中鱼响，從而得到一個新的記錄數(shù)增1的有序表鸣剪。
1.算法流程：
1）初始時， a[0]自成一個有序區(qū)， 無序區(qū)為a[1, ... , n-1], 令i=1;
2）將a[i]并入當(dāng)前的有序區(qū)a[0, ... , i-1];
3）i++并重復(fù)2）直到i=n-1, 排序完成西傀。
時間復(fù)雜度：O(n^2)。
示意圖：初始無序數(shù)列為 49桶癣， 38拥褂， 65， 97牙寞， 76饺鹃， 13， 27间雀，49
2. C++實現(xiàn)
void InsertSort(SqList *L){
? ? ? ? ? int i, j;
? ? ? ? ? for( i=2;i<L->length;i++) ?{
? ? ? ? ? ? ? ?if(L->r[i]<L->r[i-1) {
? ? ? ? ? ? ? ? ? ?L->r[0]=L->r[i]; ? ?//L->r[0]是哨兵位置
? ? ? ? ? ? ? ? ? ?for(j=i-1;L->r[j]>L->r[0];j--)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?L->r[j+1]=L->r[j];
? ? ? ? ? ? ? ? ? ?L->r[j+1]=L->r[0];
? ? ? ? ? ? ? ? }
? ? ? ? ? }
}
//插入排序悔详，版本3：用數(shù)據(jù)交換代替版本2的數(shù)據(jù)后移(比較對象只考慮兩個元素)
void StraightInsertionSort3(int a[],int n)
{
? ? ? ? for(inti=1; i<n; i++)
? ? ? ? ? ? ? ?for(int j=i-1; i=0 && a[j]>a[j+1] ; ?j--)
? ? ? ? ? ? ? ? ? ? ? ? ? Swap(a[j], a[j+1]);
}
二、冒泡排序算法----O(n^2)---穩(wěn)定的
? ? ? ? ? 冒泡排序：是一種交換排序惹挟，它基本思想是茄螃，兩兩比較相鄰的關(guān)鍵字，如果反序則交換连锯，直到?jīng)]有反序的記錄為止归苍。
算法流程：
1）比較相鄰的兩個元素，如果前面的數(shù)據(jù)大于后面的數(shù)據(jù)运怖，就將兩個數(shù)據(jù)進(jìn)行交換拼弃；這樣對數(shù)組第0個元素到第n-1個元素進(jìn)行一次遍歷后，最大的一個元素就沉到數(shù)組的第n-1個位置摇展；
2）重復(fù)第2）操作吻氧，直到i=n-1。
時間復(fù)雜度分析：O(n^2)咏连，冒泡排序是一種不穩(wěn)定排序算法盯孙。
冒泡排序的示例：
2. C++實現(xiàn)
void BubbleSort(int p[], int len){
? ? int temp;
? ? for (int i = 0; i < len; i++)
? ? ? ? for (int j = i + 1; j < len; j++){
? ? ? ? ? ? if (p[i]>p[j]){
? ? ? ? ? ? ? ? ?temp = p[i];
? ? ? ? ? ? ? ? p[i] = p[j];
? ? ? ? ? ? ? ?p[j] = temp;
? ? ? ? ? ? ? }
? ? ? ?}
}
三、簡單選擇排序-----O(n^2)-----穩(wěn)定
? ? ? ? 簡單選擇排序算法：就是通過n-i次關(guān)鍵字間的比較祟滴，從n-i+1個記錄中選擇出關(guān)鍵字最小的記錄镀梭，并和第i(1<=i<=n)個記錄作交換。
算法流程：
1）初始時踱启，數(shù)組全為無序區(qū)a[0, ... , n-1], 令i=0;
2）在無序區(qū)a[i, ... , n-1]中選取一個最小的元素與a[i]交換报账，交換之后a[0, ... , i]即為有序區(qū)；
3）重復(fù)2）埠偿，直到i=n-1透罢，排序完成。
時間復(fù)雜度分析：O(n^2)冠蒋。
直接選擇排序的示例：
2. C++實現(xiàn)
void SelectSort(int *p, int len)
{
? ? ? ? ?int minIndex, i, j;
? ? ? ? ?for (i = 0; i < len; i++)
? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?minIndex = i;//記錄最小數(shù)值的下標(biāo)
? ? ? ? ? ? ? ? ? ?for (j = i + 1; j < len; j++)
? ? ? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ? ? ? if (p[minIndex]>p[j])
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?minIndex = j;
? ? ? ? ? ? ? ? ? ? ?} ? ? ? ? ?
? ? ? ? ? ? ? ? ?if (minIndex != i)
? ? ? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?int temp;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? temp = p[i];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? p[i] = p[minIndex];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?p[minIndex] = temp;
? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? }
}
四羽圃、希爾排序算法------O(nlogn)~O(n^2)----不穩(wěn)定
基本思想：先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時抖剿，再對全體記錄進(jìn)行依次直接插入排序朽寞。
算法流程：
1）選擇一個增量序列t1识窿，t2，…脑融，tk喻频，其中ti>tj，tk=1肘迎；
2）按增量序列個數(shù)k甥温，對序列進(jìn)行k 趟排序；
3）每趟排序妓布，根據(jù)對應(yīng)的增量ti姻蚓，將待排序列分割成若干長度為m 的子序列，分別對各子表進(jìn)行直接插入排序匣沼。僅增量因子為1 時狰挡，整個序列作為一個表來處理，表長度即為整個序列的長度释涛。
時間復(fù)雜度：O(n^(1+e))(其中0
希爾排序的示例：
2. C++實現(xiàn)
//希爾排序
void shellSort(int *p, int len){
? ? ? ? ?int i, j, increment, temp;
? ? ? ? ?for (increment = len / 2; increment > 0; increment /= 2){
? ? ? ? ? ? ? ? ?for (i = increment; i < len; i++){
? ? ? ? ? ? ? ? ? ? ? ? ? ?if (p[i] < p[i - increment]){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? temp = p[i];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? for (j = i - increment; j >= 0 && p[j] > temp; j -= increment)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? p[j + increment] = p[j];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? p[j + increment] = temp;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ?}
? ? ? ?}
}
五圆兵、堆排序-----O(nlogn)-----不穩(wěn)定
? ? ? ? ? ? ? 堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進(jìn)枢贿。
1.堆排序是利用堆（假設(shè)利用大頂堆）進(jìn)行排序的方法殉农；基本思想是，將待排序的序列構(gòu)造成一個大頂堆局荚。此時超凳，整個序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將它移走（其實就是將它與堆數(shù)組的末尾元素交換耀态，此時末尾元素就是最大值）轮傍。然后將剩余的n-1個序列重新構(gòu)造成一個堆，這樣就會得到n個元素中的次大值首装，如此反復(fù)執(zhí)行创夜，便能得到一個有序序列了。
2. C++實現(xiàn)
//堆排序
void HeapSort(int a[], int n){
//初始化堆,從最后一個有孩子節(jié)點(diǎn)的位置開始調(diào)整仙逻，最后一個有孩子節(jié)點(diǎn)的位置為(n-1)/2或n/2
? ? for (int i = n / 2; i >= 0; i--)
? ? ? ? ? ? HeapAdjusting(a, i, n);
? ? for (int i = n - 1; i>0; i--)//從最后一個節(jié)點(diǎn)開始進(jìn)行調(diào)整
? ? {
? ? ? ? ? ? ? swap(a[0], a[i]); //每次交換后都要進(jìn)行調(diào)整驰吓，交換堆頂元素和最后一個元素
? ? ? ? ? ? ? HeapAdjusting(a, 0, i);
? ? ? ? }
}
void HeapAdjusting(int a[], int root, int len) ? //大頂堆
{
int temp, child;
temp = a[root];
for (child = 2 * root + 1; child < len; child *= 2)
{
? ? ? ? ? ? if (child + 1 < len&&a[child] < a[child + 1])
? ? ? ? ? ? ? ? ? ?child++;
? ? ? ? ? ? if (temp >= a[child])
? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? a[root] = a[child];
? ? ? ? ? ? ? root = child;
}
a[root] = temp;
}
我們先看一個大數(shù)據(jù)top-K示例：
例子：搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節(jié)系奉。假設(shè)目前有一千萬個記錄（這些查詢串的重復(fù)度比較高檬贰，雖然總數(shù)是1千萬，但如果除去重復(fù)后缺亮，不超過3百萬個翁涤。一個查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門葵礼。）号阿，請你統(tǒng)計最熱門的10個查詢串，要求使用的內(nèi)存不能超過1G鸳粉。
首先扔涧，我們知道這是一個典型的top-K問題。
針對大數(shù)據(jù)問題進(jìn)行統(tǒng)計首先應(yīng)該想到的就是Hash_map赁严。所以第一步就是先遍歷全部的1千萬Query，構(gòu)建出一個大小為3百萬的Hash_map粉铐，其中的key值為某條Query疼约，對應(yīng)的value值為該條Query的查詢次數(shù)。
建好Hash_map以后蝙泼，我們接下來的問題就是如何在3百萬的Query中找出10個最熱門的Query程剥，也就是要用到排序算法。排序算法中效率最高的時間復(fù)雜度為O(n*log(n))汤踏，
這是最簡單粗暴的方法织鲸，也是最直接的方法∠海或者我們進(jìn)一步優(yōu)化搂擦，該題目是要求尋找top-K問題，那么我們可以直接去前K個Query構(gòu)建一個數(shù)組哗脖，然后
對其進(jìn)行排序瀑踢。遍歷剩余的全部Query，如果某條Query的查詢次數(shù)大于數(shù)組中最小的一個才避，將數(shù)組中最小的Query剔除橱夭，加入這條新的Query。
接著調(diào)整數(shù)組順序桑逝，依次進(jìn)行遍歷棘劣，這樣的最壞情況下的復(fù)雜度為O(n*K)。
但是還可以繼續(xù)優(yōu)化尋找top-K的操作楞遏，那就是借助小根堆來實現(xiàn)茬暇。基于以上的分析寡喝，我們想想而钞，有沒有一種既能快速查找，又能快速移動元素的數(shù)據(jù)結(jié)構(gòu)呢拘荡？回答是肯定的臼节，那就是堆。
具體過程是，堆頂存放的是整個堆中最小的數(shù)网缝，現(xiàn)在遍歷N個數(shù)巨税，把最先遍歷到的k個數(shù)存放到最小堆中，并假設(shè)它們就是我們要找的最大的k個數(shù)粉臊，X1>X2...Xmin(堆頂)草添，而后遍歷后續(xù)的(n-K)個數(shù)，一一與堆頂元素進(jìn)行比較扼仲，如果遍歷到的Xi大于堆頂元素Xmin远寸，則把Xi放入堆中，而后更新整個堆屠凶，更新的時間復(fù)雜度為logK驰后，如果Xi
一個有關(guān)小根堆解決top-K問題的小動畫，請點(diǎn)擊這個鏈接矗愧。
思想與上述算法二一致灶芝，只是算法在算法三，我們采用了最小堆這種數(shù)據(jù)結(jié)構(gòu)代替數(shù)組唉韭，把查找目標(biāo)元素的時間復(fù)雜度有O(K)降到了O(logK)夜涕。那么這樣，采用堆數(shù)據(jù)結(jié)構(gòu)属愤，算法三女器，最終的時間復(fù)雜度就降到了O(n*logK)，和算法二相比住诸，又有了比較大的改進(jìn)晓避。
六、歸并排序------O(nlogn)-------穩(wěn)定
1. 歸并排序：是將兩個（或者兩個以上）有序表合并成一個新的有序表只壳，即把待排序序列分為若干個子序列俏拱，每個子序列都是有序的。然后再把有序子序列合并為整體有序序列吼句。
2. C++實現(xiàn)代碼
//merge兩個有序數(shù)列為一個有序數(shù)列
void MergeArr(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
//通過比較锅必，歸并數(shù)列a和b
while (i <= m && j <= n)
{
? ? ? ? ?if(a[i]<a[j])
? ? ? ? ? ? ? ? ? temp[k++]=a[i++];
? ? ? ? ? else
? ? ? ? ? ? ? ? ? temp[k++]=a[j++];
?}
//將數(shù)列a或者b剩余的元素直接插入到新數(shù)列后邊
while (i <= m)
? ? ? ? ? ?temp[k++] = a[i++];
while (j <= n)
? ? ? ? ?temp[k++] = a[j++];
? for (i = 0; i<k;i++)
? ? ? ? ? ?a[first+i]=temp[i];
}
//歸并排序
void MSort(int a[], int first, int last, int temp[])
{
? ? ? ? ? if (first<last)
? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ?int mid=(first+last)/2;
? ? ? ? ? ? ? ? ? ? MSort(a, first, mid, temp);
? ? ? ? ? ? ? ? ? ? MSort(a, mid + 1, last, temp);
? ? ? ? ? ? ? ? ? ? ?MergeArr(a, first, mid, last, temp);
? ? ? ? ? }
void MergeSort(int a[], int len)//為了調(diào)用方便封裝了一個函數(shù)接口
{
? ? ? ?int *temp = new int[len];
? ? ? MSort(a, 0, len - 1, temp);
? ? ? delete temp;
}
七、快速排序------O(nlogn)-------不穩(wěn)定
? ? ? ? ? ? ? 1. 快速排序：是通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分惕艳，其中一部分記錄的關(guān)鍵字比另一部分記錄的關(guān)鍵字小搞隐，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序的目的远搪。
2.C++實現(xiàn)代碼
//快速排序
void QSort(int a[], int L, int R)
{
? ? ? ? ?if (L<R)
? ? ? ? {
? ? ? ? ? ? ? ? ? ?int low = L, high = R, pivotkey = a[low];// pivotkey：樞軸
? ? ? ? ? ? ? ? ? while (low<high)
? ? ? ? ? ? ? ? ?{//從右向左找小于基準(zhǔn)值a[i]的元素
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? while (low<high&& a[high]>=pivotkey)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?high--;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if(low<high)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?a[low++] = a[high];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //從左向右找大于基準(zhǔn)值a[i]的元素
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? while (low<high&& a[high]<pivotkey)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?low++;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?if(low<high)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? a[high--] = a[low];
? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ?//將基準(zhǔn)值填入最后的坑中
? ? ? ? ? ? ? ? ? a[low] = pivotkey;
? ? ? ? ? ? ? ? ?//遞歸調(diào)用劣纲，分治法的思想
? ? ? ? ? ? ? ? ?QSort(a, L, low - 1);
? ? ? ? ? ? ? ? QSort(a, low + 1, R);
? ? ? ? ?}
}
void QuickSort(int a[], int len)? //封裝函數(shù)接口
{
? ? ? ? ? ? ? ?QSort(a, 0, len - 1);
}
后記：
1.
（1）當(dāng)原表有序或基本有序時，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動記錄的次數(shù)谁鳍，時間復(fù)雜度可降至O（n）癞季；
（2）而快速排序則相反劫瞳，當(dāng)原表基本有序時，將蛻化為冒泡排序绷柒，時間復(fù)雜度提高為O（n^2）志于；
（3）原表是否有序，對簡單選擇排序废睦、堆排序伺绽、歸并排序和基數(shù)排序的時間復(fù)雜度影響不大。
2.
穩(wěn)定性：排序算法的穩(wěn)定性:若待排序的序列中嗜湃，存在多個具有相同關(guān)鍵字的記錄奈应，經(jīng)過排序， 這些記錄的相對次序保持不變购披，則稱該算法是穩(wěn)定的杖挣；若經(jīng)排序后，記錄的相對次序發(fā)生了改變今瀑，則稱該算法是不穩(wěn)定的程梦。
穩(wěn)定性的好處：排序算法如果是穩(wěn)定的点把，那么從一個鍵上排序橘荠，然后再從另
一個鍵上排序，第一個鍵排序的結(jié)果可以為第二個鍵排序所用郎逃「缤基數(shù)排序就是這樣，先按低位排序褒翰，逐次按高位排序贮懈，低位相同的元素其順序再高位也相同時是不會
改變的。另外优训，如果排序算法穩(wěn)定朵你，可以避免多余的比較。
穩(wěn)定的排序算法：冒泡排序揣非、插入排序抡医、歸并排序、選擇排序早敬。
不是穩(wěn)定的排序算法：快速排序忌傻、希爾排序、堆排序搞监。
3.
選擇排序算法準(zhǔn)則：
每種排序算法都各有優(yōu)缺點(diǎn)水孩。因此，在實用時需根據(jù)不同情況適當(dāng)選用琐驴，甚至可以將多種方法結(jié)合起來使用俘种。
選擇排序算法的依據(jù)：
影響排序的因素有很多秤标，平均時間復(fù)雜度低的算法并不一定就是最優(yōu)的。相反安疗，有時平均時間復(fù)雜度高的算法可能更適合某些特殊情況抛杨。同時，選擇算法時還得考慮它的可讀性荐类，以利于軟件的維護(hù)怖现。一般而言，需要考慮的因素有以下四點(diǎn)：
（1）待排序的記錄數(shù)目n的大杏窆蕖屈嗤；
（2）記錄本身數(shù)據(jù)量的大小，也就是記錄中除關(guān)鍵字外的其他信息量的大械跏洹饶号；
（3）關(guān)鍵字的結(jié)構(gòu)及其分布情況；
（4）對排序穩(wěn)定性的要求季蚂。
4.
設(shè)待排序元素的個數(shù)為n.
（1）當(dāng)n較大茫船，則應(yīng)采用時間復(fù)雜度為O(n*logn)的排序方法：快速排序、堆排序或歸并排序扭屁。
快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法算谈，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時，快速排序的平均時間最短料滥；
堆排序：如果內(nèi)存空間允許且要求穩(wěn)定性的性穿；
歸并排序：它有一定數(shù)量的數(shù)據(jù)移動钥飞，所以我們可能過與插入排序組合，先獲得一定長度的序列，然后再合并牡彻，在效率上將有所提高吴裤。
（2）當(dāng)n較大哨查，內(nèi)存空間允許究驴，且要求穩(wěn)定性：歸并排序
（3）當(dāng)n較小，可采用直接插入或直接選擇排序阻肩。
直接插入排序：當(dāng)元素分布有序带欢，直接插入排序?qū)⒋蟠鬁p少比較次數(shù)和移動記錄的次數(shù)。
直接選擇排序：當(dāng)元素分布有序磺浙，如果不要求穩(wěn)定性洪囤，選擇直接選擇排序。
（4）一般不使用或不直接使用傳統(tǒng)的冒泡排序撕氧。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Pitfall
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2016.6
