目錄

前言：

快速排序

快速排序非遞歸實現(xiàn)

快速排序特性總結

歸并排序

歸并排序的代碼實現(xiàn)

歸并排序的特性總結

計數(shù)排序

計數(shù)排序的代碼實現(xiàn)

計數(shù)排序的特性總結

---

前言：

前文快速排序采用了遞歸實現(xiàn)，而遞歸會開辟函數(shù)棧幀，遞歸的深度越深，占用棧區(qū)的空間就越大，棧區(qū)的大小一般是8M，10M，當遞歸深度足夠深時，棧區(qū)的空間就會被用完，導致棧溢出，此時需要將遞歸改為非遞歸更加穩(wěn)妥，本篇繼續(xù)詳細解讀快排的非遞歸實現(xiàn)，歸并排序，計數(shù)排序；

快速排序

快速排序非遞歸實現(xiàn)

• 采用遞歸實現(xiàn)快速排序時，而遞歸就是不斷調(diào)用單趟排序函數(shù)的功能，若不采用遞歸，什么可以實現(xiàn)不斷調(diào)用單趟排序函數(shù)的功能？
• 循環(huán)；
• 循環(huán)只要滿足循環(huán)條件，就會不斷調(diào)用單趟排序函數(shù)的功能，但是每次遞歸調(diào)用時單趟排序函數(shù)的參數(shù)是變化的，而循環(huán)條件確是一成不變的，遞歸會在棧上建立函數(shù)棧幀，而函數(shù)棧幀里面存放下次調(diào)用該函數(shù)的參數(shù)，若采用非遞歸，那我們就必須把每一次循環(huán)的參數(shù)記錄下來，供單趟排序使用，如何解決？
• ?使用順序?；蛘哝準綏Ｓ涗浢看魏瘮?shù)參數(shù)，棧的實現(xiàn)采用動態(tài)內(nèi)存開辟，存儲空間是堆區(qū)開辟的空間，堆區(qū)大小可達2G；

快速排序非遞歸實現(xiàn)步驟：

1. 創(chuàng)建一個棧，將整個序列的起始位置和結束位置入棧；
2. 當棧不為空時，彈出棧頂元素，取出該區(qū)間的起始位置 left 和結束位置 right；
3. 對該區(qū)間進行劃分，獲取劃分點 keyi；
4. 如果keyi左邊還有元素，將左半部分的起始位置left和結束位置keyi-1入棧；
5. 如果keyi右邊還有元素，將右半部分的起始位置keyi+1和結束位置right入棧；
6. 重復步驟2-5，直到棧為空；

• ?棧的特性為后入先出，先將待排序序列的右邊界 right入棧，后將待排序序列的左邊界left入棧；出棧時（獲取棧頂元素）就可以先取到左邊界值left ，后取到右邊界值right；

• ?先獲取棧頂元素，然后出棧，先取到0給left，后取到7給right，進行單趟排序(hoare版本）

• ?區(qū)間被劃分為【left,keyi-1】 U keyi U 【keyi+1, right】(left=0, keyi-1=3,keyi+1=5,right=7),為了先處理劃分后的左子序列，先將右子區(qū)間的邊界值right keyi+1分別入棧（先入right，后入keyi+1) ，然后將左子區(qū)間的邊界值keyi-1，left分別入棧（先入keyi-1,? 后入left)；

• ?先取棧頂元素，然后出棧，先取到的元素給left ，后取到的元素給right (left=0, right=3), 進行單趟排序(hoare版本)；

• ?keyi左邊沒有元素，keyi右邊還有元素，將右半部分的起始位置keyi+1和結束位置right入棧（right先入棧，keyi+1后入棧）

• ??先取棧頂元素，然后出棧，先取到的元素給left ，后取到的元素給right (left=1, right=3), 進行單趟排序(hoare版本)；

• ?keyi左邊沒有元素，keyi右邊還有元素，將右半部分的起始位置keyi+1和結束位置right入棧（right先入棧，keyi+1后入棧）

?

• 左子區(qū)間全部被排完，此時才可以取出5和7排右子區(qū)間，右子區(qū)間按相同流程處理即可；

順序棧與鏈式棧的實現(xiàn)：順序棧與鏈式棧_順序棧和鏈棧-CSDN博客

