三向快速排序¶
一、算法描述¶
1.1 核心思想¶
- 三分，选取一个分区值，将数据分割成 3 部分：小于、等于、大于
- 递归，对小于大于两部分继续排序，不断选点分割数据，直到无法分割为止
- 整个过程和快速排序类似，只是原来的一个分区点变成了一个区间而已
1.2 细节解释¶
比如说， 数组 [3, 5, 2, 1, 3, 5, 1]。
首先选取一个分区值（随意选一个），比如说 3。
以 3 基准，将其他数据分割成 3 部分：小于 3、等于 3、大于 3。
小于3 等于3 大于3
___ ___ ___ ___ ___ ___ ___
| 2 | 1 | 1 | | 3 | 3 | | 5 | 5 |
等于 3 的部分就不用管了，因为已经排好了。
接着对小于 3 和大于 3 的部分进行递归排序。
(1) 先对小于 3 的部分排序
首先选取一个分区值 2，然后以 2 为基准分割成 3 部分：
小于2 等于2 大于2
___ ___ ___
| 1 | 1 | | 2 |
等于 2 的部分就不用管了，因为已经排好了。
接着对小于 2 和大于 2 的部分进行递归排序，最终可以得到：
___ ___ ___
| 1 | 1 | 2 |
(2) 再对大于 3 的部分排序
一样地，选取一个分区值 5，然后以 5 为基准分割成 3 部分：
小于5 等于5 大于5
___ ___
| 5 | 5 |
等于 5 的部分就不用管了，因为已经排好了。
至此，整个排序实际上已经拍好了，结果就是：
___ ___ ___ ___ ___ ___ ___
| 1 | 1 | 2 | 3 | 3 | 5 | 5 |
三向快速排序和快速排序差不多，只是中间的单个元素变成了一个区间而已。
但是，如果数组中有大量重复元素，三向快速排序的效率会比快速排序高很多。
二、算法实现¶
private void partSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
// 三分数据（小于、等于、大于）
int x = arr[start];
int lp = start - 1, rp = end;
for (int i = lp + 1; i < rp; ) {
if (arr[i] < x) {
swap(arr, i++, ++lp);
} else if (arr[i] > x) {
swap(arr, i, --rp);
} else {
i++;
}
}
// 对小于的部分排序
partSort(arr, start, lp + 1);
// 对大于的部分排序
partSort(arr, rp, end);
}
三、算法分析¶
3.1 时间复杂度¶
- 最好时间复杂度：O(nlogn)
- 最坏时间复杂度：O(n^2)
- 平均时间复杂度：O(nlogn)
3.2 空间复杂度¶
- 空间复杂度：O(logn)
- 原地算法
3.3 稳定性¶
- 不稳定排序算法
四、适用场景¶
- 含有大量重复元素
附录¶
/**
* 三向快速排序
* <p>
* 时间复杂度：最好 O(nlogn) 最差 O(n^2) 平均 O(nlogn)
* <p>
* 空间复杂度：O(logn)
* <p>
* 稳定性：不稳定
*
* @author weijiaduo
* @since 2023/4/16
*/
public class Quick3WaySort implements Sort {
@Override
public void sort(int[] arr) {
partSort(arr, 0, arr.length);
}
/**
* 递归排序
*
* @param arr 数组
* @param start [start, end)
* @param end [start, end)
*/
private void partSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
// 三分数据（小于、等于、大于）
int x = arr[start];
int lp = start - 1, rp = end;
for (int i = lp + 1; i < rp; ) {
if (arr[i] < x) {
swap(arr, i++, ++lp);
} else if (arr[i] > x) {
swap(arr, i, --rp);
} else {
i++;
}
}
// 对小于的部分排序
partSort(arr, start, lp + 1);
// 对大于的部分排序
partSort(arr, rp, end);
}
}