🌈個人主頁：Yui_
🌈Linux專欄：Linux
🌈C語言筆記專欄：C語言筆記
🌈數(shù)據(jù)結(jié)構(gòu)專欄：數(shù)據(jù)結(jié)構(gòu)

1 快速排序非遞歸

利用迭代的方式來模仿遞歸，快速排序遞歸的本質(zhì)也就是它可以拿到那些待排序的區(qū)間，那么不就說明了只要我們右那些待排序的區(qū)間就可以不再需要遞歸了。
為此我們只需要用一個容器來存儲這些區(qū)間就可以了，在眾多的數(shù)據(jù)結(jié)構(gòu)中我選擇利用棧來實現(xiàn)這個方法，如果你要用隊列也可以，只是存儲區(qū)間而已。那么如何獲取這些區(qū)間呢？
正常情況我們只有整個數(shù)組的區(qū)間，然后我們對這個區(qū)間"排序"，拿到基準(zhǔn)值后新的區(qū)間就又出現(xiàn)了，新的區(qū)間就是區(qū)間的左端到該基準(zhǔn)值-1的位置即[left,key-1],同理另一個就是[key+1,right]。好像和遞歸差不多，每次就是差不多，快速排序的邏輯是不會變的，我們只把原來的遞歸處理改成了迭代。
將區(qū)間保存到棧中可以寫一個結(jié)構(gòu)體，也可以直接傳，取出時也一次取兩個就可以了，不影響的。

//非遞歸版本
void QuickSortNonR(int* a, int begin, int end)
{stack s;InitStack(&s);//先入left再入rightPushStack(&s, begin);//注意傳入?yún)^(qū)間的順序與取出時相反PushStack(&s, end);while (!EmptyStack(&s))//只要棧不為空就繼續(xù)循環(huán){int right = TopStack(&s);PopStack(&s);int left = TopStack(&s);PopStack(&s);int mid = PartSort1(a, left, right);//此處調(diào)用的是hoare法，其他法都可以if (mid + 1 < right)//保證區(qū)間的有效性{PushStack(&s, mid + 1);PushStack(&s, right);}if (left < mid - 1)//保證區(qū)間的有效性{PushStack(&s, left);PushStack(&s, mid - 1);}}DestoryStack(&s);
}

快速排序的總結(jié)：

1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
2. 時間復(fù)雜度：O(N*logN)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：不穩(wěn)定

2. 歸并排序

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

合并時的動圖：

其實歸并排序很簡單，像分解的過程，不是和快速排序很像嘛，都是傳數(shù)組和區(qū)間。不同的是，因為快速排序是確定基準(zhǔn)值，因為基準(zhǔn)值已經(jīng)到了它排序后的最終位置，后續(xù)傳區(qū)間就是基準(zhǔn)值的左右區(qū)間，但是歸并排序可不是這樣的，歸并排序是直接找數(shù)組的中間下標(biāo)，然后將數(shù)組一分為二，這樣的話也就表示了再這過程中是，中間元素是不會到達(dá)最終位置，所以我們的區(qū)間要包括中間元素。
后序關(guān)于合并的問題就更簡單了，在鏈表期間，我們就應(yīng)該寫過一個合并兩個有序鏈表的問題，這個和那題是沒有本質(zhì)區(qū)別的：邏輯都在兩個區(qū)間中找小，找到后將較小的數(shù)據(jù)取出，然后移動找到小數(shù)據(jù)那邊的指針，最后當(dāng)比較完畢后，大概會有一個區(qū)間沒有走完我們只要再把那個沒有走完數(shù)據(jù)的區(qū)間取出即可。

void _MergeSort(int* a, int* tmp, int begin, int end)
{//確定遞歸出口if (begin >= end)return;int mid = (begin + end) / 2;//劃分?jǐn)?shù)組，將數(shù)組一分為二//以下為分解邏輯_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);//以下為合并邏輯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++];elsetmp[index++] = a[begin2++];}//處理剩余元素while (begin1 <= end1)tmp[index++] = a[begin1++];while (begin2 <= end2)tmp[index++] = a[begin2++];//將臨時數(shù)組存放的數(shù)據(jù)重新復(fù)制到原數(shù)組memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);//臨時數(shù)組，存放合并時的數(shù)據(jù)if (tmp == NULL){perror("malloc");exit(-1);}//歸并排序的核心邏輯，再封裝一個函數(shù)來實現(xiàn)_MergeSort(a, tmp, 0, n - 1);
}

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

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

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