首页 > 代码库 > 查找最小的k个元素
查找最小的k个元素
转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4250795.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：输入n个整数，输出其中最小的k个。
题目分析：
在找出前k个最小(或最大)的元素时，如果元素个数较少，可以采用简单选择排序；如果元素较多，可以采用堆排序；如果元素基本有序，可以采用冒泡排序。本文采用的是堆排序。
堆排序基本思想：
首先将带排序的记录序列构造成一个堆(此处要找出最小的前k个值，因此构建小根堆)，此时，选出对中的所有记录的最小者即堆顶记录，将它从堆中移走(通常是和最后一个记录交换)，并将剩余的记录重新调整成堆，这样就找出了次小的记录，以此类推，直到对中只有一个记录为止。 开始比较的节点为待排序的堆的最后一个非终端节点。
源码：
1 package com.interview; 2 3 /** 4 * 题目：输入n个整数，输出其中最小的k个。 5 * 本实现采用堆排序 6 * @author wjh 7 * 8 */ 9 10 public class _5TheKSmallestData {11 12 /**13 * @param args14 */15 public static void main(String[] args) {16 int[] b = {98,15,12,8,8,4,43,11,15,9,64,2,76,35,11,3,1};17 int k = 5;18 System.out.println("最小的前"+k+"个元素为：");19 sort(b,k);20 }21 22 //在数组b中查找前k个最小的数据23 public static void sort(int[] b, int k) {24 if(b.length<k){25 System.out.println("请输入一个<="+b.length+"的返回个数！");26 return;27 }28 int n=b.length;29 //移除堆顶，将最后一个元素推入堆顶30 for(int i=0;i<k;i++){ 31 int k1 = (n-i)/2-1;32 for(int j=k1;j>=0;j--){ //建堆33 smallHeap(b, j, n-i-1); 34 }35 System.out.print(b[0]+" ");36 int temp = b[0]; //此处是将堆顶与待排序的最后一个元素交换37 b[0] = b[n-i-1];38 b[n-i-1] = temp;39 }40 }41 42 //建小根堆 ，从最后一个非终端节点至顶点 (b[], 开始比较的节点下标,最后一个待比较的元素的下标)43 private static void smallHeap(int[] b, int k, int end){44 int i=k, j=2*i+1;//i为要筛选的节点的下标,从0开始,j为 i的左孩子45 while(j<=end){ //当还没有比较到叶子节点46 if(j<end && b[j]>b[j+1]){ //j保存i的左右孩子中较大的孩子的下标47 j++;48 }49 if(b[i]<b[j]){ //如果i比左右孩子都小，则结束本轮比较50 break;51 }52 else{ // i节点与j节点交换,53 int temp = b[i];54 b[i] = b[j];55 b[j] = temp;56 i = j;57 j=2*i+1;58 }59 }60 } 61 }
运行结果：
最小的前5个元素为：
1 2 3 4 8
查找最小的k个元素
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。