当前位置:网站首页>随机快排时间复杂度是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");
}
}
边栏推荐
- Two minutes recording can pass by second language!The volcano how to practice and become voice tone reproduction technology?
- WPF implements a MessageBox message prompt box with a mask
- WeChat payment development process
- [Interview high-frequency questions] Linked list high-frequency questions that can be gradually optimized
- 实验记录:搭建网络过程
- PM2之配置文件
- Shell正则表达式,三剑客之grep命令
- WeChat Mini Program Payment and Refund Overall Process
- C# 获取系统已安装的.NET版本
- ABP 6.0.0-rc.1的新特性
猜你喜欢
1-hour live broadcast recruitment order: industry big names share dry goods, and enterprise registration opens丨qubit·viewpoint
web course design
Shell之常用小工具(sort、uniq、tr、cut)
基于CAP组件实现补偿事务与幂等性保障
JD.com architects tidy up: what are the core technical knowledge points of jvm and performance tuning
又有大厂员工连续加班倒下/ 百度搜狗取消快照/ 马斯克生父不为他骄傲...今日更多新鲜事在此...
内网穿透工具ngrok使用教程
Reading and writing after separation, performance were up 100%
京东架构师呕心整理:jvm与性能调优有哪些核心技术知识点
ABAP 面试题:如何使用 ABAP 编程语言的 System CALL 接口,直接执行 ABAP 服务器所在操作系统的 shell 命令?
随机推荐
学长告诉我,大厂MySQL都是通过SSH连接的
ThreadLocal的简单理解
专业人士使用的 11 种渗透测试工具
Recommend a free 50-hour AI computing platform
Byte Qiu Zhao confused me on both sides, and asked me under what circumstances would the SYN message be discarded?
8、IDEA提交代码出现: Fetch failed fatal: Could not read from remote repository
AI篮球裁判火了,走步算得特别准,就问哈登慌不慌
The FFmpeg library is configured and used on win10 (libx264 is not configured)
网页控制台控制编辑框
ACM01 Backpack problem
Django cannot link mysql database
1小时直播招募令:行业大咖干货分享,企业报名开启丨量子位·视点
研发需求的验收标准应该怎么写? | 敏捷实践
箭头函数和普通函数的常见区别
听声辨物,这是AI视觉该干的???|ECCV 2022
软件测试——金融测试类面试题,看完直接去面试了
国产抗新冠口服药每瓶不超300元/ 我国IPv6网络全面建成/ 谷歌入局折叠屏手机...今日更多新鲜事在此...
GET请求和POST请求区别
Adalvo收购其首个品牌产品Onsolis
LeetCode热题(11.合并两个有序链表)