一道经典的面试题：如何从N个数中选出最大（小）的n个数？

网上有关“一道经典的面试题：如何从N个数中选出最大（小）的n个数？”话题很是火热，小编也是针对一道经典的面试题：如何从N个数中选出最大（小）的n个数？寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。

这个问题我前前后后考虑了有快一年了，也和不少人讨论过。据我得到的消息，Google和微软都面过这道题。这道题可能很多人都听说过，或者知道答案（所谓的堆），不过我想把我的答案写出来。我的分析也许存有漏洞，以交流为目的。但这是一个满复杂的问题，蛮有趣的。看完本文，也许会启发你一些没有想过的解决方案（我一直认为堆也许不是最高效的算法）。在本文中，将会一直以寻找n个最大的数为分析例子，以便统一。注：本文写得会比较细节一些，以便于绝大多数人都能看懂，别嫌我罗嗦:) 我很不确定多少人有耐心看完本文！Naive 方法：首先，我们假设n和N都是内存可容纳的，也就是说N个数可以一次load到内存里存放在数组里（如果非要存在链表估计又是另一个challenging的问题了）。从最简单的情况开始，如果n=1，那么没有任何疑惑，必须要进行N-1次的比较才能得到最大的那个数，直接遍历N个数就可以了。如果n=2呢？当然，可以直接遍历2遍N数组，第一遍得到最大数max1，但是在遍历第二遍求第二大数max2的时候，每次都要判断从N所取的元素的下标不等于max1的下标，这样会大大增加比较次数。对此有一个解决办法，可以以max1为分割点将N数组分成前后两部分，然后分别遍历这两部分得到两个最大数，然后二者取一得到max2。也可以遍历一遍就解决此问题，首先维护两个元素max1，max2（max1=max2），取到N中的一个数以后，先和max1比，如果比max1大（则肯定比max2大），直接替换max1，否则再和max2比较确定是否替换max2。采用类似的方法，对于n=2，3，4一样可以处理。这样的算法时间复杂度为O（nN）。当n越来越大的时候（不可能超过N/2，否则可以变成是找N-n个最小的数的对偶问题），这个算法的效率会越来越差。但是在n比较小的时候（具体多小不好说），这个算法由于简单，不存在递归调用等系统损耗，实际效率应该很不错.堆：当n较大的时候采用什么算法呢？首先我们分析上面的算法，当从N中取出一个新的数m的时候，它需要依次和max1，max2，max3max n比较，一直找到一个比m小的max x，就用m来替换max x，平均比较次数是n/2。可不可以用更少的比较次数来实现替换呢？最直观的方法是，也就是网上文章比较推崇的堆。堆有这么一些好处：1.它是一个完全二叉树，树的深度是相同节点的二叉树中最少的，维护效率较高；2.它可以通过数组来实现，而且父节点p与左右子节l，r点的数组下标的关系是s[l] = 2*s[p]+1和s[r] = 2*s[p]+2。在计算机中2*s[p]这样的运算可以用一个左移1位操作来实现，十分高效。再加上数组可以随机存取，效率也很高。3.堆的Extract操作，也就是将堆顶拿走并重新维护堆的时间复杂度是O（logn），这里n是堆的大小。具体到我们的问题，如何具体实现呢？首先开辟一个大小为n的数组区A，从N中读入n个数填入到A中，然后将A维护成一个小顶堆（即堆顶A[0]中存放的是A中最小的数）。然后从N中取出下一个数，即第n+1个数m，将m与堆顶A[0]比较，如果m<=A[0]，直接丢弃m。否则应该用m替换A[0]。但此时A的堆特性可能已被破坏，应该重新维护堆：从A[0]开始，将A[0]与左右子节点分别比较（特别注意，这里需要比较两次才能确定最大数，在后面我会根据这个来和败者树比较），如果A[0]比左右子节点都小，则堆特性能够保证，勿需继续，否则如左（右）节点最大，则将A[0]与左（右）节点交换，并继续维护左（右）子树。依次执行，直到遍历完N，堆中保留的n个数就是N中最大的n个数。这都是堆排序的基本知识，唯一的trick就是维护一个小顶堆，而不是大顶堆。不明白的稍微想一下。维护一次堆的时间复杂度为O（logn），总体的复杂度是O（Nlogn）这样一来，比起上面的O（nN），当n足够大时，堆的效率肯定是要高一些的。当然，直接对N数组建堆，然后提取n次堆顶就能得到结果，而且其复杂度是O（nlogN）,当n不是特别小的时候这样会快很多。但是对于online数据就没办法了，比如N不能一次load进内存，甚至是一个流，根本不知道N是多少。败者树：有没有别的算法呢？我先来说一说败者树（loser tree）。也许有些人对loser tree不是很了解，其实它是一个比较经典的外部排序方法，也就是有x个已经排序好的文件，将其归并为一个有序序列。败者树的思想咋一看有些绕，其实是为了减小比较次数。首先简单介绍一下败者树：败者树的叶子节点是数据节点，然后两两分组（如果节点总数不是2的幂，可以用类似完全树的结构构成树），内部节点用来记录左右子树的优胜者中的败者（注意记录的是输的那一方），而优胜者则往上传递继续比较，一直到根节点。如果我们的优胜者是两个数中较小的数，则根节点记录的是最后一次比较中的败者，也就是所有叶子节点中第二小的那个数，而最小的那个数记录在一个独立的变量中。这里要注意，内部节点不但要记录败者的数值，还要记录对应的叶子节点。如果是用链表构成的树，则内部节点需要有指针指向叶子节点。这里可以有一个trick，就是内部节点只记录败者对应的叶子节点，具体的数值可以在需要的时候间接访问（这一方法在用数组来实现败者树时十分有用，后面我会讲到）。关键的来了，当把最小值输出后，最小值所对应的叶子节点需要变成一个新的数（或者改为无穷大，在文件归并的时候表示文件已读完）。接下来维护败者树，从更新的叶子节点网上，依次与内部节点比较，将败者更新，胜者往上继续比较。由于更新节点占用的是之前的最小值的叶子节点，它往上一直到根节点的路径与之前的最小值的路径是完全相同的。内部节点记录的败者虽然称为败者，但却是其所在子树中最小的数。也就是说，只要与败者比较得到的胜者，就是该子树中最小的那个数（这里讲得有点绕了，看不明白的还是找本书看吧，对照着图比较容易理解）。注：也可以直接对N构建败者树，但是败者树用数组实现时不能像堆一样进行增量维护，当叶子节点的个数变动时需要完全重新构建整棵树。为了方便比较堆和败者树的性能，后面的分析都是对n个数构建的堆和败者树来分析的。总而言之，败者树在进行维护的时候，比较次数是logn+1。与堆不同的是，败者树是从下往上维护，每上一层，只需要和败者节点比较一次即可。而堆在维护的时候是从上往下，每下一层，需要和左右子节点都比较，需要比较两次。从这个角度，败者树比堆更优一些。但是，请注意但是，败者树每一次维护必定需要从叶子节点一直走到根节点，不可能中间停止；而堆维护时，有可能会在中间的某个层停止，不需要继续往下。这样一来，虽然每一层败者树需要的比较次数比堆少一倍，但是走的层数堆会比败者树少。具体少多少，从平均意义上到底哪一个的效率会更好一些？那我就不知道了，这个分析起来有点麻烦。感兴趣的人可以尝试一下，讨论讨论。但是至少说明了，也许堆并非是最优的。具体到我们的问题。类似的方法，先构建一棵有n个叶子节点的败者树，胜出者w是n个中最小的那一个。从N中读入一个新的数m后，和w比较，如果比w小，直接丢弃，否则用m替换w所在的叶子节点的值，然后维护该败者树。依次执行，直到遍历完N，败者树中保留的n个数就是N中最大的n个数。时间复杂度也是O（Nlogn）类快速排序方法：快速排序大家大家都不陌生了。主要思想是找一个轴节点，将数列交换变成两部分，一部分全都小于等于轴，另一部分全都大于等于轴，然后对两部分递归处理。其平均时间复杂度是O（NlogN）。从中可以受到启发，如果我们选择的轴使得交换完的较大那一部分的数的个数j正好是n，不也就完成了在N个数中寻找n个最大的数的任务吗？当然，轴也许不能选得这么恰好。可以这么分析，如果jn，则最大的n个数肯定在这j个数中，则问题变成在这j个数中找出n个最大的数；否则如果j<n，则这j个数肯定是n个最大的数的一部分，而剩下的j-n个数在小于等于轴的那一部分中，同样可递归处理。需要注意的是，这里的时间复杂度是平均意义上的，在最坏情况下，每次分割都分割成1：N-2，这种情况下的时间复杂度为O（n）。但是我们还有杀手锏，可以有一个在最坏情况下时间复杂度为O（N）的算法，这个算法是在分割数列的时候保证会按照比较均匀的比例分割，at least 3n/10-6。具体细节我就不再说了，感兴趣的人参考算法导论（Introduction to Algorithms 第二版第九章 Medians and Orders Statistics）。还是那个结论，堆不见得会是最优的。本文快要结束了，但是还有一个问题：如果N非常大，存放在磁盘上，不能一次装载进内存呢？怎么办？对于介绍的Naive方法，堆，败者树等等，依然适用，需要注意的就是每次从磁盘上尽量多读一些数到内存区，然后处理完之后再读入一批。减少IO次数，自然能够提高效率。而对于类快速排序方法，稍微要麻烦一些：分批读入，假设是M个数，然后从这M个数中选出n个最大的数缓存起来，直到所有的N个数都分批处理完之后，再将各批次缓存的n个数合并起来再进行一次类快速排序得到最终的n个最大的数就可以了。在运行过程中，如果缓存数太多，可以不断地将多个缓存合并，保留这些缓存中最大的n个数即可。由于类快速排序的时间复杂度是O（N），这样分批处理再合并的办法，依然有极大的可能会比堆和败者树更优。当然，在空间上会占用较多的内存。总结：对于这个问题，我想了很多，但是觉得还有一些地方可以继续深挖：1. 堆和败者树到底哪一个更优？可以通过理论分析，也可以通过实验来比较。也许会有人觉得这个很无聊；2. 有没有近似的算法或者概率算法来解决这个问题？我对这方面实在不熟悉，如果有人有想法的话可以一块交流。如果有分析错误或遗漏的地方，请告知，我不怕丢人，呵呵！最后请时刻谨记，时间复杂度不等于实际的运行时间，一个常数因子很大的O（logN）算法也许会比常数因子小的O（N）算法慢很多。所以说，n和N的具体值，以及编程实现的质量，都会影响到实际效率。

