c++：快速排序（二）

快速排序：二分 ---尾优化

#include <iostream>

#include <QList>

#include <QDebug>

using namespace std;

void qucikSort(QList<int> &list, int start, int end);

int pascOrder(QList<int> &list,int start,int end);

int main()

{

    QList<int> numList;

    numList.push_back(3);

    numList.push_back(5);

    numList.push_back(1);

    numList.push_back(2);

    numList.push_back(10);

    numList.push_back(8);

    numList.push_back(6);

    numList.push_back(7);

    numList.push_back(0);

    numList.push_back(14);

    numList.push_back(9);

    numList.push_back(11);

    numList.push_back(12);

    qucikSort(numList,0,numList.count()-1);

    qDebug()<<numList;

}

void qucikSort(QList<int> &list,int start,int end)

{

    int index;

    while(start < end)

    {

       index = pascOrder(list, start, end);

       qucikSort(list, start, index - 1);

       start=index+1;     //<尾优化

    }

}

int pascOrder(QList<int> &list, int start, int end)

{

    int info = list[start];

    int left = start;

    int right = end;

    while(left < right)

    {

        while(left < right && list[right]>info)

        {

            --right;

        }

        list[left] = list[right];

        while(left<right  && list[left]<info)

        {

            ++left;

        }

        list[right] = list[left];

    }

    list[left] = info;

    return left;

}