递归分治 — 例题4. 快速排序

---

一.问题描述

给定一个数组,使用快速排序算法进行排序.

二.解题思路

熟悉的快排,曾经写过不知道多少遍.在此还扩展了随机选择支点的算法RandomizedQuickSort.
快排的思想很简单:
对于输入a[p: r]，按以下三个步骤进行排序：

• 分解:取a中的一个元素为支点(pivot) 将a[p: r]划分成3段: a[p: q-1], a[q], a[q+1: r], 使得 a[p:q-1]中任一元素<=a[q], a[q+1: r]中任一元素 >=a[q]; 下标q在划分过程中确定。
• 递归求解:递归调用快速排序法分别对a[p: q-1]和a[q+1: r]排序。
• 合并:合并a[p: q-1], a[q], a[q+1: r]为a[p: r]

例如:
a[1:8] = [13, 24, 7, 9, 2, 7, 15, 35], 选取第一个元素13作为支点

• 分解: a[q] = 13, a[p: q-1] = [7, 9, 2, 7], a[q+1, r] = [24, 15, 35], 则知道q = 5
• 排序: a[p: q-1] = [2, 7, 7, 9] a[q+1: r] = [15, 24, 35] (实际上并不是划分一次就开始排序,而是不断递归划分,不断地把小于当前基准的值挪到前面,大于的值挪到后面,其实就是在排序)
• 合并: 把a[p: q-1]中的元素放在支点元素13之前,a[q+1: r]中的元素放在支点元素之后,
  得到数组为: [2, 7, 7, 9, 13, 15, 24, 35]

为了避免大家还不理解,我再举个例子:
就好比我们要将: 2 1 3 这三个数进行排序,那么我们首先选择基准2,然后把小于2的元素移到前面,大于的移到后面,那么就得到了 1 2 3
这样就排序好了.
而面对一个较大的数组,我们也是一样的操作,递归分治的思想就体现在这里,我们每一次都把问题规模给缩小了,最后缩小到到了只有两个元素,很容易就排好了.
而且在不断递归划分的过程中,所有的数字的顺序都已经逐渐趋于有序.
第一次划分过后,大于基准值的数字不可能再出现在前面一半元素中,同样小于基准值的数字必然在前面一半元素中.
第二次划分后,…

代码如下:

// 快排
// 大三算法课
#include<bits/stdc++.h>
using namespace std;
#define random(a,b) (((double)rand()/RAND_MAX)*(b-a)+a)  //产生(a,b)区间的一个随机数
// random,基准点由a[left],变为了random(a[left], a[right])
template<class T>
int randomizedPartition(vector<T> &a, int p, int r)
{
    srand(int(time(0)));  //每次以当前时间作为随机数生成的种子
    int i = random(p, r);
    swap(a[i], a[p]);
    return Partition(a, p, r);
}
// 基准点为a[p],进行划分
int Partition(vector<int>& a, int low, int high)  //将小于key的元素交换到左边区域,大于key的元素交换到右边区域
{
    int key = a[low];
    while(low<high)
    {
        while(low<high&&a[high]>key) --high;
        a[low] = a[high];
        while(low<high&&a[low]<=key) ++low;
        a[high] = a[low];
    }
    a[low] = key;
    return low;
}
// 随机选择,避免极端情况出现,采用random.实际上差不多,时间复杂度O(n)-O(n^2)
template<class T>
void randomizedQuickSort(vector<T> &a, int left, int right)
{
    if(left<right)
    {
        int loc = randomizedPartition(a, left, right);
        randomizedQuickSort(a, left, loc-1);
        randomizedQuickSort(a, loc+1, right);
    }
}
template<class T>
void QuickSort(vector<T> &a, int left, int right)
{
    if(left<right)
    {
        int loc = Partition(a, left, right);
        QuickSort(a, left, loc-1);
        QuickSort(a, loc+1, right);
    }
}
int  main()
{
    cout<<"快速排序"<<endl;
    int n;
    cout<<"输入数组大小:";
    while(cin>>n && n)
    {
        vector<int> nums(n);
        cout<<"输入数组元素:";
        for(int i=0; i<n; ++i) cin>>nums[i];
        // QuickSort<int>(nums, 0, n-1);
        randomizedQuickSort<int>(nums, 0, n-1);
        for(const int x:nums) cout<<x<<" ";
        cout<<endl;
        cout<<"输入数组大小:";
    }
    system("pause");
    return 0;
}

运行结果:

欢迎大家访问我的个人博客乔治的编程小屋,和我一起体验养成式程序员的打怪升级之旅吧!