快速排序和歸并排序一般都是用遞歸來實現的，但是掌握非遞歸也是很重要的，說不定在面試的時候面試官突然問你快排或者歸并非遞歸實現，遞歸有時候并不好，在數據量非常大的時候效率就不好，但是使用非遞歸結果就不一樣了，總之各有各的好。

目錄

快速排序非遞歸實現

?歸并排序非遞歸實現

計數排序?

---

快速排序非遞歸實現

要實現快排的非遞歸需要借助棧，將區間存入棧中，在快排的遞歸中先是對整個區間單趟排序，把key值放到最終位置，在非遞歸中與遞歸的思想不變，先手搓一個棧，當然這里博主以前寫過，直接復制粘貼就行，有了棧就先對棧進行初始化，將整個區間壓棧，先壓左區間，再壓右區間，根據棧的特性“先進后出”，在一個循環中出棧再壓棧，每次出棧和壓棧都是一個區間，出棧就對該區間進行排序，排序好后就返回該一個值，這個值就是排序好的值的下標，以該下標為分界分為兩個區間，再開始進行排序，循環往復，直到棧中沒有數據退出循環，最后銷毀棧。

int PartSort(int* a, int left, int right)
{if (left >= right)return -1;int prev = left, cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi]){prev++;Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[keyi], &a[prev]);return prev;	
}void PartSortR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, left);STPush(&st, right);int begin = left, end = right;while (!STEmpty(&st)){end = STTop(&st);STPop(&st);begin = STTop(&st);STPop(&st);int keyi = PartSort(a, begin, end);//對一個區間單趟排序if (keyi+1 < end){STPush(&st, keyi + 1);STPush(&st, end);}if (keyi > begin){STPush(&st, begin);STPush(&st, keyi);}}STDestory(&st);
}

?在實現快排非遞歸時，單趟排序可以用hoare版本或者挖坑法以及前后指針法，這里使用的是前后指針法，在出棧和壓棧都是兩個數據，代表區間。

?歸并排序非遞歸實現

非遞歸的歸并排序和遞歸歸并排序的思想一樣，將一個大的問題分成一個一個小問題，將一串數據先通過分解來分成一個一個，再進行合并，在合并過程中比較大小，再放入一個新的數組中，最后把新數組拷貝到原來的數組，而非遞歸也是如此，只不過不需要和遞歸一樣分解，我們直接設置間距gap，一開始gap等于1，每個數據單獨為一組，每個數據進行比較，放入新數組，gap等于2，每兩個數據為一組，與下一組進行比較，每次gap需要乘以2，直到gap大于或者等于數據個數就結束，對數組的拷貝可以是在全部結束之后拷貝，也可以是部分拷貝只不過要拷貝多次。

因為gap每次都是乘以2，所以在數據個數不是2的n次方時會出現越界訪問，需要對該問題解決，可以通過調試解決，但是這里有一個小技巧，我們可以打印出區間，更好的看出哪個區間出現了越界訪問。

錯誤代碼：

void MergesortR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){int j = 0;for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i - 1 + gap;int begin2 = i + gap, end2 = i + 2 * gap - 1;printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);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++];}}printf("\n");memcpy(a, tmp, sizeof(int) * n);gap *= 2;}free(tmp);
}

這里數據是9個，看運行結果：

?這里可以看出gap為不同值時比較的區間，這里有三種情況：

1、begin2越界訪問了，begin2越界end2肯定也越界了。

2、end1越界了，begin2和end2肯定也越界了。

3、end2越界了。

所以只需要根據這三種情況對癥下藥：

1.當begin2越界了，就把begin2調成end2大的數就可以，因為end2 大于begin2就不會進入下面的循環，也就不會越界訪問。

2.當end1越界了，就把end1調成邊界值就可以，begin2 和 end2 就和第一種情況一樣的解決方法。

3.end2越界了就只需要將end2調成邊界就好了。

調整代碼：

void MergesortR(int* a,int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){int j = 0;for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i - 1 + gap;int begin2 = i + gap, end2 = i + 2 * gap - 1;//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);if (end1 > n - 1){end1 = n-1;begin2 = n + 1;end2 = n;}else if (end2 > n - 1){end2 = n - 1;}else if (begin2 > n - 1){end2 = n;begin2 = n + 1;}//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);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++];}}//printf("\n");memcpy(a, tmp, sizeof(int) * n);gap *= 2;}free(tmp);
}

?運行結果：

最后不要忘記釋放向操作系統申請的空間，有借有還才行。?

計數排序?

思想：計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。
1. 統計相同元素出現次數
2. 根據統計的結果將序列回收到原來的序列中

代碼展示：

//計數排序
void Countsort(int* a, int n)
{int max = a[0], min = a[0];for (int i = 0; i < n; i++){if (max < a[i]){max = a[i];}if (min > a[i]){min = a[i];}}int k = max - min+1;int *CountA = (int*)calloc(k, sizeof(int));if (CountA == NULL){perror("calloc fail");return;}for (int i = 0; i < n; i++){CountA[a[i] - min]++;}int j = 0;for (int i = 0; i < k; i++){while (CountA[i]--){a[j++] = i + min;}}
}

寫計數排序最好不要寫絕對位置，相對位置是最好的，絕對位置就是1就是在新數組對應的就是下標為1的位置，當數據中有負數時就會出現越界?，相對位置就是在統計某個值時，放入新數組時將該值減去這組數據中的最小值，所以需要找出該組數據中的最大和最小值，那么新數組的大小就是最大值減去最小值加一，當統計數據出現的個數時需要減去最小值，因為最小值減去最小值等于0，也就是新數組的下標范圍是0~最大值減去最小值。當完成以上操作就可以開始排序了，從新數組起始位置開始也就是0，將下標值加上最小值放入原來數組，循環次數就是在該下標對應值，如果CountA[i]等于0，說明i+最小值這個值不存在。

計數排序的特性總結：
1. 計數排序在數據范圍集中時，效率很高，但是適用范圍及場景有限。
2. 時間復雜度：O(MAX(N,范圍))
3. 空間復雜度：O(范圍)