快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
基本思想是, 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法过程描述
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot (分区点), 我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
逻辑演示
剩下, 可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。
动图演示
quickSort.gif
复杂度
用大O表示法，忽略常量、低阶和常数系数。
时间复杂度为：最坏O(n²), 最好O(nlogn)
空间复杂度为：并未开辟额外空间, 所以为O(1)
稳定性: 不稳定
代码实现(Swift)
var numbers = [6,8,7,6,3,5,9,4]
func quickSort(numbers: inout [Int], leftIndex: Int, rightIndex: Int) {
if leftIndex >= rightIndex {
return
}
var i = leftIndex;
var j = rightIndex;
// 记录比较基准数
var pivot = numbers[i]
while i < j {
// 首先从右边j开始查找比基准数小的值
while i < j && numbers[j] >= pivot {
// 如果比基准数大，不需要做什么操作, 接续往前查找
j -= 1
}
// 如果比基准数小，则将查找到的小值调换到i的位置
numbers[i] = numbers[j]
print("\n\(numbers) bigger change \(j)th to \(i)th")
// 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值
while i < j && numbers[i] <= pivot {
// 如果比基准数小，不需要做什么操作, 接续往后查找
i += 1
}
// 如果比基准数大，则将查找到的大值调换到j的位置
numbers[j] = numbers[i]
print("\n\(numbers) smaller change \(i)th to \(j)th")
}
// 比较一次之后, 将基准数放到正确位置
numbers[i] = pivot;
print("\n\(numbers)")
/**** 递归排序 ***/
// 排序基准数左边的
quickSort(numbers: &numbers, leftIndex: leftIndex, rightIndex: i-1)
// 排序基准数右边的
quickSort(numbers: &numbers, leftIndex: i+1, rightIndex: rightIndex)
}
quickSort(numbers: &numbers, leftIndex: 0, rightIndex: numbers.count-1)
print(numbers)
终端打印结果：
[4, 8, 7, 6, 3, 5, 9, 4] bigger change 7th to 0th
[4, 8, 7, 6, 3, 5, 9, 8] smaller change 1th to 7th
[4, 5, 7, 6, 3, 5, 9, 8] bigger change 5th to 1th
[4, 5, 7, 6, 3, 7, 9, 8] smaller change 2th to 5th
[4, 5, 3, 6, 3, 7, 9, 8] bigger change 4th to 2th
[4, 5, 3, 6, 3, 7, 9, 8] smaller change 4th to 4th
[4, 5, 3, 6, 6, 7, 9, 8]
[3, 5, 3, 6, 6, 7, 9, 8] bigger change 2th to 0th
[3, 5, 5, 6, 6, 7, 9, 8] smaller change 1th to 2th
[3, 5, 5, 6, 6, 7, 9, 8] bigger change 1th to 1th
[3, 5, 5, 6, 6, 7, 9, 8] smaller change 1th to 1th
[3, 4, 5, 6, 6, 7, 9, 8]
[3, 4, 5, 6, 6, 7, 9, 8] bigger change 2th to 2th
[3, 4, 5, 6, 6, 7, 9, 8] smaller change 2th to 2th
[3, 4, 5, 6, 6, 7, 9, 8]
[3, 4, 5, 6, 6, 7, 9, 8] bigger change 5th to 5th
[3, 4, 5, 6, 6, 7, 9, 8] smaller change 5th to 5th
[3, 4, 5, 6, 6, 7, 9, 8]
[3, 4, 5, 6, 6, 7, 8, 8] bigger change 7th to 6th
[3, 4, 5, 6, 6, 7, 8, 8] smaller change 7th to 7th
[3, 4, 5, 6, 6, 7, 8, 9]
[3, 4, 5, 6, 6, 7, 8, 9]
- 稳定性
如果数组中有两个相同的元素，比如测试的序列numbers: (6，8，7，6，3，5，9，4)，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，
快速排序并不是一个稳定的排序算法。
- 快速排序的性能分析
最好的情况下, 选择的 pivot 都很合适，正好能将大区间对等地一分为二。这时快排的时间复杂度递推求解公式跟归并是相同的。即为O(nlogn)。
最坏的情况下, 有序数组中, 每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2).
T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化到 O(n2)。
回目录:常用的排序算法
结语
路漫漫其修远兮，吾将上下而求索~
.End
网友评论