当前位置:网站首页>随机快排时间复杂度是N平方?
随机快排时间复杂度是N平方?
2022-08-09 12:00:00 【爱敲代码的Harrison】
数组分区—partition
给定一个数组arr,和一个整数num,请把小于等于num的数放在数组左边,大于num的数放在右边。
分析:设计一个<=区,该区域一开始在数组左侧,只用一个变量记录它的右边界,所以一开始<=区在下标为-1的位置,然后开始遍历数组(0,1,2…N-1)
遍历规则:
- i位置的数[i] <= num:把当前数和<=区的下一个数交换,然后<=区向右扩一个位置,当前数跳到下一个(i++)
- [i] > num:什么也不干,直接i++
题目升级
将数组分为三段,[< | = | >] ——经典的荷兰国旗问题,小于部分和大于部分可以无序。
分析
设计一个>区,往左扩,<区,往右扩,i位置从左往右遍历,必然会中三中逻辑:
- [i] == num:直接i++
- [i] < num:[i]与<区的下一个数(或者说右一个数)交换,然后<区右扩一个,i++
- [i] > num:[i]与>区的左一个数交换,然后>区左扩,i停在原地
- 什么时候停?i和>区的左边界撞上的时候
随机快排
- 快排1.0版本:以arr[R]做划分值,进行一次partition搞定一个数,然后左侧范围区递归,以左侧范围的arr[R]做划分值,右侧同理,周而复始
- 快排2.0版本:与1.0一样,但是一次能搞定等于arr[R]的一批数
- 快排3.0版本:随机选一个数(如[i]位置的数),将其与arr[R]交换之后,以arr[R]做划分值。就等同于随机选一个数拿它做划分值,剩下的所有过程跟快排2.0一样
随机快排时间复杂度分析
- 划分值越靠近中间,性能越好,越靠近两边,性能越差
- 随机选一个数进行划分的目的就是让好情况和坏情况都变成概率事件
- 把每一种情况都列出来,会有每种情况下的时间复杂度,但概率都是1/N
- 把每一种情况都考虑,时间复杂度就是这种概率模型下的长期期望
- 时间复杂度O(N*logN)和额外空间复杂度O(logN)都是这么来的
- 快排为什么要用递归运行,因为要记录每一个中点的位置或划分点的位置,递归空间就是每次记录划分值的空间,这是避免不掉的。
package com.harrison.java;
public class test {
// 在数组arr[L...R]上,以arr[R]做划分值
// 小于等于arr[R]的数放左侧(左侧的数可以无序)
// 大于arr[R]的数放右侧(右侧的数可以无序)
public static int partition(int[] arr,int L,int R) {
if(L>R) {
return -1;
}
if(L==R) {
return L;
}
int lessEqual=L-1;// 小于等于区的右边界
int index=L;// 当前位置
while(index<R) {
if(arr[index]<=arr[R]) {
swap(arr, index, ++lessEqual);
}
index++;
}
// L...lessEqual lessEqual+1...R-1 R
// L.............lessEqual+1 lessEqual+2...R
swap(arr, ++lessEqual, R);
return lessEqual;
}
// arr[L...R] 玩荷兰国旗问题的划分,以arr[R]做划分值
// <arr[R] | ==arr[R] | >arr[R]
public static int[] netherlandFlags(int[] arr,int L,int R) {
if(L>R) {
return new int[] {
-1,-1};
}
if(L==R) {
return new int[] {
L,R};
}
int less=L-1;// 小于区右边界
int more=R;// 大于区左边界
int index=L;// 当前位置
while(index<more) {
// 当前位置,不能和 >区的左边界撞上
if(arr[index]==arr[R]) {
index++;
}else if(arr[index]<arr[R]) {
swap(arr, index++, ++less);
}else {
swap(arr, index, --more);
}
}
// L...less less+1...more-1 more...R-1 R
// L...less less+1..........more more+1...R
swap(arr, more, R);
return new int[] {
less+1,more};
}
public static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
//快排1.0
public static void quickSort1(int[] arr) {
if(arr==null || arr.length<2) {
return ;
}
process1(arr, 0, arr.length-1);
}
public static void process1(int[] arr,int L,int R) {
if (L >= R) {
return;
}
int M=partition(arr, L, R);
process1(arr, L, M-1);
process1(arr, M+1, R);
}
//快排2.0
public static void quickSort2(int[] arr) {
if(arr==null || arr.length<2) {
return ;
}
process2(arr, 0, arr.length-1);
}
public static void process2(int[] arr,int L,int R) {
if (L >= R) {
return;
}
int[] equalArea=netherlandFlags(arr, L, R);
process2(arr, L, equalArea[0]-1);
process2(arr, equalArea[1]+1, R);
}
public static void quickSort3(int[] arr) {
if(arr==null || arr.length<2) {
return ;
}
process3(arr, 0, arr.length-1);
}
//快排3.0
public static void process3(int[] arr,int L,int R) {
if (L >= R) {
return;
}
swap(arr, L+(int)(Math.random()*(R-L+1)), R);
int[] equalArea=netherlandFlags(arr, L, R);
process3(arr, L, equalArea[0]-1);
process3(arr, equalArea[1]+1, R);
}
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int testTimes=1000000;
int maxValue=100;
int maxSize=100;
boolean succeed=true;
for(int i=0; i<testTimes; i++) {
int[] arr1=generateRandomArray(maxSize, maxValue);
int[] arr2=copyArray(arr1);
int[] arr3=copyArray(arr1);
quickSort1(arr1);
quickSort2(arr2);
quickSort3(arr3);
if(!isEqual(arr1, arr2) || !isEqual(arr2, arr3)) {
succeed=false;
printArray(arr1);
printArray(arr2);
printArray(arr3);
break;
}
}
System.out.println(succeed?"Nice":"Oops");
}
}
边栏推荐
- LeetCode #101. Symmetric Binary Tree
- MySQL中的锁
- LeetCode 1413.逐步求和得到正数的最小值
- 1小时直播招募令:行业大咖干货分享,企业报名开启丨量子位·视点
- 鹅厂机器狗花式穿越10m梅花桩:前空翻、单桩跳、起身作揖...全程不打一个趔趄...
- Ways to prevent data fraud
- The FFmpeg library is configured and used on win10 (libx264 is not configured)
- 荣耀携手Blue Yonder,加快企业战略增长
- 程序员的专属浪漫——用3D Engine 5分钟实现烟花绽放效果
- 阿里云新增三大高性能计算解决方案,助力生命科学行业快速发展
猜你喜欢
LeetCode #101. Symmetric Binary Tree
AQS Synchronization Component - FutureTask Analysis and Use Cases
h264协议
GPT-3组合DALL·E,60秒内搞定游戏设定和原型动画!网友看后:这游戏想玩
1小时直播招募令:行业大咖干货分享,企业报名开启丨量子位·视点
LeetCode #101. 对称二叉树
8、IDEA提交代码出现: Fetch failed fatal: Could not read from remote repository
已解决IndentationError: unindent does not match any oute r indentation Level
#物联网征文#小熊派设备开发实战
2022牛客多校(六)M. Z-Game on grid
随机推荐
张朝阳对话俞敏洪:一边是手推物理公式,一边是古诗信手拈来
MongoDB-查询中$all的用法介绍
推荐一个免费50时长的AI算力平台
荣耀携手Blue Yonder,加快企业战略增长
How to upload local file trial version in binary mode in ABAP report
The latest interview summary in 20022 brought by Ali senior engineer is too fragrant
WeChat payment development process
ABAP 面试题:如何使用 ABAP 编程语言的 System CALL 接口,直接执行 ABAP 服务器所在操作系统的 shell 命令?
Simple understanding of ThreadLocal
OpenSSF的开源软件风险评估工具:Scorecards
Gumbel_Softmax 概要
Blocking, non-blocking, multiplexing, synchronous, asynchronous, BIO, NIO, AIO all in one pot
Common gadgets of Shell (sort, uniq, tr, cut)
Manchester city launch emotional intelligence scarf can be detected, give the fans
水能自发变成“消毒水”,83岁斯坦福教授:揭示冬天容易得流感的部分原因...
国产抗新冠口服药每瓶不超300元/ 我国IPv6网络全面建成/ 谷歌入局折叠屏手机...今日更多新鲜事在此...
[Interview high-frequency questions] Linked list high-frequency questions that can be gradually optimized
GET请求和POST请求区别
阻塞、非阻塞、多路复用、同步、异步、BIO、NIO、AIO 一锅端
900页数学论文证明旋转的黑洞不会爆炸,丘成桐:30多年来广义相对论首次重大突破...