//快排非遞歸實現(xiàn)
void QuickSortNonR(int* a, int begin, int end)
{Stack st;InitStack(&st);StackPush(&st, end);StackPush(&st, begin);while (!StackEmpty(&st)){int left = StackTop(&st);StackPop(&st);int right = StackTop(&st);StackPop(&st);int keyi = PartSort(a, left, right);//[left keyi-1] keyi [keyi+1 right]if (right > keyi + 1){StackPush(&st, right);StackPush(&st, keyi+1);}if (keyi - 1 > left){StackPush(&st, keyi - 1);StackPush(&st, left);}}DestroyStack(&st);
}

快速排序特性總結

1. 時間復雜度

因為每次排序都將待排序序列分成兩部分，每部分的長度大約為原序列的一半，因此需要進行l(wèi)ogn次排序，每次排序的時間復雜度為O(n)，所以快速排序的時間復雜度為O(n*logn)；

2. 空間復雜度

因為每次排序需要使用遞歸調(diào)用，每次調(diào)用需要使用一定的?？臻g，所以快速排序的空間復雜度為O(logn)；

3. 算法穩(wěn)定性

快速排序的算法不穩(wěn)定，這是因為在排序過程中，可能會出現(xiàn)相同元素的相對位置發(fā)生變化的情況；當待排序序列中存在多個相同的元素時，快速排序可能會將它們分到不同的子序列中，從而導致它們的相對位置發(fā)生變化；

歸并排序

歸并排序的基本思想：

將待排序的序列分成若干個子序列，每個子序列都是有序的，然后再將這些有序的子序列合并成一個大的有序序列；

具體實現(xiàn)過程通常采用遞歸的方法，將序列遞歸地分成兩半，對每一半分別進行歸并排序，最后將兩個有序的子序列合并成一個有序的序列；在合并的過程中，需要開辟一個數(shù)組來存儲合并后的序列，然后再將臨時數(shù)組中的元素拷貝回原數(shù)組中；

歸并排序的基本思想可以總結為以下三個步驟：

1. 分割：將待排序的序列分成若干個子序列，每個子序列都是有序的；
2. 合并：將有序的子序列歸并到開辟后的數(shù)組形成一個大的有序序列；
3. 復制：將臨時數(shù)組中的元素復制回原數(shù)組中；

歸并排序的實現(xiàn)步驟：

1. 分割：將待排序數(shù)組從中間位置分成兩個子數(shù)組，直到每個子數(shù)組只有一個元素為止；
2. 歸并：將兩個有序子數(shù)組合并成一個大的有序數(shù)組；
   • 開辟一個新數(shù)組，新數(shù)組的大小與原數(shù)組大小相同，定義三個指針，分別指向兩個子數(shù)組和新數(shù)組；
   • 比較兩個子數(shù)組的第一個元素，將較小的元素放入新數(shù)組中，并將指向該元素的指針向后移動一位；
   • 重復上一步，直到其中一個子數(shù)組的元素全部放入新數(shù)組中；
   • 將另一個子數(shù)組中剩余的元素依次放入新數(shù)組中；

歸并排序的代碼實現(xiàn)

//歸并排序(遞歸)
//將待排序序列不斷二分，直到每個子序列只有一個元素為止,只有一個元素,序列一定有序;
//將相鄰的兩個子序列合并成一個有序的序列，直到所有子序列都被合并成一個完整的序列;
void SubMergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;//劃分區(qū)間為[begin,mid]U[mid+1,end]int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;//遞歸終止的條件為區(qū)間只包含一個元素或者區(qū)間不存在;//后序遍歷SubMergeSort(a, tmp, begin1, end1);SubMergeSort(a, tmp, begin2, end2);
//首先歸并到tmp數(shù)組,然后拷貝到原數(shù)組;int index = begin;//tmp數(shù)組下標while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}//begin1>end1與begin2>end2至少有一個發(fā)生while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}//拷貝到原數(shù)組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;}SubMergeSort(a, tmp, 0, n - 1);
}

歸并排序的特性總結

1. 時間復雜度

歸并排序的時間復雜度可以通過遞歸樹來分析；在遞歸樹中，每個節(jié)點表示對一個區(qū)間進行排序的時間復雜度，而每個節(jié)點的子節(jié)點表示對該區(qū)間的兩個子區(qū)間進行排序的時間復雜度，因此，遞歸樹的深度為logn，每層的時間復雜度為O(n)，因此歸并排序的時間復雜度為O(nlogn)；

2. 空間復雜度

歸并排序的空間復雜度為O(n)，因為在排序過程中需要創(chuàng)建一個長度為n的臨時數(shù)組來存儲排序結果；

3. 算法穩(wěn)定性

歸并排序是一種穩(wěn)定的排序算法，因為在合并兩個有序子序列的過程中，如果兩個元素相等，那么先出現(xiàn)的元素會先被放入結果數(shù)組中，保證了排序的穩(wěn)定性；

計數(shù)排序

計數(shù)排序的基本思想：

計數(shù)排序不是一個基于比較的排序算法，是記錄數(shù)據(jù)出現(xiàn)次數(shù)的一種排序算法；計數(shù)排序使用一個額外的count數(shù)組，其中第i個元素是待排序數(shù)組中值等于i的元素的個數(shù)，然后根據(jù)count數(shù)組來將待排序數(shù)組中的元素排到正確的位置；

計數(shù)排序的實現(xiàn)步驟：

1. 遍歷原數(shù)組，找出原數(shù)組中的最大值max，最小值min；
2. 創(chuàng)建count數(shù)組，數(shù)組大小為max-min+1，并將其元素初始化為0；
3. 將原數(shù)組里面的值減去原數(shù)組最小值min作為count數(shù)組的下標映射下來,而count數(shù)組里面存放的值就是原數(shù)組里面值出現(xiàn)的次數(shù)；
4. 從前向后依次填充數(shù)組，填充數(shù)組時，只需要加上這個最小值，就能還原出原來的值；

計數(shù)排序的代碼實現(xiàn)

//計數(shù)排序
void CountSort(int* a, int n)
{//尋找最大值,最小值int min = a[0];int max = a[0];for (int i = 0; i < n; i++){if (a[i] < min)min = a[i];if (a[i]>max)max = a[i];}//確定新數(shù)組count的大小int range = max - min + 1;int* count = (int*)malloc(sizeof(int)*range);if (count == NULL){perror("malloc failed:");return;}//新數(shù)組全部初始化為0,方便計數(shù)memset(count, 0, sizeof(int)*range);//統(tǒng)計數(shù)據(jù)出現(xiàn)的次數(shù)for (int i = 0; i < n; i++){count[a[i] - min]++;}//從前向后依次填充原數(shù)組int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}free(count);
}

計數(shù)排序的特性總結

1. 時間復雜度

計數(shù)排序的時間復雜度與待排序元素的范圍相關，其時間復雜度為O(n+k),其中n為元素數(shù)量，k為元素的范圍（即最大的元素與最小的元素的差加1）；

2. 空間復雜度

計數(shù)排序需要額外開辟的空間大小k=max+min-1，所以空間復雜度為O(k)；

3. 算法穩(wěn)定性

計數(shù)排序是一個非基于比較的線性時間排序算法，是一種穩(wěn)定排序；