几种常见的排序（冒泡、选择、插入、希尔、堆排序）

数据表中有10000个元素,如果仅要求求出其中最大的10个元素,则采用堆排序最节省时间。

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点；在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。

扩展资料：

堆排序的基本思想是将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

百度百科-快速排序算法

内排序:是在排序整个过程中,待排序的所有记录全部被放置在内存中;

外排序:由于排序的记录个数太多,不不能同时放置在内存,整个排序过程需要在内外存 之间多次交换数据才能进?

1、顺序表结构

2、数据交换函数

3、数据打印

冒泡排序(Bubble Sort) 一种交换排序,它的基本思想就是: 两两?比较相邻的记录的关键字,如果 反序则交换,直到没有反序的记录为?.

也可以反过来，每次都把最大的值放到末尾。

简单排序算法(Simple Selection Sort) 就是通过n-i次关键词比较,从n-i+1个记录中找出关键 字最小的记录,并和第i(1<=i<=n) 个记录进行交换.

总结一句话就是(划重点)：从第一个位置开始比较，找出最小的，和第一个位置互换，开始下一轮。

（1）冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；

（2）冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；

（3）冒泡排序是通过数去找位置，选择排序是给定位置去找数；

冒泡排序优缺点：优点:比较简单，空间复杂度较低，是稳定的；

