「排序算法」专题 6:快速排序(第 1 节)
参考资料:https://www.yuque.com/liweiwei1419/algo/nrwxk6
- 基本思路:快速排序每一次都排定一个元素(这个元素呆在了它最终应该呆的位置),然后递归地去排它左边的部分和右边的部分,依次进行下去,直到数组有序;
- 算法思想:分而治之(分治思想),与「归并排序」不同,「快速排序」在「分」这件事情上不想「归并排序」无脑地一分为二,而是采用了 partition 的方法(书上,和网上都有介绍,就不展开了),因此就没有「合」的过程。
- 实现细节(注意事项):(针对特殊测试用例:顺序数组或者逆序数组)一定要随机化选择切分元素(
pivot
),否则在输入数组是有序数组或者是逆序数组的时候,快速排序会变得非常慢(等同于冒泡排序或者「选择排序」);
以下是针对特殊测试用例(有很多重复元素的输入数组)有 3 种版本的快排:
- 版本 1:基本快排:把等于切分元素的所有元素分到了数组的同一侧,可能会造成递归树倾斜;
- 版本 2:双指针快排:把等于切分元素的所有元素等概率地分到了数组的两侧,避免了递归树倾斜,递归树相对平衡;
- 版本 3:三指针快排:把等于切分元素的所有元素挤到了数组的中间,在有很多元素和切分元素相等的情况下,递归区间大大减少。
这里有一个经验的总结:之所以快排有这些优化,起因都是来自「递归树」的高度。关于「树」的算法的优化,绝大部分都是在和树的「高度」较劲。类似的通过减少树高度、使得树更平衡的数据结构还有「二叉搜索树」优化成「AVL 树」或者「红黑树」、「并查集」的「按秩合并」与「路径压缩」。
- 写对「快速排序」的技巧:保持「循环不变量」,即定义的变量在循环开始前、循环过程中、循环结束以后,都保持不变的性质,这个性质是人为根据问题特点定义的。
- 「循环不变量」的内容在《算法导论》这本书里有介绍。我个人觉得非常有用。「循环不变量」是证明算法有效性的基础,更是写对代码的保证,遵守循环不变量,是不是该写等于号,先交换还是先
++
,就会特别清楚,绝对不会写错,我在编码的时候,会将遵守的「循环不变量」作为注释写在代码中。
快速排序丢失了稳定性,如果需要稳定的快速排序,需要具体定义比较函数,这个过程叫「稳定化」,在这里就不展开了。
使用「快速排序」解决的经典问题(非常重要):
- TopK 问题:「力扣」第 215 题:数组中的第 K 个最大元素;
- 荷兰国旗问题:「力扣」第 75 题:颜色分类。
不好意思,我又来啰嗦了:《算法 4》这本书里面的代码风格是极其不推荐的。代码是写给人看的,应该尽量避免代码个人风格化,采用统一规范的写法,保证易读性,可扩展性。
Java 代码:(下面提供了快排的三个版本,供参考)
说明:
lt
是less than
的缩写,表示(严格)小于;gt
是greater than
的缩写,表示(严格)大于;le
是less than or equal
的缩写,表示小于等于(本代码没有用到);ge
是greater than or equal
的缩写,表示大于等于(本代码没有用到)。
import java.util.Random;
public class Solution {
// 快速排序 1:基本快速排序
/**
* 列表大小等于或小于该大小,将优先于 quickSort 使用插入排序
*/
private static final int INSERTION_SORT_THRESHOLD = 7;
private static final Random RANDOM = new Random();
public int[] sortArray(int[] nums) {
int len = nums.length;
quickSort(nums, 0, len - 1);
return nums;
}
private void quickSort(int[] nums, int left, int right) {
// 小区间使用插入排序
if (right - left <= INSERTION_SORT_THRESHOLD) {
insertionSort(nums, left, right);
return;
}
int pIndex = partition(nums, left, right);
quickSort(nums, left, pIndex - 1);
quickSort(nums, pIndex + 1, right);
}
/**
* 对数组 nums 的子区间 [left, right] 使用插入排序
*
* @param nums 给定数组
* @param left 左边界,能取到
* @param right 右边界,能取到
*/
private void insertionSort(int[] nums, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int temp = nums[i];
int j = i;
while (j > left && nums[j - 1] > temp) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = temp;
}
}
private int partition(int[] nums, int left, int right) {
int randomIndex = RANDOM.nextInt(right - left + 1) + left;
swap(nums, left, randomIndex);
// 基准值
int pivot = nums[left];
int lt = left;
// 循环不变量:
// all in [left + 1, lt] < pivot
// all in [lt + 1, i) >= pivot
for (int i = left + 1; i <= right; i++) {
if (nums[i] < pivot) {
lt++;
swap(nums, i, lt);
}
}
swap(nums, left, lt);
return lt;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
Python 代码:
from sorting.sorting_util import SortingUtil
class QuickSort:
def __str__(self):
return "最基本的快速排序"
def __partition(self, arr, left, right):
"""对区间 [left, right] (包括左右端点)执行 partition 操作,将 pivot 挪到它最终应该在的位置"""
pivot = arr[left]
lt = left
# 循环不变式
# [left, lt - 1] < pivot,初始时,lt - 1 = left - 1
# [lt, i) >= pivot,初始时,[left, left + 1)
# i 的性质在循环开始的时候,不能推测出,我们就是要在循环中保持这个性质
for i in range(left + 1, right + 1):
if arr[i] < pivot:
lt += 1
arr[lt], arr[i] = arr[i], arr[lt]
arr[left], arr[lt] = arr[lt], arr[left]
return lt
def __quick_sort(self, nums, left, right):
"""在区间 [left, right] (包括左右端点)执行快速排序操作"""
if left >= right:
return
p_index = self.__partition(nums, left, right)
self.__quick_sort(nums, left, p_index - 1)
self.__quick_sort(nums, p_index + 1, right)
def sort(self, arr):
size = len(arr)
self.__quick_sort(arr, 0, size - 1)
(本节完)