前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >快速排序与寻找第k小的数算法

快速排序与寻找第k小的数算法

作者头像
热心的社会主义接班人
发布2018-04-27 14:46:57
6040
发布2018-04-27 14:46:57
举报
文章被收录于专栏:cs

慕课网 首发了,放在垂直领域吧。简书备份。

出现了一点小问题,就是index,要注意。想法网上一大堆,不多说了。

ubuntu18下输入法有问题,sogou没有安装上,打字好累啊。

sou.png
sou.png
代码语言:javascript
复制
package day20180425;

public class SortDem {

    public static void main(String[] args) {
        
         int[] arr={32,68,-98,51,88,1};
         display(arr);
        System.out.println();
        quicksort(arr,0,arr.length-1);
        display(arr);

    }
    
    static int keyfid(int[] arr,int left ,int right)
    {
        int i=left,j=right,temp;
         int p=arr[left];
     /*
      * 是i<j,当二个相遇的时候就要交换   
      * 还可以变成 while(i!=j) 
      */
        while(i<j)
        {
        // 当大于等与关键字就要交换 
           while(i<j&&p<=arr[j])
               j--;
           while(i<j&&p>=arr[i])
               i++;
           if(i<j)
            {
               temp=arr[i];
               arr[i]=arr[j];
               arr[j]=temp;
             }
        }
        
        arr[left]=arr[i];
        arr[i]=p;
        return i;
    }
    
    
    static void quicksort(int[] arr, int left,int right)
    {
        int key;
        if(left>right)
        return;
        else
        {
           key=keyfid(arr,left,right);
           quicksort(arr,left,key-1);
           quicksort(arr,key+1,right);
            
        }
        
    }
    
    
    static void display(int[] arr)
    {
        for(int value:arr)
        System.out.print(" "+value);
    }

}
代码语言:javascript
复制
 32 68 -98 51 88 1
 -98 1 32 51 68 88

寻找一个数组中第k小的数,比如 [32 68 -98 51 88 1]中,选择第3小的数,就是32,一种想法是把数字排序,在去下标,但是可以利用快排。其实只要取得轴值就可以了。

代码语言:javascript
复制
static int sort(int[] arr,int k,int left,int right)
    {
        int index;
        index=keyfid(arr,left,right);
        if(k-1==index)
            return arr[index];
        else if(index>k)
        {
            return sort(arr,k,left,index-1);
        }
        else
            return sort(arr,k,index+1,right);
            
        
    }
代码语言:javascript
复制
第3小的数为:32
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.04.25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档