你好呀，我是灰小猿，一个超会写bug的程序猿！

欢迎大家关注我的专栏“每日蓝桥”，该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题，解析其中存在的算法思想、数据结构等内容，帮助大家学习到更多的知识和技术！

标题：快速排序

以下代码可以从数组a[]中找出第k小的元素

它使用了类似于快速排序中的分治算法，期望时间复杂度是O(N)的，

请仔细阅读分析源码，填写划线部分缺失的内容

   

    

     

      

     
     

      

       package 一八年省赛真题;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       import java.util.Random;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       public class Main {
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	public static int quickSelect(int a[],int l,int r,int k) {
      
     
    

     

      

     
     

      

       		Random rand = new Random();
      
     
    

     

      

     
     

      
		int p = rand.nextInt(r-l+1) + l;
      
     
    

     

      

     
     

      
		int x = a[p];
      
     
    

     

      

     
     

      
		int tmp = a[p]; a[p] = a[r]; a[r] = tmp;
      
     
    

     

      

     
     

      
		int i = l, j = r;
      
     
    

     

      

     
     

      
		while (i<j) {
      
     
    

     

      

     
     

      
			while (i<j&&
      
     
   
  

文章来源: blog.csdn.net，作者：灰小猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_44985880/article/details/115490500