当前位置: 首页 > news >正文

快速排序算法备考

image.png

image.png

快排模板

快速排序(快排) (C语言实现)_c语言快速排序_Brant_zero2022的博客-CSDN博客
快排使用递归来实现
关键思想:划分


//划分
int partion(int A[],int L,int R){int mid=A[L];while(L<R){//每一次划分:左边元素<枢轴元素<右边元素//R往前找,直到找到一个比mid小的元素,然后把A[R]放在A[L]的位置while(A[R]>=mid && L<R){R--;}A[L]=A[R];while(A[R]<=mid && L<R){L++;}A[R]=A[L];}//存放枢轴元素A[L]=mid;return L;
}//快排
void quickSort(int A[],int L,int R){if(L>=R) return;//递归终止int M=partion(A,L,R);//返回中轴元素的下标//对中轴元素两边分别排序quickSort(A,L,M-1);quickSort(A,M+1,R);}

快排的划分思想

image.png

快排划分思想的算法题

使用划分函数找到数组中第k小的元素

  • 数组中第k小的元素,说明这个元素的左边有k-1个元素比它小,利用快排的划分思想,我们只需要让划分函数返回k-1,就可以找到第k小元素。
  • 如果第一次划分后,返回下标为k-1,那么,我们就找到了这个元素
  • 如果返回的下标>k-1,说明接下来要在[L,M-1]进行划分
  • 如果返回的下标<k-1,说明接下来要在右边进行划分

int partion(int A[],int L,int R){int mid=A[L];while(L<R){	while(A[R]>=mid && L<R) R--;A[L]=A[R];while(A[L]<=mid && L<R) L++A[R]=A[L];}A[L]=mid;}
//非递归实现
int min_k(int A[],int n,int k){int L=0,R=n-1;int M=0;while(1){M=partion(A,L,R);if(M==k-1)  break;//说明找到了else if(M<k-1){//在右边进行划分L=M+1;}else{//在左边进行划分R=M-1;}}return A[K-1]}//递归实现
int min_k(int A[],int L,int R){int M=partion(A,L,R);if(M==k-1)  return A[M];//说明找到了else if(M<k-1){//在右边进行划分min_k(A,M+1,R);}else{min_k(A,L,M-1);}}

分析非递归的复杂度
image.png
image.png

王道课后习题:在数组中找到第k小的元素

image.png
第k小,说明左边有k-1个元素比它小,利用快排的划分思想,只要返回下标为k即可

利用划分思想
//返回划分后的中轴元素的下标
int partion(int L,int left,int right){int mid=L[left];while(left<right){while(L[right]>=mid && left<right) right--;L[left]=L[right];while(L[left]<=mid && left<=right) left++;L[right]=L[left];}L[left]=mid;return left;}int min_k(int L[],int n,int k){int left=1,right=n,M=0;while(1){M=partion(L,left,right);if(M==k) break;else if(M<k)  left=M+1;//要在右边进行划分else right=M-1;//左边划分}return L[k];}

快排算法题实战应用

2011年42题

image.png

方法一双指针(我自己第一遍就想到的思路)

  1. 使用双指针,i指向序列S1元素,j指向S2序列元素,cnt用来记录已经比较的次数。比较s1,s2所指元素大小,如果S1所指元素大,则j向后移动,然后cnt++,如果S2所指元素大,则i向后移动,cnt++,当cnt==L/2时,此时,s1,s2所指元素大的那个就是中位数
  2. 代码

int find(int s1[],int s2[],int n){int i=j=cnt=0;for(cnt=0;cnt<n/2;cnt++;){if(s1[i]<s2[j]){i++;}else{j++; } }//接下来比较s1,s2所指元素大小if(s1[i]>s2[j]){return s1[i];}else{return s2[j];}}

时间复杂度:o(n)
空间复杂度:o(1)

方法二利用快排解决问题

把两个数组合并成一个大数组,然后用快排,下标L/2的元素就是中位数
image.png


//快排划分
int partion(int a[].int L,int R){int mid=a[L];while(L<R){while(a[R]>=mid&& L<R) R--;a[L]=a[R];while(a[L]>=mid && L<R) L++;a[R]=a[L];a[L]=mid;return L;}
//快排void qSort(int a[],int L,int R){if(L<=R) return;int M=partion(a,L,R);qSort(a,L,M-1);qSort(a,M+1,R);}void find(int s1[],int s2[],int n){int a[2*n];int i,j=0;//合并成一个数组for( i=0;i<n;i++)c[j++]=s1[i];}for( i=n;i<2*n;j++){c[j++]=s2[i];}//排序qSort(a,0,2*n-1);return (0+2*n-1)/2;}

2013年41题

方法一利用哈希表(第一遍所想)

1.cnt数组记录元素大小0~n-1出现的次数,出现次数大于n/2的元素就是主元素
2.代码void mainElement(int a[],int n){int cnt[n]={0};//元素值为i就存放在cnt数组的下标为i的位置,并且cnt对应位置元素值+1for(int i=0;i<n;i++){cnt[a[i]]++;}//扫描cnt数组for(int i=0;i<n;i++){if(cnt[i]>n/2) court<<i<<endl;}court<<"不存在主元素"<<endl;}
3.时间复杂度:o(n)空间复杂度o(n)

方法二快排

主元素的元素数量超过数组长度的一半,如果数组有序,并且存在主元素,那么主元素一定在数组的中间位置
image.png

①无序--->有序  快排
②找n/2位置的元素
③从n/2往左、往右统计个数,然后判断存不存在

image.png

2018年41题

image.png
54

方法一哈希表

cnt数组用来记录元素i是否出现在数组中,cnt记录1n,如果元素i位于1n,则对应cnt数组相应位置+1


int fun(int a[],int n){int cnt[n+1];for(int i=0;i<n;i++){if(a[i]>=1 && a[i]<=n) {cnt[a[i]]++;}}//遍历cnt数组,如果cnt[i]==0,说明就是未出现的最小正整数for(int i=1;i<n;i++){if(cnt[i]==0) return i;}//说明1~n都存在return n+1;}时间复杂度  O(n)空间复杂度  O(n)

image.png

方法二快排

image.png

2016年43题(本质是把乱序数组排成有序)

image.png

方法一利用快排

思路:想办法让右边元素大,左边元素小,而且尽量要把数组尽量平分,想到快排的划分思想,为了满足上述条件,右半部分的元素不能比左边元素个数少。
左边:0~n/2-1
右边:n/2~n-1

  1. 把数组A排成递增有序数列,排序后集合A1为[0,n/2-1],集合A2为[n/2n-1]

    此时[S1-S2]最大,[n1-n2]最小
    2.代码

①无序数组拍成有序数组
②说明A1,A2所在区间范围//划分
int partion(int A[],int L,int R){int mid=A[L];while(L<R){//每一次划分:左边元素<枢轴元素<右边元素//R往前找,直到找到一个比mid小的元素,然后把A[R]放在A[L]的位置while(A[R]>=mid && L<R){R--;}A[L]=A[R];while(A[R]<=mid && L<R){L++;}A[R]=A[L];}//存放枢轴元素A[L]=mid;return L;
}//快排
void quickSort(int A[],int L,int R){if(L>=R) return;//递归终止int M=partion(A,0,n-1);//返回中轴元素的下标//对中轴元素两边分别排序quickSort(A,L,M-1);quickSort(A,M+1,R);}
  1. 时间复杂度

    空间复杂度

image.png

方法二利用划分的思想(最优解)

我们知道快排在进行一次划分后,该元素的左边元素都比它小,右边都比它大。我们这道题目本质是把元素大的放右边,元素小的放左边,并没有要求按照 递增进行排序。其实,我们只要找到数组中第n/2小的元素。只要这个元素的位置确定了,那么它左边元素都比它小,右边都比它大。

//划分
int partion(int A[],int L,int R){int mid=A[L];while(L<R){//每一次划分:左边元素<枢轴元素<右边元素//R往前找,直到找到一个比mid小的元素,然后把A[R]放在A[L]的位置while(A[R]>=mid && L<R){R--;}A[L]=A[R];while(A[R]<=mid && L<R){L++;}A[R]=A[L];}//存放枢轴元素A[L]=mid;return L;
}
//
void fun(int A[],int n){int M=0;int k=n/2;int L=0,R=n-1;while(1){M=partion(A,L,R);if(M==k-1) break;else if(M<k-1) L=M+1;else R=M-1}//跳出循环说明已经找到第n/2小的元素}

image.png

相关文章:

  • [个人笔记] 记录CentOS7构建docker-ce的过程
  • 数据持久化第六课-ASP.NET运行机制
  • 云上聚智——移动云云服务器进行后端的搭建及部署
  • 整理好了!2024年最常见 20 道 Redis面试题(九)
  • keepalived交叉编译
  • yarn dev启动项目时遇到的问题
  • 【实战JVM】-基础篇-02-类的声明周期-加载器
  • 春秋CVE-2022-23906
  • ❤职场小心得❤
  • 上交提出TrustGAIN,提出6G网络中可信AIGC新模式!
  • php质量工具系列之paslm
  • 工博科技联手伯尼纳,共谋食品包装外贸行业新市场,助力全球市场拓展!
  • 质量源于设计:QbD培训引领企业产品质量飞跃!
  • 数据库编程
  • 周报 | 24.5.20-24.5.26文章汇总
  • 30天自制操作系统-2
  • Apache Spark Streaming 使用实例
  • CSS 提示工具(Tooltip)
  • C语言笔记(第一章:C语言编程)
  • happypack两次报错的问题
  • Python进阶细节
  • Python连接Oracle
  • scrapy学习之路4(itemloder的使用)
  • SpringBoot 实战 (三) | 配置文件详解
  • vue+element后台管理系统,从后端获取路由表,并正常渲染
  • 解决jsp引用其他项目时出现的 cannot be resolved to a type错误
  • 聊一聊前端的监控
  • 前言-如何学习区块链
  • 区块链技术特点之去中心化特性
  • 如何学习JavaEE,项目又该如何做?
  • 深入 Nginx 之配置篇
  • 协程
  • 不要一棍子打翻所有黑盒模型,其实可以让它们发挥作用 ...
  • 仓管云——企业云erp功能有哪些?
  • 湖北分布式智能数据采集方法有哪些?
  • 数据可视化之下发图实践
  • #define 用法
  • #QT(TCP网络编程-服务端)
  • (¥1011)-(一千零一拾一元整)输出
  • (C++20) consteval立即函数
  • (cljs/run-at (JSVM. :browser) 搭建刚好可用的开发环境!)
  • (JSP)EL——优化登录界面,获取对象,获取数据
  • (NO.00004)iOS实现打砖块游戏(十二):伸缩自如,我是如意金箍棒(上)!
  • (Redis使用系列) Springboot 实现Redis 同数据源动态切换db 八
  • (三)Honghu Cloud云架构一定时调度平台
  • (十八)SpringBoot之发送QQ邮件
  • (数据结构)顺序表的定义
  • (详细版)Vary: Scaling up the Vision Vocabulary for Large Vision-Language Models
  • (一)使用Mybatis实现在student数据库中插入一个学生信息
  • .net framwork4.6操作MySQL报错Character set ‘utf8mb3‘ is not supported 解决方法
  • .NET LINQ 通常分 Syntax Query 和Syntax Method
  • .Net MVC4 上传大文件,并保存表单
  • .NET MVC之AOP
  • .net 重复调用webservice_Java RMI 远程调用详解,优劣势说明
  • .net解析传过来的xml_DOM4J解析XML文件