三路快速排序
对于快速排序，如果排序的数组中有很多的重复数如10000个【1，9】的数就有很多重复数，由于快速排序的判定问题，会导致这些重复数移到一边从而大幅增加算法的运算时间。解决方法，就是进行三路排序，分层>,=,<.
下面来介绍三路排序算法：
文章图片
分成3块
文章图片
当比较点e
文章图片
单e>v时交换i处的元素与gt-1处的元素，i不变，gt--；
文章图片
这是最后排序完成的图像
文章图片
将l处的元素与lt处的元素交换即可。 以下是算法实现：
package bobo.algo;
import java.util.*;
public class QuickSort3Ways {
// 我们的算法类不允许产生任何实例
private QuickSort3Ways(){}
// 递归使用快速排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r){
// 对于小规模数组, 使用插入排序
if( r - l <=15 ){
InsertionSort.sort(arr, l, r);
return;
}
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr, l, (int)(Math.random()*(r-l+1)) + l );
Comparable v = arr[l];
int lt = l;
// arr[l+1...lt] < v
int gt = r +1;
// arr[gt...r] > v
int i = l+1;
// arr[lt+1...i) == v
while( i < gt ){
if( arr[i].compareTo(v) <0 ){
swap( arr, i, lt+1);
i ++;
lt ++;
}
else if( arr[i].compareTo(v) >0 ){
swap( arr, i, gt-1);
gt --;
}
else{// arr[i] == v
i ++;
}
}
swap( arr, l, lt );
sort(arr, l, lt-1);
sort(arr, gt, r);
}
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
}
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// 测试QuickSort3Ways
public static void main(String[] args) {
// 三路快速排序算法也是一个O(nlogn)复杂度的算法
// 可以在1秒之内轻松处理100万数量级的数据
int N =1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("bobo.algo.QuickSort3Ways", arr);
return;
}
【三路快速排序】}
推荐阅读
- 一个选择排序算法
- 排序（归并排序）
- 【图解】9张图彻底搞懂堆排序
- neo4j|neo4j cql语句 快速查询手册
- 通过复盘快速成长（附模板）
- jar|springboot项目打成jar包和war包，并部署（快速打包部署）
- 快速阅读作业【2/21】《阅读（革命性新定义》）
- Spring注解05|Spring注解05 @Import 给容器快速导入一个组件
- vue|vue 上移 下移 删除 排序
- 必须掌握的八种基本排序算法