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

【算法基础】(一)基础算法 --- 快速排序

✨个人主页:bit me
✨当前专栏:算法基础
🔥专栏简介:该专栏主要更新一些基础算法题,有参加蓝桥杯等算法题竞赛或者正在刷题的铁汁们可以关注一下,互相监督打卡学习 🌹 🌹 🌹

快 速 排 序

  • 💤一. 快速排序:(分治)
  • 💦二.第k个数

 

💤一. 快速排序:(分治)

题目要求:

给定你一个长度为n的整数数列
请你使用快速排序对这个数列按照从小到大进行排序
并将排好的数列按顺序输出

输入格式:

输入一共两行,第一行包含整数n
第二行包含n个整数(所有整数均在1 ~ 10^9范围内),表示整个数列

输出格式:

输出共一行,包含n个整数,表示排好序的数列

数据范围:

1 <= n <= 100000

输入样例:

5
3 1 2 4 5

输出样例:

1 2 3 4 5

快排思路:

  1. 先确定分界点:左右极点分别为q[i],q[j],中间值为q[(i+j) / 2]
  2. 调整区间:定义一个任意值x,让小于x的值都挪到x左边,让大于x的值都挪到x右边
  3. 递归处理左右两段,让他们进行排序然后衔接,方法就是左右极限都定义一个指针,左指针往右走,遇到大于x的值就停下来,右指针往左走,遇到小于x的值就停下来,然后俩指针指向的值进行交换,直到相遇为止,这样左边就全是小于x的值,右边全是大于x的值,然后完成衔接,排序就完成了

导图:
在这里插入图片描述

  1. 首先我们需要输入第一行包含整数n,第二行包含n个整数:
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] q = new int[n];
for(int i=0; i<n; i++){
	q[i] = sc.nextInt();
}
  1. 对快速排序函数进行分类处理:

①:当左边界大于等于右边界的时候直接返回

if(l >= r) return;

②:取随机值x我们最好取左右边界的中间值,因为取左右边界值可能会超时,时间复杂度退化,当我们左右指针往中间挪的时候我们不要把起点定在左右边界处,要放在边界外面一位,方便我们处理边界,不容易发生混淆

int x = q[l + r >> 1], i = l - 1, j = r + 1;

③:当左指针没遇到右指针的时候,我们需要考虑到随机值x,当左指针小于x的时候就往右边走,当右指针大于x的时候就往左边走,如果左指针和右指针都停了的时候,就交换两边的数据,然后继续往后走

while(i < j){
    while( q[++i] < x );
    while( q[--j] > x) ;
    if(i < j){
        int t = q[i];
        q[i] = q[j];
        q[j] = t;
    }
}

④:对边界的处理

quickSort(q, l, j);
quickSort(q, j + 1, r);

在这里对边界进行一个小结:

quickSort(q, l, j);
quickSort(q, j + 1, r);

quickSort(q, l, i - 1);
quickSort(q, i, r);

  1. 是因为对于第一次处理后的数组,索引i左侧的数字都是小于等于x,但不包括q[i]。索引i右侧的数字都是大于等于x,包括q[i]。故区间分为[l,i-1]和[i,r]。
  2. 同理,对于第一次处理后的数组,索引j左侧的数字都是小于等于x,包括q[j]。索引j右侧的数字都是大于等于x,不包括q[j]。故区间分为[l,j]和[j+1,r]。

再对x位置小结:

  1. 如果区间取[l,i-1]和[i,r]这种,那么x不应该取左边界(l、(l+r)/2)。
    应取 x = q[r]; x = q[(l+r+1)/2];
  2. 如果区间取[l,j]和[j+1,r]这种,那么x不应该取右边界(如r、(l+r+1)/2)。
    应取 x = q[l]; x = q[(l+r)/2];
     
    自己选择其中一种即可。

附上总的代码

public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] q = new int[n];
    for(int i=0; i<n; i++){q[i] = sc.nextInt();}

    quickSort(q, 0, n-1);
    for(int i=0; i<n; i++){System.out.print(q[i] + " ");}
}

public static void quickSort(int[] q, int l, int r){
    if(l >= r) return;
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j){
        while( q[++i] < x );
        while( q[--j] > x) ;
        if(i < j){
            int t = q[i];
            q[i] = q[j];
            q[j] = t;
        }
    }
    quickSort(q, l, j);
    quickSort(q, j + 1, r);
}

 

