quickSort - 编程细节

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 <iostream>

#include <cstdio>

#include <cstring>

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;

}