当前位置:   article > 正文

力扣刷题记录---快排算法_力扣快速排序

力扣快速排序

AcWing 785. 快速排序

在这里插入图片描述
快排算法思想就不描述了,针对快排递归过程中边界的取值做了总结:

x为每次递归中,选取的基准数(枢轴)

如果x = q[i]或者x = q[l + r >> 1],此时只能用sort(l,j),sort(j + 1, r)
如果x = q[r]或者x = q[l + r + 1 >> 1],此时只能用sort(l, i - 1),sort(i, r)

记忆:
如果选取的基准元素偏左,则用 j划分区间;sort(l,j),sort(j + 1, r);
如果选取的基准元素偏右,则用 i划分区间;sort(l, i - 1),sort(i, r);

因为如果选取的基准元素偏左,再用i进行划分,
会导致下一次递归快排的时候,出现递归和这次一样的区间,造成死循环

如1,2时,选最左作为基准:x=q[0]=1; l=0,r=1;此次快排区间是[0,1]

第一趟快排结束时,i=j=0---->最开始时l索引也是0;
如果按照i来划分区间[l,i-1][i,r]----->

  • 左区间[0,-1] (不符合l<r,下一层直接返回)
  • 右区间[0,1] (重复进入和这次一样的区间,死循环)

那按这样划分行不行呢:[l,i][i+1,r]---->

  • 左区间[0,1] (重复划分一样的区间,死循环)
  • 右区间[2,1] (不符合,进入下一层直接返回)

既然不能用i划分,用j划分的话,能不能[l,j-1][j,r],这样去划分呢?

这也是不行的,因为这样的话[j,r]这个右边的区间也会变成[0,1],和本次递归初始区间[0,1]相同,进入死循环
所以只能用j这样划分:[l,j][j+1,r]

举例:
情况1:int i = l - 1, j = r + 1, x = q[l + r >> 1];//选取基准偏左
情况2:int i = l - 1, j = r + 1, x = q[l];//选取基准偏左
情况3:int i = l - 1, j = r + 1, x = q[r];//选取基准偏右
情况4:int i = l - 1, j = r + 1, x = q[l + r + 1 >> 1];//选取基准偏右

对应后续划分:
情况1: quick_sort(q, l, j), quick_sort(q, j + 1, r);//偏左时用j划分
情况2: quick_sort(q, l, j), quick_sort(q, j + 1, r);//偏左时用j划分
情况3: quick_sort(q, l, i - 1), quick_sort(q, i, r);//偏右时用i划分
情况4: quick_sort(q, l, i - 1), quick_sort(q, i, r);//偏右时用i划分

代码如下:

import java.util.*;
public class Main{
    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++){
            if(i==n-1)System.out.println(q[i]);
            else System.out.print(q[i]+" ");
        }
    }
    public static void quickSort(int[] q,int l,int r){
        
        if(l>=r)return;
        int x=q[l],i=l-1,j=r+1;
        
        while(i<j){
            
            while(q[++i]<x);//先+1,再判断,相当于do i++;while(q[i]<x);
            while(q[--j]>x);
            // 对于i来说,i左边的值是确定的,一定小于x,q[i]此时的值大于或等于x。
            // 对于j来说,j右边的值是确定的,一定大于x,q[j]此时的值小于或等于x。
            if(i<j){
                int temp=q[i];
                q[i]=q[j];
                q[j]=temp;
            }
        }
        quickSort(q,l,j);
        quickSort(q,j+1,r);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

AcWing 786. 第k个数

在这里插入图片描述

最容易想到的就是直接进行快排,然后输出快排后q数组的d第k个数字,这样的时间复杂度就是O(nlogn)。直接套用上一题的模板,增添一些代码即可。

代码如下:

//快排,时间:O(nlogn)
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[] q=new int[n];
        for (int i = 0; i < n; i++) {
            q[i]= sc.nextInt();
        }
        quickSort(q,0,n-1);
        System.out.println(q[k-1]);

    }
    public static void quickSort(int[] q, int l, int r){
        if(l>=r)return;
        int x=q[l],i=l-1,j=r+1;
        while (i<j){
            while(q[++i]<x);
            while(q[--j]>x);
            if(i<j){
                int temp=q[i];
                q[i]=q[j];
                q[j]=temp;
            }
        }
        quickSort(q,l,j);
        quickSort(q,j+1,r);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

还有一种更高效的方法,就是快速选择算法,针对快排过程中的递归排序区间进行选择,而不是全部都排序。

思想如下:

基准数x会将待排序数字划分为两个区间,左区间都是小于x 的数,右区间都是大于x的数。

要寻找第k小的数,可以设左区间有sl个数:

  • 当k<=sl的时候,说明要找的数就在左区间内,下一层递归只要对左区间进行快排算法即可,而不用对右区间进行排序;
  • 当k>sl的时候,要找的的数在右区间内,左区间的数一定都小于要寻找的第k个数,不用递归排序,只要排序右区间,但是这时候就不是在右区间找第k小的数,而是在右区间找第k-sl小的数了。

代码如下:

/*
快速选择(在快排基础上优化),时间:O(n)

因为除了第一次递归需要O(n)之外,后面的每次递归只需要递归左区间或者右区间
也就是O(n)+O(1/2*n)+O(1/4*n)+……<=n+n=2n
*/
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[] q=new int[n];
        for (int i = 0; i < n; i++) {
            q[i]= sc.nextInt();
        }
        
        System.out.println(quickSort(q,0,n-1,k));

    }
    
    //这里需要注意,这题里的快排有返回值,最终直接就返回第k个数,所以主函数直接打印即可
    public static int quickSort(int[] q, int l, int r,int k){
        //因为每次递归都保证k在[l,r]之间
        //当边界重合为一个点的时候,那个点一定是要找的第k个数
        if(l==r)return q[l];
        int x=q[l],i=l-1,j=r+1;
        while (i<j){
            while(q[++i]<x);
            while(q[--j]>x);
            if(i<j){
                int temp=q[i];
                q[i]=q[j];
                q[j]=temp;
            }
        }
        //因为左区间[l,j],右区间[j+1.r]
        int sl=j-l+1;//左区间有sl个数
        //k没超过左区间长度,说明第k小的数就在左区间
        //直接递归左区间快排,不用管右区间,还是找左区间第k个数
        if(k<=sl)return quickSort(q,l,j,k);
        //否则k大于左区间长度,说明第k个数在右区间里,就要去右区间了
        //此时就不是找右区间的第k个数了,而是右区间第k-sl个数
        return quickSort(q,j+1,r,k-sl);
    }
    
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/735798
推荐阅读
相关标签
  

闽ICP备14008679号