一、.算法分析
快速排序使用分治（Divide and conquer）策略，从序列中选取pivot ，把这个序列（list）通过这个pivot分为两个子序列（sub-lists），一个子序列中所有的元素都不大于pivot，另一个子序列中的所有元素都不小于pivot，从而确定了pivot在整个序列的位置，对每个子序列执行同样的操作，直至序列中的每个元素的最终位置都确定。
步骤为：
从数列中挑出一个元素，称为 "基准"（pivot）
- 重新排序数列，所有元素中比基准值小的摆放在基准前面，所有元素中比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
- 递归地（recursive）对小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最终的位置上。
二、快速排序算法性能分析。
快速排序的平均时间复杂度为o(nlgn).空间复杂度o(1), 就地（in place）排序，不稳定的排序。
三、算法的实现。（参见《算法导论》的第7章）
本文实现4种quickSort的实现：它们的实现核心是对划分的的设计。
1.第一种：qickSort使用增量求解的方式进行划分，
在数组a[p..r] 中构建选取a[r]为pivot基准元，在子数组a[p...i...j]中，具有这样的性质：
1)、对于 p<=k <=i, 总有a[k] <=pivot;
2)、对于 i< k <=j 总有a[k]> pivot;
是一个循环不变式。证明不再给出。
2.第二种：randomizedQuickSort随机算法。
公认随机算法能够改善quickSort的平均性能。所谓，随机算法，在算法中引入随机数，使算法对象的处理具有概率上的公平性。
quickSort算法的运行好坏取决于划分的优劣，划分的形成取决于pivot基准的选择，为了使基准的选择性更具有一般性，通过一个随机数生成器来辅助pivot基准的选取。
划分方法同第一种。
3.第三种： Hoare-quickSort 算法，最初的版本的quicksort。发现其实现有一定的技巧，而且很容易出错。原算法中有一些不必要的重复交换，本实现做了一定修改。
4. 第四种： 是对Hoare-quickSort算法的一种改进版，用赋值代替交换，从而避免了不必要的交换。
下面给出quickSort算法的4中实现：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void printArray(int* a, int len);
void exchange(int* a, int* b);
int getRandomNum(int a, int b);
int partition(int* a, int p, int r);
void quickSort(int* a, int p, int r);
int randomizedPartition(int* a, int p, int r);
void randomizedQuickSort(int* a, int p, int r);
int hoarePartition(int* a, int p, int r);
void hoareQuickSort(int* a, int p, int r);
int modifiedHoarePartition(int* a, int p, int r);
void modifiedHoareQuickSort(int* a, int p, int r);
int main(int argc, char* argv[])
{
int a[] ={5, 4, 3, 2, 1, 3, 3, 3, 3, 3, 5, 6, 1};
int len = sizeof(a)/sizeof(a[0]);
// quickSort(a, 0, len-1);
// randomizedQuickSort(a, 0, len-1);
// hoareQuickSort(a, 0, len-1);
modifiedHoareQuickSort(a, 0, len-1);
printArray(a, len);
return 0;
}
void printArray(int* a, int len) {
int i;
for(i=0; i<len; i++) {
printf("%d\t", a[i]);
}
printf("\n");
}
void exchange(int* a, int* b) {
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int* a, int p, int r) {
int i;
int j;
int pivot;
pivot = a[r];
i = p-1;
for(j=p; j<r; j++) {
if(a[j]<= pivot) {
i++;
exchange(a+i, a+j);
}
}
exchange(a+i+1, a+r);
return i+1;
}
//加入随机算法的partition算法
int randomizedPartition(int* a, int p, int r) {
int i;
/*
srand((unsigned)time(NULL)); // init the seed of rand()
i = rand()%(r-p) + p;
*/
i = getRandomNum(p, r);
exchange(&a[i], &a[r]);
return partition(a, p, r);
}
int hoarePartition(int* a, int p, int r) {
int i;
int j;
int pivot;
pivot = a[p];
i = p;
j = r+1;
while(i<j) {
while(i<j && a[--j]>pivot);
while(i<j && a[++i]<=pivot);
if(i<j) {
exchange(&a[i], &a[j]);
}
}
if(i!=p) exchange(&a[i], &a[p]);
return i;
}
int modifiedHoarePartition(int* a, int p, int r) {
int i;
int j;
int pivot;
pivot = a[p];
i = p;
j = r;
while(i<j) {
while(i<j && a[j]>pivot) j--;
if(i<j) a[i++] = a[j];
while(i<j && a[i]<=pivot) i++;
if(i<j) a[j--] = a[i];
}
if(i!= p) a[i] = pivot;
return i;
}
void quickSort(int* a, int p, int r) {
int q;
if(p<r) {
q = partition(a, p, r);
quickSort(a, p, q-1);
quickSort(a, q+1, r);
}
}
void randomizedQuickSort(int* a, int p, int r) {
int q;
if(p<r) {
q = randomizedPartition(a, p, r);
randomizedQuickSort(a, p, q-1);
randomizedQuickSort(a, q+1, r);
}
}
void hoareQuickSort(int* a, int p, int r) {
int q;
if(p<r) {
q = hoarePartition(a, p, r);
hoareQuickSort(a, p, q-1);
hoareQuickSort(a, q+1, r);
}
}
void modifiedHoareQuickSort(int* a, int p, int r) {
int q;
if(p<r) {
q = modifiedHoarePartition(a, p, r);
modifiedHoareQuickSort(a, p, q-1);
modifiedHoareQuickSort(a, q+1, r);
}
}
int getRandomNum(int a, int b) {
srand((unsigned)time(NULL)); // init the seed of rand()
return rand()%(b-a) + a;
}
以上参考《算法导论》第7章。