?=========================================================================
主頁點(diǎn)擊直達(dá)：個(gè)人主頁
我的小倉庫：代碼倉庫
C語言偷著笑：C語言專欄
數(shù)據(jù)結(jié)構(gòu)挨打小記：初階數(shù)據(jù)結(jié)構(gòu)專欄
Linux被操作記：Linux專欄
LeetCode刷題掉發(fā)記：LeetCode刷題
算法頭疼記：算法專欄?
=========================================================================
目錄
前言
歸并排序
?遞歸實(shí)現(xiàn)代碼
非遞歸實(shí)現(xiàn)歸并排序
計(jì)數(shù)排序
排序算法復(fù)雜度及穩(wěn)定性分析
前言
上兩篇文章講解了插入排序、選擇排序以及交換排序，每種類型的排序大類下都有一到兩種排序，今天給大家?guī)淼氖?span style="color:#fe2c24;">歸并排序，和前面幾種排序一樣都屬于比較排序中的一種，是通過比較數(shù)組中的元素來實(shí)現(xiàn)排序的，還給大家?guī)硪环N非比較排序計(jì)數(shù)排序，讓我們開始今天的排序之吧?。?！
歸并排序
基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。歸并排序核心步驟：?
這張圖片看起來是不是非常眼熟？和上篇文章的快速排序非常的相似，歸并排序也是一種類似與二叉樹結(jié)構(gòu)的排序，我們也是使用遞歸的思想來實(shí)現(xiàn)，歸并排序是先將一整個(gè)亂序的數(shù)組分成若干個(gè)數(shù)組（極限情況下每一個(gè)數(shù)字可以看成一個(gè)數(shù)字）然后將每個(gè)有序的數(shù)組進(jìn)行有序的合并，通過多次合并最終成為一個(gè)有序的數(shù)組。
?遞歸實(shí)現(xiàn)代碼
void _MergerSort(int* a, int* tmp,int begin, int end ) { if (begin >= end) { return; } int mid = (end + begin) / 2; //[begin,mid] [mid+1,end] _MergerSort(a, tmp, begin, mid); _MergerSort(a, tmp, mid + 1, end); //歸并到tmp數(shù)組 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int index = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1]< a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp =(int *) malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc failed"); return; } //不可以自己遞歸，因?yàn)槊看味家_辟新的空間 _MergerSort(a, tmp, 0, n - 1); free(tmp); }?
遞歸實(shí)現(xiàn)排序確實(shí)優(yōu)點(diǎn)難理解，大家可以根據(jù)我畫的圖和代碼結(jié)合起來自己多多畫圖理解。
非遞歸實(shí)現(xiàn)歸并排序
上篇文章的快速排序我們可以使用棧數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，但是歸并排序我們很難用棧數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，普通的方法實(shí)現(xiàn)起來也不難，遞歸是將一整個(gè)數(shù)組分成若干數(shù)組（極限情況下每一個(gè)數(shù)字是一個(gè)數(shù)組）來實(shí)現(xiàn)分治，最后歸并。我們逆向著來，根據(jù)控制數(shù)組的下標(biāo)來直接實(shí)現(xiàn)歸并。
非遞歸實(shí)現(xiàn)代碼
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc failed"); return; } int gap = 1; while (gap < n) { //11歸并 22歸并 44歸并 for (int i = 0; i < n;i=i+2*gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; int index = i; //防止越界，防止只能排序個(gè)數(shù)為2的倍數(shù) //當(dāng)begin2大于等于數(shù)組個(gè)數(shù)時(shí)end2一定越界了 if (begin2 >= n) { break; } if (end2 >= n) { end2 = n - 1; } while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a + i, tmp + i, (end2-i+1) * sizeof(int)); } gap *= 2; } free(tmp); }在對(duì)數(shù)組進(jìn)行操作時(shí)我們一定要注意越界問題，下面是解決上面問題的圖解。?
因此當(dāng)end2越界時(shí)但begin2沒越界時(shí)我們將end2調(diào)到n-1的位置時(shí)候就可以了。
歸并排序的特性總結(jié)：
1. 歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序題。
2. 時(shí)間復(fù)雜度：O(N*logN)
3. 空間復(fù)雜度：O(N)
4. 穩(wěn)定性：穩(wěn)定
計(jì)數(shù)排序
思想：計(jì)數(shù)排序又稱為鴿巢原理，是對(duì)哈希直接定址法的變形應(yīng)用。
操作步驟：
1. 統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)
2. 根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來的序列中
開辟一個(gè)新的數(shù)組利用數(shù)組下標(biāo)統(tǒng)計(jì)原數(shù)組中每個(gè)數(shù)出現(xiàn)的次數(shù)，因?yàn)闀r(shí)從小到大統(tǒng)計(jì)的因此直接將每個(gè)數(shù)字放在原數(shù)組中即可，如果原數(shù)組全是大數(shù)據(jù)呢？開辟空間的大小是個(gè)問題，因此我們先遍歷數(shù)組找到最大值和最小值做差作為我們開辟空間大小的基準(zhǔn)，每個(gè)數(shù)的代表下標(biāo)=數(shù)組元素-最小值。
實(shí)現(xiàn)代碼
void CoutSort(int* a, int n) { int max = a[0]; int min = a[0]; //遍歷數(shù)組求出最大值 for (int i = 0; i < n; i++) { if (max < a[i]) { max = a[i]; } if (min > a[i]) { min = a[i]; } } //根據(jù)最大值和最小值的差值開辟空間 int range = max - min+1; int* cout = (int*)malloc(sizeof(int) * range); if (cout == NULL) { perror("malloc failed"); return; } //將開辟的空間所有值置為0 memset(cout, 0, sizeof(int) * range); for (int i = 0; i < n; i++) { //計(jì)數(shù) //防止數(shù)值過大 cout[a[i] - min]++; //3 4 5 6 7 8 9 10 //0 1 2 3 4 5 6 7 //2 1 1 2 1 1 2 1 } int j = 0; for (int i = 0; i < range; i++) { while (cout[i]--) { a[j++] = i + min; } } }?計(jì)數(shù)排序的特性總結(jié)：
1. 計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場(chǎng)景有限。
2. 時(shí)間復(fù)雜度：O(MAX(N,范圍))
3. 空間復(fù)雜度：O(范圍)
排序算法復(fù)雜度及穩(wěn)定性分析
文章來源：http://www.zghlxwxcb.cn/news/detail-715483.html
?經(jīng)典的幾大排序本片文章就徹底完結(jié)了，大家可以根據(jù)這三篇文章對(duì)排序有新的認(rèn)識(shí)。希望大家閱讀完可以有所收獲，同時(shí)也感謝各位看官的三連支持。文章有問題可以直接留言，我一定及時(shí)認(rèn)真的修改。?文章來源地址http://www.zghlxwxcb.cn/news/detail-715483.html
到了這里，關(guān)于【算法】排序——?dú)w并排序和計(jì)數(shù)排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
