快速排序和归并排序是两种基本的排序算法，它们在实际应用中得到了广泛的运用。本文将分析这两种算法的优劣，并比较它们的特点和应用场景，最后介绍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 < j && arr[j] >= 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 < n2) arr[k++] = R[j++]; } void merge_sort(int arr[], int l, int r) { if(l >= 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
> v = {{2, 3}, {1, 2}, {3, 4}}; stable_sort(v.begin(), v.end(), cmp); return 0; } ```
总结
本文分析了快速排序和归并排序的特点及优劣，并通过比较解释它们的应用场景。最后，介绍了C++ STL中的stable_sort函数，方便大家进行稳定排序。
