//快速排序
#include <stdio.h>
#include <iostream>

void quick_sort(int*, int, int);
int partition(int*, int, int);

int main()
{
    int i, j;
    int sort[11] = {0, 6, 5, 4, 9, 3, 0, 8, 2, 1, 7};    //数组0下标丢弃不用
    int first = 1;
    int end = sizeof(sort) / sizeof(int) - 1;
    quick_sort(sort, first, end);
    for(i = first; i<= end; i++){
        printf("%d\n",sort[i]);
    }
    system("pause");
    return 0;
}

void quick_sort(int* ptr, int first, int end)
{
    if(first < end){
        int mid = partition(ptr, first, end);
        quick_sort(ptr, first, mid - 1);
        quick_sort(ptr, mid + 1, end);
    }
}

int partition(int* ptr, int first, int end)
{
    int value = ptr[end];    //将最后一个元素做为主元
    int i = first - 1;    //将i下标减1
    int j, temp;
    for(j = first; j <= end - 1; j++){    //遍历整个分区数组
        if(ptr[j] <= value){    //如果当前值小于或等于主元
            i++;    //则i下标加1,使i下标指向大于主元的元素
            temp = ptr[i];    //交换元素,将大于主元的元素向后移动
            ptr[i] = ptr[j];
            ptr[j] = temp;
        }
    }
    temp = ptr[i + 1];    //将最大的元素与主元交换,完成排序
    ptr[i + 1] = ptr[end];
    ptr[end] = temp;
    return i + 1;    //返回中位下标,右边元素大于等于左边元素
}