quicksort

快速排序

有几个细节比较重要

今天听到一个清华的大佬的话，他曾经是NOI,在大一就得到了我梦寐以求的ACM金奖，他这样说，他们在打NOI的时候，每天要求做10道题，连续做60天就是600每10道题就是一个小小的台阶，只有练好了这种元功力，才能更好的在这条道路上走下去每做10道题就是一个小的提升，我从大一大二这么长时间，才做了300题不到虽然有人说ACM不是唯一的出路，但是编程水平还有算法是一个程序员的必修课，所以不管我能不能得到奖，我都会认真的去学习编程

之前的学习都太过于肤浅，没有深刻理解程序内涵，所以今后写的代码一定要高质量，博客内容也不能太不好，要认真的去对待，全心投入，毕竟有一件可以全身心投入的事情是多么不容易。

快速排序需要记住的几个点

• 取等条件

  在递归的过程中要严格控制取等条件，因为稍不注意就会导致陷入死循环
  • 退出条件 l >= r return;
  • i 从 l 开始
  • main中调用quickSort(0,n-1):n-1是边界
• 细节
  • 先从右侧开始选择，然后在从左侧开始
  • quickSort(l,i-1)(i+1,r)
  • if i < j 才进行交换，否则不交换

很容易看懂的代码（代码原理就不说了）

#include 
    
     #include 
     
      #include 
      
       using namespace std;int n;int arr[10000];void quickSort(int l, int r){  if(l >= r)return ;  int tmp = arr[l];  int i = l;  int j = r;  // cout << i << " " << j << endl;  while(i != j){    while(arr[j] >= tmp && i < j)      j--;    while(arr[i] <= tmp && i < j)      i++;    if(i < j){      int tt = arr[j];      arr[j] = arr[i];      arr[i] = tt;    }  }  arr[l] = arr[j];  arr[j] = tmp;  quickSort(l,j-1);  quickSort(j+1,r);}int main(){  memset(arr,0,sizeof arr);  cin >> n;  for(int i = 0 ; i < n ;i++){    cin >> arr[i];  }  quickSort(0,n-1);  for(int i = 0 ; i < n ;i++){    cout << arr[i] << " ";  }  cout << endl;  return 0;}