數據結構-歸并排序+計數排序

1.歸并排序

基本思想：
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。歸并排序核心步驟：

相當于每次把待排數據分為兩個子區間，如果每個子區間有序，再讓兩個子區間歸并起來也有序，那整體就有序了。我們可以按照二叉樹的思想，把子區間再分為兩份，使子區間的子區間有序.......直到子區間分無可分為止。

具體過程如下：

那該如何讓兩個有序子區間歸并呢？

直接在數組中肯定不行，這樣會發生數據的覆蓋。所以我們可以像之前合并兩個有序數組一樣，另外開辟一個空間tmp，依次比較兩個有序子區間的值，每次比較后把較小的放在tmp中，如果其中一個子區間提前結束，就把另外一個子區間的剩余的數據全放進tmp，最后把tmp中的數據拷貝回原數組。

使用遞歸實現：
#include<stdio.h>
#include<stdlib.h>
void _MegeSort(int* a, int begin, int end,int*tmp)
{//只剩一個數據，遞歸結束if (begin == end){return;}int mid = (begin + end) / 2;//遞歸子區間，分為兩部分_MegeSort(a, begin, mid, tmp);_MegeSort(a, mid+1, end, tmp);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int j = begin;//兩部分比較，每次小的放入tmpwhile (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}//哪部分有剩余，全部放入tmpwhile (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//拷貝到原數組memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MegeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MegeSort(a, 0, n - 1, tmp);free(tmp);
}void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ",a[i]);}printf("\n");
}
int main()
{int a[] = { 1,4,9,6,3,5,2,8,10,7,11,1};MegeSort(a, sizeof(a) / sizeof(int));Print(a, sizeof(a) / sizeof(int));return 0;
}
注意：

1.?因為每次遞歸的子區間都不一定是從0開始的，所以我們拷貝數據時，最好從begin的位置開始：
//拷貝到原數組
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
2. 在代碼中j作為tmp的坐標，每次往tmp中放入數據后都要加一，但不能初始化為0，否則每次遞歸進入，j的值都會清0，所以最好初始化：j=begin

歸并排序的復雜度：

時間復雜度：O(N*logN)

歸并排序每次遞歸都要把待排數據分為兩份，相當于二分法，那一共有logN層遞歸，而每次遞歸都要比較數據，要把每個數據都遍歷一遍，每層的時間復雜度就是O(N)，所以總共的時間復雜度是O(N*logN)。

空間復雜度：O(N)?

剛開始就開辟了空間，此時就已經是O(N)了，而遞歸過程中函數棧幀的創建是logN，所以總的空間復雜度是：O(N+logN)，但是量級沒變，還是O(N)。

2.非遞歸實現歸并排序

非遞歸實現歸并排序，我們只需模擬上述的遞歸過程即可，把遞歸過程轉換為：把數據先分為2個一組，全部歸并一遍，拷貝回原數組，然后4個一組，全部歸并一遍，拷貝回原數組，再8個一組，?全部歸并一遍，拷貝回原數組，

那我們就可以設置一個gap，兩個數據為一組時，gap=1，每歸并一組數據就往后跳2*gap步，直到全部歸并一遍，再次分組，這次gap=2，每歸并一組數據往后跳2*gap步，直到全部歸并一遍，下次gap=4，跳2*gap步.....，直到gap>n就停止，

代碼如下：
void MegeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}int gap = 1;while (gap < n){int j = 0;for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//兩部分比較，每次小的放入tmpwhile (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}//哪部分有剩余，全部放入tmpwhile (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}}memcpy(a, tmp, sizeof(int) * n);gap *= 2;}free(tmp);
}
測試一下：

上面結果看起來，我們排序成功了，但是上述代碼真的對嗎？

上面代碼我們在測試時用的是8個數據，但是如果用9個、10個等，就會發現排序并不會成功，可能程序還會崩掉，這是為什么呢？

因為我們在分組時，是按照固定的2的次方分的，一旦數據個數不是2、4、8的次方，后面歸并時就會發生越界問題。

下面我們給10個數據打印一下邊界，會發現，有三種越界的方式，：

那我們對這三種情況分別做一下處理：

第1、2種情況出現時，我們直接break，第三種情況，我們修改邊界，令end2=n-1，但是注意直接break后，第1、2種情況往tmp中歸并時會少一部分數據（如上圖藍框所示），所以最后把tmp的數據往a中拷貝時，不能一次性全部拷貝回去，否則a中這些數據就永遠丟失了，所以最好歸并一段，拷貝一段，這樣拷貝過去的數據只會把前面的數據覆蓋，沒參與歸并的數據還在a中。

代碼如下:
void MegeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}int gap = 1;while (gap < n){int j = 0;for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (end1 >= n || begin2 >= n){break;}//修正if (end2 >= n){end2 = n - 1;}//兩部分比較，每次小的放入tmpwhile (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}//哪部分有剩余，全部放入tmpwhile (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//歸并一段，拷貝一段memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));}gap *= 2;}free(tmp);
}

3.計數排序

基本思想：

1. 統計每個數據出現的次數。

2. 根據數據的次數排序。?

如果我們要排序的數在0~9之間，我們可以像上面一樣開辟10個int大小的空間，統計待排數據中每個數據的個數，在開辟出的數組的相應下標處計數，那如果我們要排序的數據在100~109之間呢？難道開辟110個空間嗎？

當然不是，我們可以做相對映射，在開辟空間之前，先找到待排數據中的最小值和最大值，開辟空間的大小就是：sizeof(int)*(max-min+1)，開辟出的數組下標應該是：0~9，0~9下標的位置分別對應的是100~109，計數時，在下標為該數據減待排數據中的最小值的位置統計次數，例如：109就在109-100=9的下標處統計次數，統計完排序的時候再加上最小值即可。

代碼如下：
#include<stdio.h>
#include<stdlib.h>
void CountSort(int* a, int n)
{int min = a[0], max = a[0];//找最大值和最小值for (int i = 0; i < n; i++){if (a[i] < a[0]){min = a[i];}if (a[i] > a[0]){max = a[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);memset(count, 0, sizeof(int) * range);//計數for (int i = 0; i < n; i++){count[a[i] - min]++;}//排序int k = 0;for (int j = 0; j < range; j++){while (count[j]--){a[k++] = j + min;}}
}
//打印函數
Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
int main()
{int a[] = { 6,1,6,7,9,6,4,5,6,1 };CountSort(a, sizeof(a) / sizeof(int));Print(a, sizeof(a) / sizeof(int));return 0;
}