简单的快排

性能分析

空间效率

由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为[log₂(n+1)]；最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n)；平均情况下，栈的深度为O(log₂n)。因而空间复杂度在最坏情况下为O(n)，在平均情况下为O(log₂n)。

时间效率

快速排序的运行时间与划分是否对称有关，而后者又与具体使用的划分算法有关。快速排序的最坏情况发生在两个区域分别包含n- 1个元素和0个元素时，这种最大程度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为O(n²)。

有很多方法可以提高算法的效率。一种方法是当递归过程中划分得到的子序列的规模较小时不要再继续递归调用快速排序，可以直接采用直接插入排序算法进行后续的排序工作。另一种方法就是尽量选取一个可以将数据中分的枢轴元素。如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；或者随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。

在最理想的状态下，即Partition()可能做到最平衡的划分中，得到的两个子问题的大小都不可能大于n/2，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为O(nlog₂n)。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法

稳定性

在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。例如，表L={3,2, 2}，经过一-趟排序后L= {2,2, 3}，最终排序序列也是L= {2,2,3},显然，2与2的相对次序已发生了变化。

注意:在快速排序算法中，并不产生有序子序列，但每趟排序后会将一个元素（基准元素）放到其最终位置的信置上。

Code


void quickSort(int A[],int left,int right){
	if(left<right){
		int pos = partition(A,left,right);
		quickSort(A,left,pos-1);
		quickSort(A,pos+1,right);
	}
}

//二分：枢轴左侧的值比其小，右侧的值比其大。
int partition(int A[],int left,int right){
	int temp = A[left];
	while(left<right){
		while(left<right&&A[right]>temp)right--;//反复左移right，直到遇到比temp小的
			A[left]=A[right];
		while(left<right&&A[left]<temp)left++
			A[right]=A[left];
	}
	A[left]=temp;
	return left;
}