#include<iostream>

using namespace std;

int partion(int num[],int left,int right)
{
    int i,j,index,exchage;
    index = num[left];
    i = left; //由于while (i < j)已经决定了，如果 i = left + 1;而数组只有两个元素且j 指向的元素比较大，如 3 8 那么循环不会执行，最后还把8 和3交换了
    j = right;
    while (i<j) // 3 7 2 4 下面的sawp 执行后 变成 3 2 7 4 这时候 i 指向7 j指向2, 就不需要再循环了j就是最终位置  
    {
        while(num[i] <= index && i < right) // i < right 是为了处理 100 2 3 4 这样的情况，i 会一直扫描越界，为什么不是 i<= right，因为已经j 在right了，一定会处理那个元素
          i++;
    
        while(num[j] >= index && j > left) //j > left 是为了处理 -13 2 1 4 这样的情况，j 会一直扫描到-13的左边越界， 注意 j 是 > left， 不是>i 否则 3 8 这种情况就错了
            j--;
        
        if(i < j)
            swap(num[i++],num[j--]);//循环结束三种情况，第一种是 3 7 2 4 第二种是 3 3 1，i == right == j结束了，这时候 i j 肯定在一起，就没有必要交换了
//第三种是 3 7 9 这时候j 因为越界判断失败而退出循环，为什么越界，因为它碰到了第一个元素，这时候不能交换3 和 7 ，因为i 停在了比第一个元素大的地方
    }

     swap(num[left],num[j]);// 从小到大排序注意是 交换 j 和 index 位置！

    return j;
}
void quick_sort(int num[],int lo,int hi)
{
    if (lo<hi)
    {
        int x = partion(num,lo,hi); //对于 3 8 ，x = 0
        quick_sort(num,lo,x-1); //0 到 -1 所以要判断lo <= hi 如果是等于
        quick_sort(num,x+1,hi);//1 到 1，由于只有一个元素8，也没有必要排序了所以上面注释的lo <= hi改成 lo < hi

    }
}
int main()
{
    int a[5] = {3, 4, 2, 1, 0 };
    quick_sort(a,0,4);
     for(i=0;i<5;i++)
         cout << a[i] << endl;
    return 0;
}