算法-快速排序.md

快速排序

简介

快速排序使用了分治思想：

1. 分解：数组 A[p..r] 被划分为两个(可能为空)子数组 A[p..q-1] 和 A[q+1..r]，使得 A[p..q-1] 中的每一个元素都小于等于 A[q]，而 A[q] 也小于等于 A[q+1..r] 中的每个元素。其中，计算下标 q 也是划分过程的一部分。
2. 解决：通过递归调用快速排序，对子数组 A[p..q-1] 和 A[q+1..r]进行排序。
3. 合并：因为子数组都是原址排序的，所以不需要合并操作：数组 A[p..r] 已经有序。

实现

分解

QUICKSORT 通过递归调用将数组分解成长度不等的子数组。

解决

算法的关键部分是 PARTITION 过程，它实现了对子数组 A[p..r] 的原址重排。

PARTITION 选择一个 x=A[r] 作为主元(pivot element)，并围绕它来划分子数组。

对于任意数组下标 k,有：

1. 若 p<=k<=i,则 A[k]<=x
2. 若 i+1<=k<=j-1,则A[k]>x
3. 若 k=r，则 A[k]=x

随着程序的执行，数组被划分成 4 个(可能有空的)区域，基于数组下标 k，区域分别为：

1. 若 p<=k<=i，则区域内的元素均小于 x
2. 若 i<k<j，则区域内的元素均大于 x
3. 若 j<=k<r，则区域内的元素均未遍历到，与 x 之间的大小关系仍未知
4. 若 k=r，则区域内的元素仅有一个便是 x

当程序运行结束，区域 3 内的元素全部遍历完成后，数组就只剩下 3 个区域，如图 (i) 所示：

1. 值均小于元素 x 的区域，索引均在元素 x 左边
2. 值均大于元素 x 的区域，索引均在元素 x 右边
3. 元素 x 组成的区域

复杂度

快速排序的运行时间依赖于划分是否平衡，平均的时间复杂度为 O(nlgn)，因为快速排序是原址重排，没有新建空间存储数组，所以空间复杂度取决于递归所损耗的空间，为 O(lgn)

最坏情况划分

当划分产生的两个子问题分别包含了 n-1 个元素和 0 个元素时，快速排序效率是最低的，递归树如下所示，这时分解的时间复杂度是 O(n),解决的时间复杂度是 O(n),总的复杂度为 O(n^2)

最好情况划分

在平衡的划分中，PATITION 得到的两个子问题的规模都不大于 n/2，递归树如下所示，这时快速排序分解的效率如归并排序分解一样是 O(lgn)，解决的时间固定是 O(n)，总的复杂度为 O(nlgn)

平衡的划分

假设划分算法总是产生 9:1 的划分，于是可以得出如下递归树：

go 实现

快排在实现上有很多版本，在这里给出的是依据以上伪代码实现的。

type QuickSort struct {
	Value []int
}

func (q *QuickSort) Sort() ([]int, error) {
	quickSort(q.Value, 0, len(q.Value)-1)
	return q.Value, nil
}

func quickSort(s []int, l, r int) {
	if l < r {
		q := patition(s, l, r)
		quickSort(s, l, q-1)
		quickSort(s, q+1, r)
	}

}
func patition(s []int, l, r int) int {
	key, index := s[r], l-1

	for j := l; j < r; j++ {
		if s[j] <= key {
			index++
			s[index], s[j] = s[j], s[index]
		}
	}
	s[index+1], s[r] = s[r], s[index+1]
	return index + 1
}