两路快速排序

基本概念

算法解释

1. 在两路快速排序中，我们首先选择第一个元素作为基准值，然后设置两个指针i和j分别指向数组的头部和尾部。

2. 两个指针分别向中间移动，右指针j寻找比基准值小的元素，左指针i寻找比基准值大的元素，当找到这样的一对元素时，交换它们的位置。注意：需要先移动右指针j！

3. 重复这个过程直到两个指针相遇，此时便找到基准值所在位置j。

4. 交换基准值与右指针j所指元素，一次分区流程即结束。

5. 递归左区间以及右区间，重复执行上述步骤，直到每个区间内剩下1个或0个元素，排序终止。

代码示例

过程说明

优势

三向切分快速排序

基本概念

算法解释

1. 选取基准值：与其他快速排序变体类似，需要选取一个基准值。

2. 分区操作：
1. 初始化三个指针，lt（小于区的右边界），gt（大于区的左边界）和i（当前考察的元素指针）。开始时，lt指向数组头部，gt指向数组末尾，i指向数组头部下一个。
2. 从i位置开始，向右遍历数组，直到i与gt相遇。对于每个元素，进行如下操作：
• 如果arr[i] < pivot，将arr[i]与arr[lt]交换，然后lt和i都向右移动一位。
• 如果arr[i] > pivot，将arr[i]与arr[gt]交换，gt向左移动一位，i不动。
• 如果arr[i] == pivot，i向右移动一位。
3. 经过上述步骤后，数组被分为三部分：索引lt左侧的所有元素都小于基准值，索引lt到gt之间的所有元素都等于基准值，索引gt右侧的所有元素都大于基准值。
4. 对lt左侧和gt右侧的子数组递归执行上述步骤。

3. 递归排序：分别对小于和大于基准值的部分递归进行快速排序，不需要对等于基准值的部分进行排序，因为它们已经处于正确的位置。

代码示例

过程说明

解决的问题

参考文章