//13.快速排序-对顺序表L进行快速排序

//③交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置

//此时在它之前(后)的记录均不大(小)于它

int Partition(SqList *L,int low,int high){

    int pivotkey;

    //pivokey 保存子表中第1个记录作为枢轴记录;

    pivotkey = L->r[low];

    //① 从表的两端交替地向中间扫描;

    while (low < high) {





        //② 比较,从高位开始,找到比pivokey更小的值的下标位置;

        while (low < high &&  L->r[high] >= pivotkey)

            high--;

        //③ 将比枢轴值小的记录交换到低端;

        swap(L, low, high);

        //④ 比较,从低位开始,找到比pivokey更大的值的下标位置;

        while (low < high && L->r[low] <= pivotkey)

            low++;

        //⑤ 将比枢轴值大的记录交换到高端;

        swap(L, low, high);





    }





    //返回枢轴pivokey 所在位置;

    return low;

}





//② 对顺序表L的子序列L->r[low,high]做快速排序;

void QSort(SqList *L,int low,int high){

    int pivot;





    if(low < high){

        //将L->r[low,high]一分为二,算出中枢轴值 pivot;

        pivot = Partition(L, low, high);

        printf("pivot = %d L->r[%d] = %d\n",pivot,pivot,L->r[pivot]);

        //对低子表递归排序;

        QSort(L, low, pivot-1);

        //对高子表递归排序

        QSort(L, pivot+1, high);

    }





}





//① 调用快速排序(为了保证一致的调用风格)

void QucikSort(SqList *L){

    QSort(L, 1, L->length);

}





//14 快速排序-优化

int Partition2(SqList *L,int low,int high){





    int pivotkey;





    /**1.优化选择枢轴**/

    //① 计算数组中间的元素的下标值;

    int m = low + (high - low)/2;

    //② 将数组中的L->r[low] 是整个序列中左中右3个关键字的中间值;

    //交换左端与右端的数据,保证左端较小;[9,1,5,8,3,7,4,6,2]

    if(L->r[low]>L->r[high])

        swap(L, low, high);

    //交换中间与右端的数据,保证中间较小; [2,1,5,8,3,7,4,6,9];

    if(L->r[m]>L->r[high])

        swap(L, high, m);

    //交换中间与左端,保证左端较小;[2,1,5,8,3,7,4,6,9]

    if(L->r[m]>L->r[low])

        swap(L, m, low);

    //交换后的序列:3,1,5,8,2,7,4,6,9

    //此时low = 3; 那么此时一定比选择 9,2更合适;









    /**2.优化不必要的交换**/

    //pivokey 保存子表中第1个记录作为枢轴记录;

    pivotkey = L->r[low];

    //将枢轴关键字备份到L->r[0];

    L->r[0] = pivotkey;





    //① 从表的两端交替地向中间扫描;

    while (low < high) {

        //② 比较,从高位开始,找到比pivokey更小的值的下标位置;

        while (low < high &&  L->r[high] >= pivotkey)

            high--;





        //③ 将比枢轴值小的记录交换到低端;

        //swap(L, low, high);

        //③ 采用替换的方式将比枢轴值小的记录替换到低端

        L->r[low] = L->r[high];





        //④ 比较,从低位开始,找到比pivokey更大的值的下标位置;

        while (low < high && L->r[low] <= pivotkey)

            low++;





        //⑤ 将比枢轴值大的记录交换到高端;

        //swap(L, low, high);

        //⑤ 采样替换的方式将比枢轴值大的记录替换到高端

        L->r[high] = L->r[low];

    }

    //将枢轴数值替换会L->r[low]

    L->r[low] = L->r[0];





    //返回枢轴pivokey 所在位置;

    return low;

}





//② 对顺序表L的子序列L->r[low,high]做快速排序;

#define MAX_LENGTH_INSERT_SORT 7 //数组长度的阀值

void QSort2(SqList *L,int low,int high){

    int pivot;

    //if(low < high){

    //当high-low 大于常数阀值是用快速排序;

    if((high-low)>MAX_LENGTH_INSERT_SORT){

        //将L->r[low,high]一分为二,算出中枢轴值 pivot;

        pivot = Partition(L, low, high);

        printf("pivot = %d L->r[%d] = %d\n",pivot,pivot,L->r[pivot]);

        //对低子表递归排序;

        QSort(L, low, pivot-1);

        //对高子表递归排序

        QSort(L, pivot+1, high);

    }else{

        //当high-low小于常数阀值是用直接插入排序

        InsertSort(L);

    }

}





//① 快速排序优化

void QuickSort2(SqList *L)

{

    QSort2(L,1,L->length);

}