排序算法——快速排序

前言

快速排序采用了分治法，即将原问题划分成为若干个规模更小且与原问题相似的子问题，然后递归地解决这些子问题，最后将他们组合起来。

快速排序的思想是：假设数据元素存放在数组L中，当前序列为L[left]~L[right]，left和right是当前序列的上下界；在序列中，任选一个数据元素L[pos]（一般选择L[left]，并成为枢轴）作为基准元素；然后，依次从序列的两端交替向序列中间扫描，将序列中关键字小于L[pos]的元素移动到pos的左边，大于L[pos]的元素移动到pos的右边，这样经过一趟快速排序之后，序列就被基准元素划分为了左右两个子序列L[left]~L[pos-1]和L[pos+1]~L[right]，并且左端序列中所有数据元素均小于基准元素，右边的所有元素都大于基准元素，这样基准元素的位置就确定好了。之后将切分开来的子序列重复上面的过程，直到left<right条件不满足，算法结束。

1. 编码

template<typename T> struct Disp
{
    void operator()(T value)
    {
        cout << value << "\t";
    }
};

int Partition(std::vector<int>& vec, int left, int right)
{
    int base_pos = left;    //选择left的坐标为基准元素
    int temp(vec[left]);

    while(left != right) //从数组的两边向中间扫描
    {
        //从右边开始寻找，直到找到第一个小于基准元素的坐标
        while(left<right && temp<=vec[right]) --right;
        if(left < right)
        {
            vec[left] = vec[right];
        }

        //从左边开始寻找，直到找到第一个大于基准元素的坐标
        while(left<right && temp>=vec[left]) ++left;

        if(left < right)
        {
            vec[right] = vec[left];
        }
    }

    //最终将基准数归位
    //vec[base_pos] = vec[left];
    vec[left] = temp;

    return left;
}

void my_QuikSort(std::vector<int>& vec, int left, int right)
{
    if(left <= right)   //待排序的元素至少有两个的情况
    {
        int break_pos = Partition(vec, left, right);
        my_QuikSort(vec, left, break_pos-1);  //对基准元素左边的元素进行递归排序
        my_QuikSort(vec, break_pos+1, right);  //对基准元素右边的进行递归排序
    }
}

void QuikSort(std::vector<int> vec)
{
    int len(vec.size());
    if(len == 0) return;
    cout << "display origin array:" << endl;
    for_each(vec.begin(), vec.end(), Disp<int>());  //打印原始的数据

    //快速排序
    my_QuikSort(vec, 0, len-1);

    cout << "\narray sorted:" << endl;
    for_each(vec.begin(), vec.end(), Disp<int>());

}