C++快速排序實現(quicksort) （算法導論）

quicksort：分治思想。

分解：數組A[p, r)被劃分成兩個子數組A[p..q) 和 A[q+1, r)，使得A[p..q)中的每個元素小於等於A[q], A[q]也小於A[q+1..r)中的每個元素。q是劃分過程要返回的結果。

解決：遞歸調用quicksort，對子數組A[p..q) 和 A[q+1, r)進行排序。

合並：因為子數組都是原址排序的，所以不需要合並操作：A[p..r)已經有序。

代碼數組下標從0開始，並且所有函數使用左閉右開區間。與算法導論第三版書上的偽代碼不同的部分在注釋標出。

#include 
#include 
#include 
#include 
#include 
inline void swap(int &a, int &b)
{ int t = a; a = b; b = t; }

int partition(int *a, int p, int r) {      //對 a[p, r) 原址重排
	int x = a[r-1];                        //a[r] ==> a[r-1]
	int i = p - 1;
	for (int j = p; j < r - 1; ++j)
		if (a[j] <= x) {
			++i;
			swap(a[i], a[j]);
		}
	swap(a[i+1], a[r-1]);
	return i + 1;
}
void quicksort(int *a, int p, int r) {     //調用quicksort(a, 0, n),不是(a, 0, n-1)，區間a[0, n)
	if (p < r - 1) {                       //(p < r) ==>  (p < r - 1)
		int q = partition(a, p, r);
		quicksort(a, p, q);                //(a, p, q-1)  ==> (a, p, q)
		quicksort(a, q+1, r);
	}
}
int main()
{
	srand(time(NULL));
	int n;
	while (scanf("%d", &n)) {
		int a[n];
		for (int i = 0; i < n; ++i)
			a[i] = rand() % n;
		for (int i = 0; i < n; ++i)
			printf("%d ", a[i]);
		printf("\n");
		quicksort(a, 0, n);
		for (int i = 0; i < n; ++i)
			printf("%d ", a[i]);
		printf("\n");
	}
}