目錄

歸并排序

1.基本思想：

2.原理圖：

1）分解合并

2）數(shù)組比較和歸并方法：

3.代碼實現(xiàn)（遞歸方式）：

4.歸并排序的非遞歸方式

原理：

情況1：

情況2：

情況3：

非遞歸代碼實現(xiàn)

歸并排序的特性總結(jié)：

計數(shù)排序

基本思想：

算法原理：

算法升級

計算排序的特點：

代碼實現(xiàn)

排序算法復(fù)雜度及穩(wěn)定性分析

什么時穩(wěn)定性？

各種常見排序算法的總結(jié)

---

歸并排序

1.基本思想：

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,

該算法是采用分治法（Divide andConquer）的一個非常典型的應(yīng)用。

將已有序的子序列合并，得到完全有序的序列；

即先使每個子序列有序，再使子序列段間有序。

若將兩個有序表合并成一個有序表，稱為二路歸并。

2.原理圖：

1）分解合并

第一層將一個數(shù)組分兩個大組，

第二層再繼續(xù)分，直到分成每組都只有一個為止

分解完了之后就是進(jìn)行合并，每兩個小數(shù)組，按順序合并成一個大的數(shù)組

最終，合并稱為一個有序的集合

動圖效果：

歸并排序是在原數(shù)組上進(jìn)行的，用一個臨時數(shù)組來做歸并，把歸并好的元素復(fù)制回原數(shù)組

2）數(shù)組比較和歸并方法：

用上述長度為4的集合舉例：

第一步：比較p1和p2位置元素的大小，誰的小，將誰的值放到p位置，并將指向小的元素的那個指針++，并且將p++

1比2小，放1到p位置，p1++，p++

?......

第二步：按第一步的步驟，逐一比較，直到有一個指針走到了集合之外如下：

此時p2已經(jīng)走到了集合外，就可以退出循環(huán)了

?第三步：放一個循環(huán)，將沒走完的那個集合的剩余元素按順序放到大集合種即可

當(dāng)p走到大集合外面時結(jié)束循環(huán)

3.代碼實現(xiàn)（遞歸方式）：

//歸并排序（遞歸實現(xiàn)）//歸并子函數(shù)
//（在遇到需要malloc擴容的函數(shù)時，將malloc代碼放入主函數(shù)，另寫一個子函數(shù)用來完成遞歸）
void _MergeSort(int* a, int begin ,int end, int* temp)
{//最后只剩下一個數(shù)的時候就說明begin=end，返回if (begin >= end){return;}int mid = (begin + end) / 2;//[begin, mid] [mid+1, end] 遞歸讓子區(qū)間都有序_MergeSort(a, begin, mid, temp);    //遞歸左半?yún)^(qū)_MergeSort(a, mid+1, end, temp);    //遞歸右半?yún)^(qū)//歸并int begin1 = begin, end1 = mid;     //左區(qū)間[begin1, end1]int begin2 = mid + 1, end2 = end;   //右區(qū)間[begin2, end2]int i = begin;//如果左右兩個區(qū)間都沒有結(jié)束就繼續(xù)，只要有一個區(qū)間結(jié)束就終止while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){temp[i++] = a[begin1++]; }else{temp[i++] = a[begin2++];}}//將沒走到頭的區(qū)間按順序放到后面while (begin1 <= end1){temp[i++] = a[begin1++];}while (begin2 <= end2){temp[i++] = a[begin2++];}//將臨時區(qū)間的數(shù)據(jù)拷貝回原數(shù)組memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}//歸并主函數(shù)
void MergeSort(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, 0, n-1, temp);free(temp);temp = NULL;
}

4.歸并排序的非遞歸方式

原理：

控制每次參與歸并的元素即可，可以先定義一個變量rangeN，讓其來劃分區(qū)域

?開始時rangeN=1，區(qū)域為1則是有序，

i = i + 2*rangeN? ? ?定義 i 來區(qū)分每塊區(qū)域

左區(qū)域：[begin1,end1]? ? ? ? ? ? ? ? 右區(qū)域：[begin2,end2]

上圖情況是一個特殊情況，如果遇到不能被完全劃分左右區(qū)域?qū)ΨQ的情況分為以下三種：

情況1：

當(dāng)最后一個區(qū)域進(jìn)行歸并時，最后一組的左區(qū)間越界，所以需要對左區(qū)間的end1進(jìn)行控制

情況2：

當(dāng)最后一個區(qū)域進(jìn)行歸并時，最后一組的右區(qū)間全部越界，所以需要對右區(qū)間的begin2進(jìn)行控制

情況3：

?當(dāng)最后一個小組進(jìn)行歸并時，由于右區(qū)間越界，所以我們需要對右區(qū)間end2進(jìn)行控制

非遞歸代碼實現(xiàn)

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}// 歸并每組數(shù)據(jù)個數(shù)，從1開始，因為1個認(rèn)為是有序的，可以直接歸并int rangeN = 1;while (rangeN < n) {for (int i = 0; i < n; i += 2 * rangeN){// [begin1,end1][begin2,end2] 歸并int begin1 = i, end1 = i + rangeN - 1;int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;int j = i;// end1 begin2 end2 越界的三種情況//一定需要按順序進(jìn)行判斷，不然會出錯//end1越界，情況1，//解決：直接退出本次循環(huán)，可以不讓后面的進(jìn)行歸并，再下一次循環(huán)時再排序if (end1 >= n){break;}//begin2出界，情況2，//解決：直接退出本次循環(huán)，可以不讓后面的進(jìn)行歸并，再下一次循環(huán)時再排序else if (begin2 >= n){break;}//end2越界，情況3//解決：讓end2等于數(shù)組最后的下標(biāo)else if (end2 >= n){end2 = n - 1;}//開始按順序歸并while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}// 歸并一部分，拷貝一部分memcpy(a + i, tmp + i, sizeof(int)*(end2 - i + 1));}rangeN *= 2;}free(tmp);tmp = NULL;
}

