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

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

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

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

sou.png
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);
    }

}
 32 68 -98 51 88 1
 -98 1 32 51 68 88

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

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);
            
        
    }
第3小的数为:32

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【编程基础】聊聊如何学习Java——Java的特性

上一篇文章聊了学习编程可能会遇到的心里障碍和为什么学习Java,看了网友们的回复小编很激动,我会积极听取网友们的留言,在我以后的文章中改进。现在说Java语言的...

40390
来自专栏landv

我的第一个Java程序和Java简介

13820
来自专栏Java学习网

Java虚拟机工作原理之JVM用到的3大计算机核心功能,重点是方法调用

JVM是Java Virtual Machine(Java虚拟机)的缩写,JVM是一种用于计算设备的规范,它是一个虚构出来的计算机,是通过在实际的计算机上仿真模...

21430
来自专栏窗户

shell编程/字库裁剪(3)——验证

  程序写完了,必须要验证,这是重要的方法论。因为如果不验证,则不会知道程序写的对还是不对。学过人工智能或者控制论都知道,反馈非常重要,反馈形成闭环,可以用来指...

224100
来自专栏AndroidTraveler

责任链模式妙用

除了应用场景比较多的单例模式你能够信手拈来,其他的可能会觉得有点难以掌握。也许压根都没用过。

13630
来自专栏iOS技术

何为代码质量?——用脑子写代码引言正文总结

为什么项目维护困难、BUG 反复?实际上很多时候就是代码质量的问题。代码架构就像是建筑的钢筋结构,代码细节就像是建筑的内部装修,建筑的抗震等级、简装或豪装完全取...

7620
来自专栏撸码那些事

【抽象那些事】不完整的抽象&多方面抽象&未用的抽象&重复的抽象

10520
来自专栏CSDN技术头条

应用广泛的语言ECMAScript 2018来了,新特性都在这里

ECMAScript的两项新特性已确定,另外四项正在考虑中。 ? 作为JavaScript的标准规范,ECMAScript有望在6月发布新的版本。 目前为止,已...

20860
来自专栏小勇DW3

通俗的理解java设计模式的准则

  原文链接:http://blog.csdn.net/lovelion/article/details/7536542

25730
来自专栏逍遥剑客的游戏开发

从Native到Web(三), NaCl学习笔记: 3D渲染(DX9迁移到GLES)

13920

扫码关注云+社区

领取腾讯云代金券