排序算法复习（6）——QuickSort排序
1.基本原理：
（1）使用分而治之法，将数组一分为二（至于怎么分？这就是快速排序的精粹所在、理解的难点所在），然后递归排序子数组。
（2）递归结束的条件是子数组为空或者仅仅含有1个元素！！
关键是找出P的位置，根据该下标把数组A[L,H]分成两半，A[L,P-1]和A[P+1,H]；其中A[L,P-1]中的所有元素小于A[P]，A[P+1,H]中所有元素大于A[P]，但是A[L,P-1]和A[P+1,H]未必就是有序的！然后递归调用即可。
递归结束的条件是子数组为空或者仅仅含有1个元素！！
2、数组如何划分
2.1这里使用的是《编程珠玑》第11章介绍的方法。
2.1.1选取第一个元素为主轴元素
//a[low],a[low+1],...,a[high]//static int partition(int* a,int low,int high){ int m = low;
//use the first element in each array int pivot = a[low]; int pivot_index = low;
for( int j = low + 1; j <= high ; ++j) { if ( a[j] < pivot ) { ++m; swap(a[m],a[j]); } } swap(a[pivot_index],a[m]);
return m;}
/*if we have an array:\ int a[100];\ USE quick_sort(a,0,99),NOT quick_sort(a,0,100)*/static void quick_sort(int* a,int low,int high){ //assert( a != NULL && n > 0); if( low >= high ) return; int q = partition(a,low,high); quick_sort(a,low,q - 1); quick_sort(a,q + 1,high);}2.1.2
2.1.3双向划分
2.1.4小数组上使用insertion sort
2.2这里使用的是《算法导论》第7章介绍的方法。
2.2.1选取A[p..r]中的A[r]为主轴元素
static int partition(int* a,int low,int high){ int x = a[high]; int i = low - 1; for( int j = low; j <= high - 1; ++j) { if ( a[j] <= x ) { ++i; swap(a[i],a[j]); } } swap(a[(i+1)],a[high]); return (i+1);}2.2.2随机化版本
不是始终采用A[r]为主元，而是从子数组A[p..r]中随机选择一个元素，即将A[r]于从A[p..r]中随机选出的一个元素交换。
static int partition(int* a,int low,int high){ int x = a[high]; int i = low - 1; for( int j = low; j <= high - 1; ++j) { if ( a[j] <= x ) { ++i; swap(a[i],a[j]); } } swap(a[(i+1)],a[high]); return (i+1);}int random_partition(int* a,int low,int high){ int i = low + ( rand() % (high - low) + 1); swap(a[i],a[high]); return partition(a,low,high);}/*if we have an array:\ int a[100];\ USE quick_sort(a,0,99),NOT quick_sort(a,0,100)*/static void quick_sort(int* a,int low,int high){ //assert( a != NULL && n > 0); if( low >= high ) return; int q = random_partition(a,low,high); quick_sort(a,low,q - 1); quick_sort(a,q + 1,high);}2.2.3Hoare划分法（思考题7-1）
。。。待续
2.2.4三数取中（思考题7-5）
。。。待续
参考：
算法导论
编程珠玑