相信上过数据结构这门课的同学都接触过排序问题，一开始我们学习的是冒泡排序，虽然时间复杂度很糟糕，但是也是最经典最基础的排序算法。
今天我来介绍两种也很经典的排序算法：快速排序和归并排序。
首先是快速排序：
快速排序用的是分而治之的思想。
① 首先我们来确定一个分界点，理论上是可以随机确定分界点的，但是我偏向于选择q[ ( l + r ) / 2 ] 这个分界点
② 调整排序区间，那么具体如何调整呢？如下图所示：
③递归处理左右两端
快速排序的时间复杂度平均来说是 O ( n logn) 同时快速排序也不是稳定排序。
话不多说 上代码~
# include <iostream> # include <algorithm> using namespace std; const int N =1e6+10; int n; int q[N]; void quick_sort(int q[],int l,int r) { if(l>=r) return; //递归出口 int x = q[( l + r ) / 2],i = l-1,j=r+1; //确保排序不漏掉第一个和最后一个 while(i<j) { do i++; while(q[i]<x); //当i指向的数小于x，i后移 do j--; while(q[j]>x); //当j指向的数小于x，j前移 if(i<j) swap(q[i] , q[j]); //当i j停止 调换位置 } quick_sort(q,l,j); quick_sort(q,j+1,r); //递归 } int main() { cin.tie(0); cin>>n; for(int i = 0;i < n ; i ++) { cin>>q[i]; } quick_sort(q,0,n-1); for(int i = 0;i < n ; i ++) cout<<q[i]<<" "; return 0; }
下面再介绍另一种排序算法：归并排序
归并排序用的也是分治的思想。
① 首先找分界点mid = (l + r ) / 2
② 这里就与快速排序不同啦，我们这里先递归
③再归并 合二为一
我画一张图来帮助理解一下：
上代码~
# include <iostream> # include <algorithm> using namespace std; const int N = 1e6+10; int n; int q[N],temp[N]; void merge_sort(int l,int r) { if(l>=r) return; //递归出口 int mid = (l+r) / 2; merge_sort(l,mid); merge_sort(mid+1,r); int i =l,j=mid+1,k=0; //k是temp数组的指针 while(i <= mid && j <= r) { if(q[i] <= q[j]) temp[k++] = q[i++]; else temp[k++] = q[j++]; } //存在一端已经存入temp中但是另一端还没存完的情况 while(i<=mid) temp[k++] = q[i++]; while(j<=r) temp[k++] = q[j++]; for(i = l,j = 0;i<=r;i++,j++) q[i] = temp[j]; //双指针用temp更新q }
int main()
{
cin.tie(0);
cin>>n;
for(int i = 0;i < n ; i ++)
{
cin>>q[i];
}
merge_sort(0,n-1);
for(int i = 0;i < n ; i ++)
cout<<q[i]<<" ";
return 0;
}
归并排序的时间复杂度是稳定的O(nlogn) 同时归并也是稳定的排序算法~
虽然我们平时在做题的时候想排序直接用algorithm库中的sort函数，但是这种分治的思想也很重要。
话说sort函数好像也不是用的快速排序，分情况用堆排序还是快速排序。