学步园

/*
 * quickSort.cpp(快速排序)
 *
 *  Created on: 2012-4-21
 *      Author: jiyiqin
 *
 *  快速排序：
 *
 *	分治法：
 *		和归并排序一样，快速排序也是基于分治思想的。
 *	代价：
 *		时间复杂度,期望为o(n log n), 但是最坏可能达到o(n^2)
 *		空间复杂度,o(1)，因为是基于交换元素的。
 *	稳定性：
 *		depends
 *	描述：
 *		选择一个partitioner，然后两个指针从头尾各自开始扫描
 *		如果前面的比他大，停止，如果后面的比他小，停止，然后交换
 *
 *		迭代进行前半部分和后半部分(partitioner为分割点)
 */

#include <iostream>
using namespace std;

class QuickSort{
private:

	/**
	 * 特别注意：
	 * 这种交换方式在交换同一个内存的元素时,
	 * 会导致内存中的元素变为0。
	 * */
	void swap(int *a, int *b){
		//*a = *a + *b;
		//*b = *a - *b;
		//*a = *a - *b;
		int temp = *a;
		*a = *b;
		*b = temp;
	}
public:

	/**
	 * 选择一个分割点，将a[low~high]分隔为两部分
	 * 返回选择的分割点最终所在位置
	 * 分隔点值：随机化可以有效避免最坏时间复杂度
	 * 分隔点位置：最好在high处，在low处会麻烦一些，除非倒着扫描
	 *
	 * ###交换的思想：
	 *
	 * 这里将小于x的元素和大于x的元素划分开利用了
	 * 类似于（荷兰国旗）的思想。
	 * 即用指针i指向第一个应该被交换到后面的元素(大于x)。
	 * 然后另外用j作为扫描一遍的扫描指针，如果扫描到小于
	 * 分割点x，则将其与a[i]交换(各取所需)。
	 *
	 * 这样一遍下来，i一直向前（扩张），比x大的元素就会慢慢被
	 * （逼到）后面。扫描到a[high]的时候将其与第一个大于分割点
	 * 的元素a[i]交换即可将分隔点放到最终正确位置。
	 * 3,4,6,3,7,8,3,2,6,11,5
	 * */
	int partition(int a[], int low, int high){
		int pviot = a[high];	//最后一个元素作为分割点，否则会比较麻烦
		int p = low;			//指针p指向第一个不满足小于pviot的元素

		//扫描一遍
		for(int j=low;j<high;j++){
			if(a[j] < pviot){
				swap(&a[p], &a[j]);
				p++;
			}
		}

		//将分割点与第一个不满足小于pviot的元素交换
		swap(&a[p], &a[high]);
		return p;
	}

	/**
	 * 基于分治思想的快速排序
	 * */
	void quickSort(int a[], int low, int high){
		int p;

		//注意if的条件
		if(low < high){
			p = partition(a, low, high);	//find partition			
			quickSort(a, low, p-1);
			quickSort(a, p+1, high);
		}
	}
};

int main(){
	QuickSort qsort;
	int a[] = {12,2,16,-3,0,-1,4,10,20,6,18};

	//quickSort
	qsort.quickSort(a, 0, 10);
	for(int i=0;i<10;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	return 0;
}