排序算法——快速排序

淡淡的烟草味﹌ 2022-06-12 00:20 336阅读 0赞

## 前言 ##

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

快速排序的思想是：假设数据元素存放在数组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>());
    
    }