快速排序(从小到大)

   6 7 3 2 5 8 1 9 4

   t

   i->           <-j

1、找标兵（基准元素），通常找第一个元素，作为基准元素，基准元素的值会对算法速度有一定的影响

2、找哨兵*2，分别记录左右两端

3、先j后i相向而行

   (a)j向左移动，直到与i相遇或当前元素小于标兵，停止：j->4

   (b)i向右移动，直到与j相遇或当前元素大于标兵，停止：i->7

   (c)交换i与j的元素值（643258197），重复3直到i与j相遇

4、交换标兵与哨兵对应的值（143256897）

此时标兵位置正确，且左右两端的数据均小于（大于）标兵

5、将左右两端的数据分别从1开始递归，直到左右两端的数据数量小于等于1，递归结束

{6}[7] 3  2  5  8  1  9 [4]

{6} 4  3  2  5 [8][1] 9  7

{6} 4  3  2  5[[1]]8  9  7

1  4  3  2  5 |6| 8  9  7

{1} 4  3  2  5    {8} 9  7

#include <iostream>

using namespace std;

int a[9]={6,7,3,2,5,8,1,9,4};

void qsort(int left,int right){

   if(right-left<=1) return ;

   int t=a[left];

   int i=left,j=right;

   while(i!=j){

       while(i!=j&&a[j]>=t) j--;

       while(i!=j&&a[i]<=t) i++;

       if(i!=j) swap(a[i],a[j]);

   }

   if(i!=left) swap(a[i],a[left]);

   qsort(left,i-1);

   qsort(i+1,right);

}

int main(){

   qsort(0,8);

   for(int i=0;i<9;i++) cout<<a[i]<<" ";

   return 0;

}