歸并排序的特性總結(jié)：

1. 歸并的缺點在于需要O(N)的空間復(fù)雜度，
   歸并排序的思考更多的是解決在磁盤中的外排序問題。
2. 時間復(fù)雜度：O(N*logN)
3. 空間復(fù)雜度：O(N)
4. 穩(wěn)定性：穩(wěn)定

計數(shù)排序

基本思想：

之前學(xué)習(xí)的排序，無論是希爾排序，還是堆排序，都用的是比較兩個數(shù)大小的方式進(jìn)行的排序

而計數(shù)排序不是用比較的方法來進(jìn)行排序的，它利用的是數(shù)組下標(biāo)的計數(shù)來進(jìn)行的排序

具體實現(xiàn)方法如下：

算法原理：

現(xiàn)假設(shè)有一組0~4的數(shù)據(jù)需要排序：{ 2，3，3，4，0，3，2，4，3 }

創(chuàng)建一個臨時數(shù)組temp來依次記錄每個數(shù)的出現(xiàn)次數(shù)

原數(shù)組中，

? ? ? ? 0出現(xiàn)了1次，就在temp下標(biāo)為0的位置記錄1

? ? ? ? 1沒有出現(xiàn)，? 就在temp下標(biāo)為1的位置記錄0

? ? ? ? 2出現(xiàn)了2次，就在temp下標(biāo)為0的位置記錄2

? ? ? ? 3出現(xiàn)了4次，就在temp下標(biāo)為0的位置記錄3

? ? ? ? 4出現(xiàn)了2次，就在temp下標(biāo)為0的位置記錄2

數(shù)組每一個下標(biāo)位置的值，代表了數(shù)列中對應(yīng)整數(shù)出現(xiàn)的次數(shù)。

有了這個 “統(tǒng)計結(jié)果”，排序就很簡單了。
直接遍歷數(shù)組，輸出數(shù)組元素的下標(biāo)值，元素的值是幾，就輸出幾次：

這樣就能得到一個有序序列了

這就是計數(shù)排序的過程，因為他沒有進(jìn)行數(shù)與數(shù)之間的比較，
所以他的性能甚至快過那些O( log N)?的排序

可以看到上面的排序是一種特殊情況，那如果我們要排序的數(shù)組是? 9000~9009，那么是不是得浪費前九千多個空間？

又或者是在原數(shù)組里面有負(fù)數(shù)的情況下是不是九不能進(jìn)行計數(shù)排序了？

這就要對現(xiàn)有的算法進(jìn)行一些小小的升級了

算法升級

例如我們有一組這樣的數(shù)：9004，9001，9002，9005，9004，9001

這個數(shù)組，最大是9005，但最小的數(shù)是9001，如果用長度為9005的數(shù)組，那么按照上面的方法排序，肯定會太過浪費

事實上我們只需要開辟大小為5的數(shù)組即可（最大數(shù) -?最小數(shù) + 1）9005 - 9001 +1 = 5

用下標(biāo)為0的記錄9001，用下標(biāo)為4的記錄9005

當(dāng)然，對于負(fù)數(shù)也一樣可以使用，這里就不一一展示了

計算排序的特點：

1. 穩(wěn)定性：穩(wěn)定
2. 時間復(fù)雜度：O（n+k）
3. 空間復(fù)雜度：O（n+k）

對于數(shù)據(jù)率不是很大，并且數(shù)據(jù)比較集中時，計數(shù)排序是一個很有效的排序算法

計數(shù)排序的局限性：

不能對小數(shù)進(jìn)行排序，只適用于整數(shù)

代碼實現(xiàn)

分4步實現(xiàn)

1. 找到數(shù)組中的最大最小值
2. 計算范圍，開辟臨時數(shù)組空間
3. 統(tǒng)計相同元素出現(xiàn)次數(shù)
4. 根據(jù)計數(shù)結(jié)果將序列依次放回原來的數(shù)組中

//計數(shù)排序
void CountSort(int* a, int n)
{//確定數(shù)組里面的最大最小值int max = a[0], min = a[0];for (int i = 1;i < n;i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}//范圍 = 最大值 - 最小值 + 1//比如從 0 到 9 有10個數(shù)int range = max - min + 1;//用calloc開辟range個大小為int的空間，并給每個元素賦值為0int* countA = (int*)calloc(range, sizeof(int));if (countA == NULL){perror("calloc fail");exit(-1);}//統(tǒng)計相同元素出現(xiàn)的次數(shù)for (int i = 0;i < n;i++){//a[i] - min 是a[i]下標(biāo)在countA里面對應(yīng)的相對位置countA[a[i] - min]++;}//排序，根據(jù)計數(shù)結(jié)果將序列依次放回原來的數(shù)組中int k = 0;for (int j = 0;j < range;j++){while (countA[j]--){//j + min 就是數(shù)組元素的大小a[k++] = j + min;}}free(countA);
}

排序算法復(fù)雜度及穩(wěn)定性分析

什么時穩(wěn)定性？

穩(wěn)定性的價值：

比如再考試排名的時候，第三名種有三個人的成績相同，那么如果先交卷的人是第三名的話，就要去再成績排序的時候保證其穩(wěn)定性

各種常見排序算法的總結(jié)