java快速排序法的常见问题
一道java面试题，20亿数字的文本排序，如何取前100？
一道java面试题，20亿数字的文本排序，如何取前100？
每行一个数字
自己写个最小（大）堆不就完了，c 也可以用标准库里的优先队列。先找出前100大，然后再对前100大进行排序就是结果。。。。这题目简直不要太简单。。。。常见扩展就是1亿个url，如何找出出现最次数前100多的url。
有点笨的方法.:将20亿的数字分成2000（2万）个数据一段（或文件），对每组数组取1个（也可10个），直接汇总既可。也可多取再二次分组或三次分组。更多次就约准确。
我作为一个外行看来，这样的方案应该可以吧:假如要找出的是排大到小的前100.那么随机抓取20亿个中的100个，然后将这100个数排序，然后将剩下的数字中逐个跟100个中的最小的比较，如果比100个中最小的小，就淘汰这个，换下一个，如果那个数比100个中的最小的大，则将这个数置换掉那个最小的，100个再排序，(这次排序就很快了)，接着再从剩余的数字中抓一个来比较，直至20亿个全部比较完，剩下的100个就是最大的前100
我赞成两个靠谱的回答
1
取100个数字排序，后面的数字依次和100个数字最小的比，最后留下100个最大的
2
根据字符串长度、小数、负数几个属性分类，可以直接排除部分较短的数字不转化为数字，然后做排序。这应该能省一些转换数字的时间吧？
Java一些经典算法自己想不出来怎么办？
比如，斐波那契，冒泡，一直都看别人写。
算法前期还是需要多看、多练，锻炼强的逻辑思维能力，前期把每个算法摸透，比如冒泡，可能你第一次看完了，好像懂了，但是动手去写，发现毫无逻辑，无从下手，根本还是没有理解算法的核心；它是怎么冒泡的？有什么规则？这些应该是当一提到冒泡你就应该能够想到的。提到冒泡就应该想到排序，那何为排序呢？
如果实在不懂，就挨条代码理解，不懂的多问。加油！
通常Java开发人员如何进行数据排序？
选择排序
思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：①初始状态：无序区为R[1..n]，有序区为空。②第1趟排序在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。……③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
排序实例初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [76 97 65 49 ]
第五趟排序后 13 27 38 49 49 [97 65 76]
第六趟排序后 13 27 38 49 49 65 [97 76]
第七趟排序后 13 27 38 49 49 65 76 [97]
最后排序结果 13 27 38 49 49 65 76 97
Java实现代码如下：
结果验证正确。
冒泡法
原理
冒泡排序算法的运作如下：比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。算法分析算法稳定性冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
Java实现代码：
?
插入排序
插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
算法描述一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：从第一个元素开始，该元素可以认为已经被排序取出下一个元素，在已经排序的元素序列中从后向前扫描如果该元素（已排序）大于新元素，将该元素移到下一位置重复步骤3，直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
Java示例代码如下：
希尔排序
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i step_size而不是i ）。
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，
这样他们就应该看起来是这样：
然后我们对每列进行排序：将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：排序之后变为：最后以1步长进行排序（此时就是简单的插入排序了）。
在实际使用过程中，带排序的数据肯定不是只有十个，但是上述的思想。其实排序只是插入排序的一种优化。
快速排序 思想：从待排序记录序列中选取一个记录(通常选取第一个记录)为枢轴其关键字设为k1，然后将其余关键字小于k1的记录移到前面去，而将关键字大于k1的记录移到后面，结果将待排序序列分成了两个子表最后将关键字为k1的记录查到其分界线的位置处.算法步骤：假设待划分序列为r[left],r[left 1],.......r[right],具体实现上述划分过程时，可以设两个指针i和j，他们的初值分别为left,right.首先将基准记录r[left]移至变量x中，是r[left]，即r[i]相当于空单元，然后反复进行如下两个扫描过程，直到i和j相遇（1）j从右向左扫描，直到r[j].key （2）i从左向后扫描，直到r[i]时，将r[i]移至空单元r[j],此时r[i]相当于空单元。当i和j相遇时，r[i](或r[j])相当与空单元，且r[i]左边所有记录的关键字均不大于基准记录的关键字，而r[i]右边所有记录的关键字均不小于基准记录的关键字，最后将基准记录移至r[i]中，就完成了一次划分过程。最后对子表进行递归调用排序函数进行排序。Java示例代码如下：
归并排序归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并操作归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。如 设有数列{6，202，100，301，38，8，1}初始状态：6,202,100,301,38,8，1第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；第三次归并后：{1,6,8,38,100,202,301},比较次数：4；总的比较次数为：3 4 411,；逆序数为14；算法描述归并操作的工作原理如下：第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾Java示例代码如下：