一天一算法（43）：最小k个数

题目

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路

超级简单的题目，就是考察排序算法而已

代码

为了熟悉堆排序，使用了堆排

using System.Collections.Generic; class Solution { public List<int> GetLeastNumbers_Solution(int[] input, int k) { // write code here List<int> list=new List<int>(); if(input.Length==0 || input.Length<k) { return list; } HeapSort(input); for(int i=0;i<k && i<input.Length;i++) { list.Add(input[i]); } return list; } public void HeapSort(int []a) { int length=a.Length,lastIndex=length/2-1,nowIndex=lastIndex,index; int k; while(lastIndex>=0) { while(nowIndex>=0) { ChangeValue(a,length,nowIndex); index=nowIndex+1; while(index<=lastIndex) { ChangeValue(a,length,index); index++; } nowIndex--; } k=a[length-1]; a[length-1]=a[0]; a[0]=k; length--; lastIndex=length/2-1; nowIndex=0; } } public void ChangeValue(int[]a,int length,int index) { int i=index*2+1,max=a[index],x=index; for(int j=0;j<2 && i<length;j++) { if(a[i]>max) { max=a[i]; x=i; } i++; } a[x]=a[index]; a[index]=max; } }