title: Notes-QuickSorttags: ACM
abbrlink: 12aa90f7
date: 2020-10-10 12:03:02

思路

快排基本思路应该就是二分+递归，从两侧同时（实则先从右往左）往中间找，同时和参变量对比，发现位置颠倒后交换位置，然后通过二分将其一块一块的分割开，直到分割到一个元素位置，即完成了快排。

代码

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. int a[101],n;
  7. void quicksort(int left,int right)
  8. {
  9.     int i,j,t,temp;//temp存基准数 
  10.     if(left>right)    return;
  12.     temp=a[left];
  13.     i=left;
  14.     j=right;
  15.     while(i!=j)
  16.     {
  17.         while(a[j]>=temp && i<j)    j--;
  18.         while(a[i]<=temp && i<j)    i++;
  20.         if(i<j)
  21.         {
  22.             t=a[i];
  23.             a[i]=a[j];
  24.             a[j]=t;
  25.         }
  26.     }
  28.     a[left]=a[i];
  29.     a[i]=temp;
  31.     quicksort(left, i-1);
  32.     quicksort(i+1,right);
  33.     return;
  34. }
  36. int main(){
  37.     cin>>n;
  38.     for(int i=1;i<=n;i++)
  39.         cin>>a[i];
  40.     quicksort(1,n);
  42.     for(int i=1;i<=n;i++)
  43.     {
  44.         cout<<a[i]<<" ";
  45.     }
  47.     return 0;
  48. }

总结

快排应该是最常用的模板了，时间复杂度也比较理想

PS.致敬一波快排的提出者东尼·霍尔(C. A. R. Hoare)