排序算法之快速排序

快速排序，简称快排。也利用了分治思想。

快速排序是这样的：

如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot(分区点)。我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。
根据分治、递归的处理思想，我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有数据都有序了。

递推公式：

递推公式：
quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1,r)

终止条件：
p >= r

将递推公式转化为代码：

//快速排序，A是数组，n表示数组的大小
quick_sort(A,n){
	quick_sort_c(A,0,n-1)
}

//快速排序递归函数，p,r为下标
quick_sort_c(A，p,r){
	if p>=r then return 

	q=partition(A,p,q-1)  //获取分区点
	quick_sort_c(A,p,q-1)
	quick_sort_c(A,q+1,r)
}

这里涉及一个partition()分区函数。而它的作用就是：随机选择一个元素作为pivot，然后对A[p…r]分区，函数返回pivot的下标。

partition(A,p,r){
	pivot := A[r]
	i := p
	for j:=p to r-1 do {
		if A[j] < pivot {
			swap A[i] with A[j]
			i := i+1
		}
	}
	swap A[i] with A[r]
	return i
}

我们通过游标 i 把 A[p…r-1] 分成两部分。其中 i 左边表示已经处理的，其中 j 表示一种遍历，从 i 开始往右一次与 pivot 比较，如果小于 pivot，那么，就把元素换到 i 的位置，同时 i 加1。最后，返回 i 的值作为分区点， i 左边的小于它，右边的大于它。

此分区函数的思路：i和j都从第一个元素开始，用 j 依次与pivot比较，如果比pivot小，则把它放到i的左边，同时 i 右移 ，j 也右移；最后把pivot和 i 位置的元素交换

分区示例图如下