《算法之美》---快速排序(随机快速排序)

快速排序是对冒泡排序的一种改进，它使用分治的思想，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录循环进行排序，以达到整个序列有序的状态。
 
快速排序是C.A.R Hoare在1962年提出的，显然，它是一种分治算法，并且是原地排序算法。快速排序可分为四个步骤：
1）选择杠杆点：在待排序的序列中按照某种方式选取一个元素作为划分的杠杆点。
2）分解：以杠杆点为界，将序列分为两个子序列，其中一个子序列里的所有元素小于等于杠杆点，另一个子序列里的所有元素大于杠杆点。
3）治之：递归对两个子序列进行快速排序。
4）合并：将排好序的两个子序列合并成大序列。
 
快速排序的时间成本取决于分解这一步，分解的好坏将对整个算法的效率产生决定性影响。但分解的好坏取决于杠杆点的选择。下面是标准的序列分解算法：
PARTITION(A, m, n)             //A[m...n]为一个序列
        x<--A[m]                  //A[m]为我们选择的杠杆点
        i<--m
        for   to  n  do
                  if A[j]<=x then
                           i<--i+1
                           Exchange A[i] <--> A[j]
        Exchange A[m] <--> A[i]
        return i;
 
上述算法将子序列A[m…n]以A[m]为界分解为两个子序列：A[m…i-1]和A[i+1…n]。在每一次for循环中，A[m…i]里面的元素都小于等于杠杆点x，A[i+1…j]里面的元素都大于杠杆点x，而A[j+1…n]里面的元素是尚未分解的子序列里的元素。
有了分解算法之后，整个快速排序算法如下：
QUICKSORT(A, p, r)
        if p<r then
                  q <-- PARTITION(A, p, r)
                  QUICKSORT(A, p, q-1);
                  QUICKSORT(A, q+1, r);
 
程序的初始调用为QUICKSORT(A, 1, n)。
 
快速排序最坏情况下时间复杂度是Θ(n2)，最好情况下和平均情况下都是Θ(nlogn)。
 
快速排序分解出的子序列是否为空取决于杠杆点与其他元素的相对关系，因此，在使用快速排序的时候，要想保证算法的时间复杂度不被输入序列有意地操控，我们在选择杠杆点的时候就不能是确定性的。如果每次都是随机选择一个元素作为杠杆点，则无论对手进行多少次实验也不能得出任何肯定的结论，自然也就不能有针对性的进行输入数据次序的安排来使我们快排算法总是处于最坏时间复杂度下。
随机化快速排序算法模板如下：
/*
函数名：     quick_sort
功能：       快速排序辅助过程
*/
template <typename T>
void quick_sort (T data[],int frist,int last)
{
        int lower=frist+1;
        int upper=last;
        int t=rand()%(last-frist)+frist;
        std::swap(data[frist], data[t]);
        T& bound=data[frist];
        while (lower<=upper)
        {
                  while (data[lower]<bound)
                  {
                           ++lower;
                  }
                  while (bound<data[upper])
                  {
                           --upper;
                  }
                  if (lower<upper)
                  {
                           std::swap(data[lower], data[upper]);
                           ++lower;
                           --upper;
                  }
                  else
                           ++lower;
        }
        std::swap(data[upper], data[frist]);
        if (frist<upper-1)
                  quick_sort(data, frist, upper-1);
        if (upper+1<last)
                  quick_sort(data, upper+1, last);
}
 
/*
函数名：     QuickSort
功能：       快速排序
模板参数说明：T必须支持小于操作
参数说明：   data待排序数组, size待排序数组大小
前置条件：   data!=NULL, size>0
后置条件：   data按排列
用法：
#include <algorithm>
#include <stdlib.h>
#include <time.h>
int arr[]={10,9,8,4,5,7,6,3,1,4};
QuickSort(arr, 10);
*/
template <typename T>
void QuickSort (T data[],int size)
{
        int i, max;
        if (size<2)
                  return;
        for (i=1, max=0; i<size; ++i)
        {
                  if (data[max]<data[i])
                           max=i;
        }
        std::swap(data[size-1], data[max]);
        srand(time(0));
        quick_sort(data, 0, size-2);
}
 
 
 
/*
函数名：     quick_sort
功能：       快速排序辅助过程
*/
template <typename T, typename Func>
void quick_sort (T data[],int frist,int last, Func& f)
{
        int lower=frist+1;
        int upper=last;
        int t=rand()%(last-frist)+frist;
        std::swap(data[frist], data[t]);
        T& bound=data[frist];
        while (lower<=upper)
        {
                  while (f(data[lower],bound))
                           ++lower;
                  while (f(bound,data[upper]))
                           --upper;
                  if (lower<upper)
                  {
                           std::swap(data[lower], data[upper]);
                           ++lower;
                           --upper;
                  }
                  else
                           ++lower;
        }
        std::swap(data[upper], data[frist]);
        if (frist<upper-1)
                  quick_sort(data, frist, upper-1, f);
        if (upper+1<last)
                  quick_sort(data, upper+1, last, f);
}
 
/*
函数名：     QuickSort
功能：       快速排序
模板参数说明：T元素类型，Func函数对象或指针
参数说明：   data待排序数组, size待排序数组大小,函数对象或指针
前置条件：   data!=NULL, size>0
后置条件：   data按排列
用法：
#include <algorithm>
#include <stdlib.h>
#include <time.h>
bool cmp(int a, int b)
{ return a<b; }
int arr[]={10,9,8,4,5,7,6,3,1,4};
QuickSort(arr, 10, cmp);
*/
template <typename T, typename Func>
void QuickSort (T data[],int size, Func f)
{
        int i, max;
        if (size<2)
                  return;
        for (i=1, max=0; i<size; ++i)
        {
                  if (f(data[max],data[i]))
                           max=i;
        }
        std::swap(data[size-1], data[max]);
        srand(time(0));
        quick_sort(data, 0, size-2, f);
}