C++ STL中提供了sort()函数,但对于学习理解快速排序的思想,还是得明白快速排序手写模板的具体运用。
时间复杂度:O(n*logn)。
空间复杂度:O(n)。
具体思想是选择一个一个枢纽进行比较,从两端开始寻找。左端点找到一个比枢纽大的值,右端点找到一个比枢纽小的值,进行交换。然后左右递归两端,类似于二叉树的先序遍历。
对于枢纽的选择是具有不确定性的,可以选择任意一个断点值。为了方便计算一般选择左端点、右端点或者中间值。
#include <iostream> #include <bits/stdc++.h> using namespace std; const int N = 1e6+10; int a[N],n; void quick_sort(int *a,int l,int r) { int i = l-1,j = r+1;//预处理 因为循环使用的do while循环 int x = a[(l+r)/2];//定义一个枢纽 if( l >= r)//递归终止条件 return; while(i < j) { do i++;while(a[i] < x); do j--;while(a[j] > x);//找到两个符合的数值进行交换 if(i < j) swap(a[i],a[j]); } quick_sort(a,l,j);//递归遍历 quick_sort(a,j+1,r); } int main() { scanf("%d",&n); for(int i = 0;i < n;i++) scanf("%d",&a[i]); quick_sort(a,0,n-1); for(int i = 0;i < n;i++) printf("%d ",a[i]); return 0; }