《算法导论》笔记2-7

快速排序

与归并排序一样，快速排序也使用了分治思想，下面是对一个典型的子数组 A[low … high] 进行快速排序的三步分支过程：

1. 分解：数组 A[low … high] 被划分为两个子数组 A[low … mid - 1] 和 A[mid + 1 … high]，使得 A[low … mid - 1] 中的每一个元素都小于等于 A[mid]，而 A[mid] 也小于等于 A[mid + 1 … high] 中的每个元素。
2. 解决：通过递归调用快速排序，对子数组 A[low … mid - 1] 和 A[mid + 1 … high] 进行排序。
3. 合并：因为子数组都是原址排序的，所以不需要合并操作：数组 A[low … high] 已经有序。

伪代码：

quick_sort(A, low, high)
	if low < high
		mid = partition(A, low, high)
		quick_sort(A, low, mid - 1)
		quick_sort(A, mid + 1, high)

算法的关键就是 partition(A, low, high) 划分过程，它实现对子数组 A[low … high] 的原址重排：

partition(A, low, high)
	x = A[high]
	i = low - 1
	for j in range(low, high - 1)
		if A[j] <= x
			i++
			swap(A[i], A[j])
	swap(A[i + 1], A[high])
	return i + 1

Java 代码：

int partition(int[] A, int low, int high) {
	int x = A[high];
	int i = low - 1;
	for (int j = low; j < high; j++) {
		if (A[j] <= x) {
			i++;
			swap(A, i, j);
		}
	}
	swap(A, i + 1, high);
	return i + 1;
}

void quickSort(int[] A, int low, int high) {
	if (low < high) {
		int mid = partition(A, low, high);
		quickSort(A, low, mid - 1);
		quickSort(A, mid + 1, high);
	}
}

快速排序的随机版

在讨论快速排序的平均情况性能时，我们是假设了：输入数据的所有排列都是等概率的。但实际情况下，这个假设并不总是成立。为了使所有的输入都能获得较好的性能，我们可以在算法中引入随机性。

划分前进行一次随机交换：

randomized_partition(A, low, high)
	i = random(low, high)
	swap(A[high], A[i])
	return partition(A, low, high)

快速排序中的划分改成上面的划分：

randomized_quicksort(A, low, high)
	if low < high
		mid = randomized_partition(A, low, high)
		randomized_quicksort(A, low, mid - 1)
		randomized_quicksort(A, mid + 1, high)