快速排序
这里我们直接开始讲相对的最优解 带随机数的三路快排 好了,中间还有很多版本的快排,但是都有一些问题导致在某种极端情况下造成耗费时间极多。
- 基础快排:在序列本身有序的情况下复杂度为O(n²)
- 带随机数的快排:在序列本身有序的情况下复杂度为O(nlogn),但是在序列全部元素相同情况下复杂度为O(n²)
- 带随机数的双路快排:比前者更快一些为O(n),因为前后同时向中间遍历,但是在序列全部元素相同情况下的复杂度问题仍旧未解决
- 带随机数的三路快排: 解决上述各种问题且时间复杂度最快O(n)
工作原理:
将数组分为三个部分,小于V的,等于V的,大于V的。
-
首先在数组中选取任意一个下标和最左边的下标互换(选取一个随机下标的目的是,将快排结果最后V左边或右边没有东西的极端情况概率降到最小甚至约等于0,如果出现这种情况将会导致复杂度为n²,这里我们不再深入讨论)
-
确定需要的变量:因此我们要有2个下标 Lt,Rt 将数组分割成3部分。还需要一个下标 i 指向当前的元素 e 。除此之外,用 l 和 r 确定数组的首尾。
-
分配当前元素 e 去哪个区域 这里我们又分为3种情况:
- e < V 将e和Lt+1处(也就是 ==V 的第一个元素)的位置交换,然后Lt++
- e == V 将e直接纳入该区域(也就是不做处理)然后 i++ 即可
- e > V 将e和Rt - 1处(也就是 >V 的前一个元素)的位置交换,然后Rt--
无论是哪个情况,无非就是将其和Lt和Rt附近的元素交换位置即可。
- 那么当全部都排序完毕时,也就是鼠标指的那个点处,i 和 Rt 重合时,退出循环
- 因为按顺序应该是 小于V ,V,==V,>V ,所以只要将V和 <V 处的最后一个元素交换位置即可
6.最后反复递归调用 <V 区间以及 >V 的区间,从而让两边的区间也都有序。文章来源:https://www.toymoban.com/news/detail-458362.html
实现一下吧:文章来源地址https://www.toymoban.com/news/detail-458362.html
package com.sort;
import java.util.Random;
/**
* @Author: 翰林猿
* @Description: 三路快排
**/
public class Quick {
public Quick() {
}
public static <T extends Comparable<T>> void quicksort(T[] arr) {
Random random = new Random();
quicksort3ways(arr, 0, arr.length - 1, random);
}
private static <T extends Comparable<T>> void quicksort3ways(T[] arr, int l, int r, Random random) {
if (l >= r)
return;
int randomInt = l + random.nextInt(r + 1 - l); //生成一个不超过数组长度的随机数
swap(arr, randomInt, l); //把他和首元素交换位置
//定义需要的变量
int Lt = l; //放在数组最左边
int Rt = r + 1; //到时候先-1再交换
int i = l + 1; //最左边的下一个开始遍历
while (i < Rt) {
if (arr[i].compareTo(arr[l]) < 0) {
Lt++; //因为应该交换Lt+1处,所以可以直接先++再交换
swap(arr, Lt, i);
i++;
} else if (arr[i].compareTo(arr[l]) == 0) {
i++;
} else if (arr[i].compareTo(arr[l]) > 0) {
Rt--; //因为应该交换Rt-1处,所以可以直接先--再交换
swap(arr, Rt, i);
}
}
swap(arr, l, Lt); //将V摆到小于V和等于V中间
quicksort3ways(arr, l, Lt - 1, random); //反复递归调用 <V 区间以及 >V 的区间,让这两区间也都有序
quicksort3ways(arr, Rt, r, random);
}
public static <E> void swap(E[] arr, int j, int beforej) {
E t = arr[j];
arr[j] = arr[beforej];
arr[beforej] = t;
}
public static void main(String[] args) {
Integer[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 10, 9};
Quick.quicksort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " "); //1,2,3,4,5,6,7,8,9,10
}
}
}
到了这里,关于三路快排Java版(带思路分析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!