4. 快速排序

      虽然堆排序算法是一个很漂亮的算法，但在实际中，快速排序的一个好的实现往往由于堆排序，又由于其平均性能相当好，故快速排序通常是用于排序的最佳的使用选择。

      与合并算法类似，快速排序也是基于分治模式的。下面以典型子数组A[p…r]为例，其分治过程的三个步骤分别为：

      分解：将原数组划分为两个（可能为空）子数组A[p…q-1]，A[q+1…r]，使得A[p…q-1]中的每一个元素都小于等于A(q)，并且，小于等于A[q+1…r]中的元素。

      解决：通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]排序。

      合并：因为两个子数组是就地排序的， 将它们合并不需要操作。故此时数组A[p, r]已完成排序。

4.1 数组划分

      快速排序算法的关键是对该数组进行初始划分并选取合适的q值。

      数组划分的过程需要选取一个主元（一般选取A[r]），并围绕它来划分子数组A[p…r]，将其划分为两个数组，一个数组的值均小于主元，另一个数组的值均大于主元。以数组{2,8,7,1,3,5,6,4}为例进行说明，数组划分过程如图4-1所示。

      过程详解：

      A）：选取A[r]（即数组中最后一位）作为主元。

      B）：将数组第一位与主元比较，由于数组第一位的值（2）小于主元（4），故将其放入小于主元的子数组；

      C）：将数组第二位与主元比较，由于数组第二位的值（8）大于主元（4），故将其放入大于主元的子数组；

      D）：将数组第三位与主元比较，由于数组第三位的值（7）大于主元（4），故将其放入大于主元的子数组；

      E）：将数组第四位与主元比较，由于数组第四位的值（1）小于主元（4），故将其放入小于主元的子数组。但与上面不同的是，该数字与目标子数组（即小于主元的数组）之间被大于主元的数组隔开，故将该数字与大于主元的数组的第一位交换，从而将该数字放入小于主元的数组，即将数组第四位的值（1）与数组第三位的值交换（7）。

      F）：将数组第五位与主元比较，由于数组第五位的值（3）小于主元（4），故将其放入小于主元的子数组。与E）中情况相同，该数字与目标子数组（即小于主元的数组）之间被大于主元的数组隔开，故将该数字与大于主元的数组的第一位交换，从而将该数字放入小于主元的数组，即将数组第五位的值（3）与数组第四位的值交换（8）。

      G）：将数组第六位与主元比较，由于数组第六位的值（5）大于主元（4），故将其放入大于主元的子数组；

      H）：将数组第七位与主元比较，由于数组第三位的值（6）大于主元（4），故将其放入大于主元的子数组；

      I）：此步骤的操作与上述过程均不相同，将主元与大于主元的子数组的第一位交换，从而将原数组按大小（不同子数组之间存在大小关系，相同子数组之间并未按大小排序）划分为小于主元的子数组、主元、大于主元的子数组三部分。

4.2 完成快速排序

      进行完数组划分之后，需要递归地将划分出来的两子数组分别进行快速排序。以上述过程为例，说明之后的快速排序步骤，完成整个快速排序过程。如图4-2a）、b）所示。

      其中4-2a）为小于4的子数组的快速排序后半段，4-2b）为大于4的子数组的快速排序后半段。

C代码实现为：

#include <stdio.h>
//交换两数
void exchange(int &a, int &b) {
	int temp = a; 
	a = b;
	b = temp;
}
//数组划分
int partition(int a[], const int &start, const int &end){
	int x = a[end];
	int i = start-1;
	for(int j=start; j<end; j++) {
		if(a[j]<=x){
			i = i+1;
			exchange(a[i], a[j]);
		}
	}
	exchange(a[i+1], a[end]);
	return i+1;
}
//快速排序算法
void quicksort(int a[], const int &start, const int &end){
	if(start<end){
		int mid = partition(a, start, end);
		quicksort(a, start, mid-1);
		quicksort(a, mid+1, end);
	}
}

int main(int argv,char** arc) {
	int a[] = {2,8,7,1,3,5,6,4};
	int length = sizeof(a)/sizeof(a[0]);
	//显示原数列
	for(int i=0; i<length; i++){
		printf("%d ", a[i]);
	}
	printf("\n");
	//进行快速排序
	quicksort(a, 0, length-1);
	//显示排序后数列
	for(int i=0; i<length; i++){
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;	
}

#include <iostream>
#include <vector>
using namespace std;

//交换两数
void exchange(int &a, int &b){
	if(a==b){
		return;
	}else {
		int temp = a;
		a = b;
		b = temp;
	}
}
//数组划分
int partition(vector<int> &a, const vector<int>::iterator &itStart, const vector<int>::iterator &itEnd) {
	int x = *(itEnd);
	vector<int>::iterator i = itStart;
	for(vector<int>::iterator j=itStart; j<itEnd; j++) {
		//若存在某数小于等于主元，则将该数换至小于主元的子数组
		if( *(j) < x ){
			exchange(*(i), *(j));
			i = i+1;
		}
	}
	exchange(*(i), *(itEnd));
	return (i-itStart);
}
//快速排序
void quicksort(vector<int> &a, const vector<int>::iterator &itStart, const vector<int>::iterator &itEnd) {
	if( itStart<itEnd ) {
		int mid = partition(a, itStart, itEnd);
		if( mid!=0 ){	//当mid=0,itSart+mid-1会报错
			quicksort(a, itStart, itStart+mid-1);
		}
		quicksort(a, itStart+mid+1, itEnd);
	}
}


int main(int argv, char** argc){
	int a[] = {2,8,7,1,3,5,6,4};
	int length = sizeof(a)/sizeof(a[0]);
	vector<int> aVec(a, a+length);
	//显示原排序	
	for(vector<int>::iterator i=aVec.begin(); i<aVec.end(); i++ ){
		cout<<*(i)<<" ";
	}
	cout<<endl;
	const vector<int>::iterator itStart = aVec.begin();
	//itEnd是指该数组的最后一位对应的地址，而.end()得到的是最后一位对应的地址+1
	const vector<int>::iterator itEnd = aVec.end()-1;
	quicksort(aVec, itStart, itEnd);
	//显示排序完成情况
	for(vector<int>::iterator i=aVec.begin(); i<aVec.end(); i++ ){
		cout<<*(i)<<" ";
	}
	cout<<endl;
	return 0;	
}