快速排序和歸併排序的比較： stable_sort

快速排序和歸併排序是兩種基本的排序算法，它們在實際應用中得到了廣泛的運用。本文將分析這兩種算法的優劣，並比較它們的特點和應用場景，最後介紹C++中的stable_sort算法。

一、快速排序

快速排序的核心是分治法，將原問題劃分為若干個子問題，再將子問題劃分為更小的子問題，直到問題的規模被縮小到可以直接求解的程度。具體的快排實現過程可以分為以下三個步驟：

1、選擇一個基準元素，通常選擇第一個元素或者最後一個元素；

2、將數組中小於基準元素的數放到它左邊，大於基準元素的數放到它右邊；

3、對基準元素左右兩邊的子數組重複步驟1和步驟2，直到子數組中只有一個元素或者沒有元素。

快速排序的主要優點在於其平均時間複雜度為O(nlogn)，且原地排序，即空間複雜度為O(1)。但其劣勢也相對明顯，容易受到輸入數據的影響，可能會退化為O(n^2)的時間複雜度。

“`cpp
void quick_sort(int arr[], int left, int right) {
if(left >= right) return;
int i = left, j = right, base = arr[left];
while(i < j) {
while(i = base) j–;
if(i < j) arr[i++] = arr[j];
while(i < j && arr[i] <= base) i++;
if(i < j) arr[j–] = arr[i];
}
arr[i] = base;
quick_sort(arr, left, i – 1);
quick_sort(arr, i + 1, right);
}
“`

二、歸併排序

歸併排序採用的是分治法的思想，其主要思路就是將原序列分成若干個子序列，每個子序列長度為1，然後將相鄰的子序列進行合併得到一個新的有序序列，重複這個過程直到整個序列有序為止。具體實現過程如下：

1、將數組劃分為左右兩個子數組；

2、遞歸地將左右兩個子數組進行排序；

3、將排序後的左右兩個子數組進行合併。

相比於快排，歸併排序的時間複雜度始終為O(nlogn)，且穩定，不受輸入數據影響。但其缺點也很明顯，需要額外的空間存放排好序的序列。

“`cpp
void merge(int arr[], int l, int m, int r) {
int n1 = m – l + 1, n2 = r – m;
int L[n1], R[n2];
for(int i = 0; i < n1; i++) L[i] = arr[l + i];
for(int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while(i < n1 && j < n2) {
if(L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while(i < n1) arr[k++] = L[i++];
while(j = r) return;
int m = l + (r – l) / 2;
merge_sort(arr, l, m);
merge_sort(arr, m + 1, r);
merge(arr, l, m, r);
}
“`

三、快速排序和歸併排序的比較

雖然兩種排序算法都可以實現O(nlogn)的時間複雜度，但是快排和歸併排序卻有很大的區別。

首先，歸併排序是穩定排序，即對於相等元素排序後的順序不會改變，而快排是不穩定的，相等元素的順序可能被改變。

其次，快排的空間複雜度為O(1)，不需要額外的存儲空間，而歸併排序需要額外的空間存放排好序的序列。

最後，快排在大部分情況下的排序性能相對較好，但是在處理大規模、非隨機數據時，可能會退化為O(n^2)，而歸併排序的時間複雜度始終穩定在O(nlogn)。

四、stable_sort函數

在實際的開發中，我們通常希望對序列進行穩定排序，以確保排序結果滿足我們的要求。這時，就可以考慮使用C++ STL中的stable_sort函數，其採用的是歸併排序的思想，能夠保證排序的穩定性。

“`cpp
#include
#include
using namespace std;
bool cmp(const pair& x, const pair& y) {
return x.first < y.first;
}
int main() {
vector<pair> v = {{2, 3}, {1, 2}, {3, 4}};
stable_sort(v.begin(), v.end(), cmp);
return 0;
}
“`

總結

本文分析了快速排序和歸併排序的特點及優劣，並通過比較解釋它們的應用場景。最後，介紹了C++ STL中的stable_sort函數，方便大家進行穩定排序。