缺点:时间复杂度太高，效率慢；

选择排序优缺点：优点：一轮比较只需要换一次位置；

缺点：效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。

直接插入排序算法(Stright Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表 中,从而得到一个新的,记录数增1的有序表;

步骤1、将数据插入到有序表中与前一个比较，如果大于则不改变位置

2、如果插入数据小于前一个数据，则前面大的数据依次往后移动，然后找到合适位置插入该数据。

空间复杂度: O(1) 解读:在直接插?入排序中只使?用了了i,j,temp这三个辅助元素，与问题规模?无关，空间复杂度为O(1)

时间复杂度: O(n2)

希尔排序思想: 希尔排序是把记录按下标的一定增量分组，对每组使用直接插?排序算法排 序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减?1时，整个序列恰被分成 一组，算法便终止.

其实就是分治法升级版的插入排序，又称为缩小增量排序。我们不断减半增量，直到增量为1时，退化为普通插入排序。

希尔排序通过增量进行了分组(分治)，比较的是L->r[j-increment]和L->[j]，跨度是increment，如果摸到的是较小的牌，只需要移动1次，而插入排序需要移动increment次。

也就是说希尔排序的优势是，能让较小的牌更容易来到数组的前面部分，节约了移动次数。

需要注意的是：

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。

或者

每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

如下图1为大顶堆：

下图为小顶堆：

我们用简单的公式来描述一下堆的定义就是：

大顶堆： arr[i] >= arr[2i] && arr[i] >= arr[2i+1]

小顶堆： arr[i] <= arr[2i] && arr[i] <= arr[2i+1]

1、用待排序序列构造一个大顶堆。

2、将其与末尾元素进行交换，此时末尾就为最大值。

3、然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。

4、如此反复执行，便能得到一个有序序列了。

我们可以发现其实堆排序还是一种选择排序，用一句话概括思想：

利用堆结构特性，不断选出最大值，放到最后。

归并排序(Merging Sort) 就是利利?用归并的思想实现排序?方法. 它的原理理是假设初始序 列列含有n个记录,则可以看成n个有序的?子序列列. 每个?子序列列的?长度为1,然后两两合并.得 到[n/2]个?长度为2或1的有序?子序列列, 再两两归并. ......如此重复,直到得到?一个?长度为n 的有序序列列为此. 这种排序?方法称为2路路归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。

将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起。

进行合并时，我们需要一个额外的数组来进行辅助排序，再回填回原数组。

//6归并排序

首先设定一个分界值，通过该分界值将数组分成左右两部分。

将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。

此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

关于“一道经典的面试题：如何从N个数中选出最大（小）的n个数？”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！