赞
踩
对快排算法思想就不描述了,针对快排递归过程中边界的取值做了总结:
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]
----->
那按这样划分行不行呢:[l,i][i+1,r]---->
既然不能用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); } }
最容易想到的就是直接进行快排,然后输出快排后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); } }
还有一种更高效的方法,就是快速选择算法,针对快排过程中的递归排序区间进行选择,而不是全部都排序。
思想如下:
基准数x会将待排序数字划分为两个区间,左区间都是小于x 的数,右区间都是大于x的数。
要寻找第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); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。