随机化快速排序学习笔记

介绍

随机化快速排序是一种非常常用的排序算法。其时间复杂度为 $O(n\log n)$，是目前最优秀的排序算法之一。

思路

随机化快速排序的思路是基于分治的思想，将问题划分为更小的子问题来解决。

具体步骤如下：

1. 从数列中选择一个元素作为基准点（pivot）。
2. 将所有小于基准点的元素放到该元素左边，所有大于基准点的元素放到该元素右边。
3. 分别对左边和右边的子序列做递归调用，直至子序列大小为 1 或 0。

实例

假设有以下一组数字需要进行排序：

Copy Code
6, 8, 3, 7, 1, 9, 5, 4, 2

选取其中一个数字作为基准点，我们可以随机选择5作为基准点。然后将小于5的数字放在左侧，大于5的数字放在右侧：

Copy Code
3, 1, 4, 2, 5, 8, 7, 9, 6

现在我们已经将原始序列划分为两个子序列，再次对子序列进行递归调用，直到子序列大小为 1 或 0。此时，整个序列已经被排序完成：

Copy Code
1, 2, 3, 4, 5, 6, 7, 8, 9

结论

随机化快速排序是一种非常高效的排序算法，其时间复杂度为 $O(n\log n)$。虽然在极端情况下（基准点选择不合适）可能会导致时间复杂度达到 $O(n^2)$，但这种情况的概率非常小，因此随机化快速排序在实际应用中表现很好。