💦二.第k个数

题目要求:

给定一个长度为 n 的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式:

第一行包含两个整数 n 和 k。
第二行包含 n 个整数(所有整数均在 1∼109 范围内),表示整数数列。

输出格式:

输出一个整数,表示数列的第 k 小数。

数据范围:

1≤n≤100000 ,
1≤k≤n

输入样例:

5 3
2 4 1 5 3

输出样例:

3

根据我们上述的快排思路,我们还可以再多分一步就可以

  1. 先确定分界点:左右极点,中间值
  2. 左边所有数<= x,右边所有数>= x
  3. 当我们找的k小于等于x的时候,就递归左边所有的数Left,反之,当k大于x的时候,就递归右边的所有的数Right
  1. 首先我们需要创建两个整数 n 和 k,创建数组arr来输入
Scanner s  =  new Scanner(System.in);
int n = s.nextInt();
int k = s.nextInt();
int[] arr = new int[n];
for(int i = 0;i < arr.length;i++){
    arr[i] = s.nextInt();
}
  1. 接下来我们需要按照快排函数来实现它,和上面一题思路一样代码也一样,模板照抄

①:分情况处理

if(left >= right) return left;
int x = arr[(left + right) / 2],i = left - 1,j = right + 1;
while(i < j){
    while(arr[++i] < x);
    while(arr[--j] > x);
    if(i < j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

②:边界问题

int sl = j - left + 1;
if(k <= sl) return quickSort(arr,left,j,k);
else return quickSort(arr,j+1,right,(k-sl));

在这里sl代表小于x的区域,它的范围个数是 j - left + 1,当k值小于第一区域个数时,返回的就是第一个区域的个数数值,当它个数范围比第一区域大的时候,就在大于x的区域找,第二个区域的范围就是 j + 1到 right,然后返回值为k - sl

附上总的代码

public static void main(String[] args){
    Scanner s  =  new Scanner(System.in);
    int n = s.nextInt();
    int k = s.nextInt();
    int[] arr = new int[n];
    for(int i = 0;i < arr.length;i++){
        arr[i] = s.nextInt();
	}
    int result = quickSort(arr,0,n-1,k);
    System.out.print(arr[result]);
}

public static int quickSort(int[] arr,int left,int right,int k){
    if(left >= right) return left;
    int x = arr[(left + right) / 2],i = left - 1,j = right + 1;
    while(i < j){
        while(arr[++i] < x);
        while(arr[--j] > x);
        if(i < j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int sl = j - left + 1;
    if(k <= sl) return quickSort(arr,left,j,k);
    else return quickSort(arr,j+1,right,(k-sl));
}

相关文章:

  • 蓝桥杯实战应用【算法代码篇】-基于数组实现线性表
  • 晶圆盒RF载具ID读取器CK-S650-PA60E的1协议和N协议通信说明
  • Grails SpringBoot国际化不生效
  • JNDI注入的理解、JDK给出的修复
  • WPF项目实战布局--通用固件下载 C#
  • java EE初阶 — 计算机工作原理
  • 零时科技 || 分布式资本创始人4200万美金资产被盗分析及追踪工作
  • [附源码]java毕业设计医院预约挂号管理系统
  • 上游模式用于实验室用冷冻机压力和真空度的高精度控制
  • LinkedIn领英开发客户方法大全(篇一)
  • Spring中的ApplicationContext所体现出来的工厂模式
  • Navicat使用教程
  • 数据库 Apache Doris 展开了为期两个月的调研测试
  • 链接杂谈 CASPP
  • 面试:SurfaceView 和 TextureView
  • Scala、Spark的安装及配置
  • 【前端内容学习】vue的引用,下载,语法
  • Sentinel流控规则
  • mysql8.0以上修改密码-干货版
  • 图的拓扑序列
  • Spark中宽依赖、窄依赖、Job执行流程
  • R语言最优聚类数目k改进kmean聚类算法
  • 【torch.utils.data.sampler】采样器的解析和使用
  • Request和Response基础知识入门
  • 实战Docker未授权访问提权
  • 【微信小程序】页面跳转、组件自定义、获取页面参数值
  • 间接式常压热水锅炉_58mw燃气热水锅炉安装预算
  • 天然气锅炉烧水的原理_天然气锅炉总是停
  • 导热油锅炉厂家_燃油气蒸汽锅炉