快速排序算法

快速排序算法

原理：从待排序集合中选取一个元素为基准，然后对待排序元素进行一趟排序，排序结果保证基准元素在正确的位置上，其前面的元素都小于基准，后面的元素都大于基准。这样将集合划分为两个子集，然后对子集进行递归排序。

通常快速排序算法采用递归方式实现， 非递归实现需要模拟栈的行为，将每次划分的起止坐标入栈，然后取栈元素进行排序。

inline int partition(int a[], int i, int j)
{
    int pivot = a[i];
    while (i < j){
        while (i<j && a[j]>pivot) --j;
        if (i < j){
            a[i++] = a[j];
        }
        while (i<j && a[i]<pivot) ++i;
        if (i < j){
            a[j--] = a[i];
        }
    }
    a[i] = pivot;
    return i;
}

void quicksort(int a[], int low, int high)
{
    int pivotpos;

    if (low < high){
        pivotpos = partition(a, low, high);
        quicksort(a, low, pivotpos-1);
        quicksort(a, pivotpos+1, high);
    }
}