最小的k个数

左手的ㄟ右手 2022-08-20 11:27 171阅读 0赞

题目描述：查找最小的K个数  
题目：输入n个整数，输出其中最小的K个数  
例如，输入1、2、3、4、5、6、7、8这8个数字，则最小的4个数字为1、2、3、4。

解题思路：

首先：我们会想到先排序，这个想法最为直接，排完序之后自然可以找到最小的k个数，这是第一层思考；那么我们来分析一下常用的排序算法：  
冒泡排序  
选择排序(简单选择排序，堆排序)  
插入排序(直接插入排序，希尔排序)  
快速排序  
归并排序

在这些算法中，冒泡排序和选择排序每循环一次就找到了一个最小值，可以不用全部排序；快速排序可以每循环一次即选择一个中轴值，一部分比它小，一部分比它大；这些特性都是有利于在查找最小的k个值中能够用到的。具体分析如下：

*  当k=1时，简单选择排序和冒泡排序是最佳选择，它们均能通过一次遍历找到最小值，（堆排序存在一个建堆初始化的时间，这个时间在最坏情况下是O(4n)）。这两个比较下，冒泡排序在最坏情况下一次遍历比较的时间复杂度为O(n-1)，同时移动的时间复杂度为O(3(n-1))，而选择排序主要时间复杂度在比较上，同样为O(n-1) (排序的基本操作为比较和移动)；但冒泡排序有一个好处是能通过一次遍历，来确定序列是不是最好情况，适用于k>1时做第一次遍历。
 *  当a>k>1时,依然使用简单选择排序是理想选择。这个a的临界点即是上面说到堆排序建堆初始化的时间代价。此时简单选择排序的时间复杂度为(n-1)+(n-2)+…+(n-a)。
 *  当k>a时，堆排序就开始发挥他的优势（使用小顶堆）。堆排序的创建堆的时间复杂度为O(n),每次调整的时间复杂度为O(logn),调整k次的时间复杂度为O(n+klogn);堆排序除了时间复杂度以外，它的空间复杂度为O(1)，有利于节省空间；在k>a的范围内，若k>n/2,可以先使用快速排序的特性，能够快速找到一部分，降低搜索空间的同时降低k值。
 *  当k接近于n时，快排是最快的。
 *  最后，当n是属于海量数据级别的，以至于不能使用内排的情况。由于这时问题的复杂性主要取决于读盘，因此我们希望的是找出最小的k个数的代价是只读一遍磁盘。在这种情况下，k=1时，简单选择排序是可以的；当k>1时，需要使用堆排序，建立一个包括k个元素的大顶堆，每次读取一个与堆顶比较，大于堆顶就舍去，小于堆顶就把堆顶替换然后再调整成大顶堆.