快速排序 java实现 (原理-优化) 三路快排
2024-09-01 00:51:29
一、基本的快速排序
在数组中选取一个元素为基点，然后想办法把这个基点元素移动到它在排好序后的最终位置，使得新数组中在这个基点之前的元素都小于这个基点，而之后的元素都大于这个基点，然后再对前后两部分数组快速排序，直到数组排序完成。
代码实现：
public void quickSorted ( int arr[] ) {
int n = arr.length - 1; // 闭区间 [0...n]
__quickSorted (arr, 0, n);
}
private __quickSorted( int arr[], int L, int R) {
if ( (L >= R) {
return;
}
// 将基点移动到最终位置的方法
int p = __partioner(arr, L, R);
// 递归拆分数组
__quickSorted(arr, L, p - 1);
__quickSorted(arr, p + 1, R);
}
那么最大的问题就是怎么把这个基点移动到它最终应该所在的位置。
代码实现：
private int __partioner ( int arr[], int L, int R ) {
int v = arr[L];
// [L + 1, j] < v ; [j + 1, i) > v;
int j = L;
for ( int i = L + 1; i <= R; i++ ) {
if ( arr[i] < v) {
// 交换 arr[i] 和 arr [j + 1]
int tmp = arr[j + 1];
arr[j + 1] = arr[i];
arr[i] = tmp;
j++;
}
}
// 交换 arr[j] 和arr[L]
int tmp = arr[j];
arr[j] = arr[L];
arr[L] = tmp;
return j;
}
最终实现：
public void quickSorted ( int arr[] ) {
int n = arr.length - 1; // 闭区间 [0...n]
__quickSorted (arr, 0, n);
}
private __quickSorted( int arr[], int L, int R) {
if ( (L >= R) {
return;
}
// 将基点移动到最终位置的方法
int p = __partioner(arr, L, R);
// 递归拆分数组
__quickSorted(arr, L, p - 1);
__quickSorted(arr, p + 1, R);
}
private int __partioner ( int arr[], int L, int R ) {
int v = arr[L];
// [L + 1, j] < v ; [j + 1, i) > v;
int j = L;
for ( int i = L + 1; i <= R; i++ ) {
if ( arr[i] < v) {
// 交换 arr[i] 和 arr [j + 1]
int tmp = arr[j + 1];
arr[j + 1] = arr[i];
arr[i] = tmp;
j++;
}
}
// 交换 arr[j] 和arr[L]
int tmp = arr[j];
arr[j] = arr[L];
arr[L] = tmp;
return j;
}
快速排序完整代码
二、快速排序的优化
1. 快速排序的第一次优化，减小递归的深度，转而使用 选择排序
private __quickSorted( int arr[], int L, int R) {
// if ( (L >= R) {
// return;
// }
// 快速排序的第一次优化，减小递归的深度，转而使用 选择排序
if ( R - L <= 15) {
insertSorted(arr, L, R);
return;
}
// 将基点移动到最终位置的方法
int p = __partioner(arr, L, R);
// 递归拆分数组
__quickSorted(arr, L, p - 1);
__quickSorted(arr, p + 1, R);
}
// 减小递归的深度转而使用选择排序
private void insertSorted(int arr[], int L, int R) {
for (int i = L + 1; i <= R; i++) {
int i = arr[i];
int j;
for (j = i; j > L && arr[j - 1] > e; j--) {
arr[j] = arr[j - 1];
}
}
return;
}
2. 优化二，基点的选择随机化
private int __partioner ( int arr[], int L, int R ) {
// 第二次优化，将基点的选择随机化
int rand = (new Random().nextInt(R + 1)) + L;
// 交换最左侧和随机点的元素
int tmp = arr[rand];
arr[rand] = arr[L];
arr[L] = tmp;
int v = arr[L];
// [L + 1, j] < v ; [j + 1, i) > v;
int j = L;
for ( int i = L + 1; i <= R; i++ ) {
if ( arr[i] < v) {
// 交换 arr[i] 和 arr [j + 1]
int tmp = arr[j + 1];
arr[j + 1] = arr[i];
arr[i] = tmp;
j++;
}
}
// 交换 arr[j] 和arr[L]
int tmp = arr[j];
arr[j] = arr[L];
arr[L] = tmp;
return j;
}
三、两路快排
解决排序的数组中存在多数重复元素的情况
代码实现
public void quickSorted ( int arr[] ) {
int n = arr.length - 1; // 闭区间 [0...n]
__quickSorted (arr, 0, n);
}
private __quickSorted( int arr[], int L, int R) {
// if ( (L >= R) {
// return;
// }
// 快速排序的第一次优化，减小递归的深度，转而使用 选择排序
if ( R - L <= 15) {
insertSorted(arr, L, R);
return;
}
// 将基点移动到最终位置的方法
int p = __partioner(arr, L, R);
// 递归拆分数组
__quickSorted(arr, L, p - 1);
__quickSorted(arr, p + 1, R);
}
private int __partioner ( int arr[], int L, int R ) {
// 第二次优化，将基点的选择随机化
int rand = (new Random().nextInt(R + 1)) + L;
// 交换最左侧和随机点的元素
int tmp = arr[rand];
arr[rand] = arr[L];
arr[L] = tmp;
int v = arr[L];
// 两路快排的实现过程
int i = L + 1;
int j = R ;
while (true) {
while (i <= R && arr[i] < v ){
i++;
}
while (j >= L + 1 && arr[j] > v) {
j--;
}
if (i > j) {
break;
}
// 交换 i 和 j 的位置
int tmp arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
int tmp arr[L];
arr[L] = arr[j];
arr[j] = tmp;
return j;
}
// 减小递归的深度转而使用选择排序
private void insertSorted(int arr[], int L, int R) {
for (int i = L + 1; i <= R; i++) {
int i = arr[i];
int j;
for (j = i; j > L && arr[j - 1] > e; j--) {
arr[j] = arr[j - 1];
}
}
return;
}
两路快排代码实现
四、三路快排
代码实现：
public static void quickSorted3Ways(int arr[]) {
int n = arr.length -1;
// arr[0, n] 闭区间
__quickSorted3Ways(arr, 0, n);
}
private static void __quickSorted3Ways(int[] arr, int L, int R) {
// if (L >= R) {
// return;
// }
// 快速排序的第一次优化，减小递归的深度，转而使用 选择排序
if ( R - L <= 15) {
insertSorted(arr, L, R);
return;
}
// 第二次优化，将基点的选择随机化
int rand = (new Random().nextInt(R + 1)) + L;
// 交换最左侧和随机点的元素
int tmp = arr[rand];
arr[rand] = arr[L];
arr[L] = tmp;
int v = arr[L];
// partioner
// 这三个变量的初始值 ， 相当重要
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 // 此处的 i 的比较对象
while (i < gt ) {
if (arr[i] < v) {
SortedHandler.swap(arr, i, lt + 1);
lt++;
i++;
} else if (arr[i] > v) {
SortedHandler.swap(arr, i, gt - 1);
gt--;
} else {
i++;
}
}
SortedHandler.swap(arr, lt, L);
__quickSorted3Ways(arr, L, lt -1);
__quickSorted3Ways(arr, gt, R);
}
三路快排
最后附上整篇 关于快速排序从实现到逐步优化的思路图 (画到我怀疑人生了....)
最新文章
- 练习JavaScript判断上传文件后缀名
- 在Python应用中使用MongoDB
- Sunny-Code 最终版总结会议
- C#学习笔记----AppDomain应用程序域
- 32、mybatis
- javascript内建对象
- jQuery Jcrop API参数说明(中文版)(转)(图片剪切)
- GridView不換行
- GraphViz web版
- MyBatis魔法堂：Insert操作详解
- 【PHP】制作日历
- 自己动手编写IOC框架（四）
- Redis进阶实践之十八 使用管道模式加速Redis查询
- LeetCode之“散列表”：Two Sum && 3Sum && 3Sum Closest && 4Sum
- elementUi源码解析(1)--项目结构篇
- dpr,ppi,dip,viewport的一些概念
- linux 开机自启
- 异常类Exception(String message, Throwable cause)中的cause理解
- centos6.8安装具有ngx_cache_purge模块的nginx1.10.3
- Bootstrap-CL：标签