数据量很大的排序问题大量数据如何排序

淡淡的烟草味﹌ 2023-10-17 15:36 83阅读 0赞

## 数据量很大的排序问题 大量数据如何排序 ##

【[尊重][Link 1] [原创，转载请注明出处][Link 1] 】http://blog.csdn.net/guyuealian/article/details/51151674

同学某天参加腾讯面试，技术面的时候，面试官问了排序问题：

**问题一**：若有1T的数据，需要实现由大到小排序，你用什么办法，说说你的思路和想法？

**问题二**：有10个G的数据，如果两条数据一样，则表示该两条数据重复了，现在给你512的内存，把这10G中重复次数最高的10条数据取出来。

**分析：**问题一和问题二思路基本是一样的，对于这种题目，利用常规的排序方法（如插入排序，快速排序……），自然是不能解决问题的！因此数据量太大。注意内部排序和外部排序的区别

**排序算法分为内部排序和外部排序：  
（1）内部排序：**指的是待排序记录存放在计算机随机存储器（内存）中进行的排序过程；我们熟悉常用的冒泡排序，选择排序，插入排序，快速排序，堆排序，归并排序，希尔排序……等都属于内部排序方法；

**内部排序算法的比较：**

![Center][]

![Center 1][]

**（2）外部排序：**指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序过程；

**基本思路：**外部排序指的是大文件的排序，即待排序的记录存储在外部存储器上，在排序过程中需进行多次的内、外存之间的交换。首先将打文件记录分成若干个子文件，然后读入内存中，并利用**内部排序**的方法进行排序；然后把排序好的有序子文件（称为：归并段）重新写入外存，再对这些归并段进行逐个归并，直到整个有序文件为止。  
例子：假设有10 000个记录的文件需要排序，则先把这10 000个记录文件分成10个归并段（R1…~R10，每段1000个记录），然后逐个读入归并段进行内部排序（共10次），然后把排序好的归并段重新写入外存中，再进行两两归并，直到得到一个有序文件为止。

![Center 2][]

**先来看看各位大神对问题解答：http://bbs.csdn.net/topics/390360278?page=1**

**思路一：**

**\[plain\]** [view plain][] [copy][view plain]

1.  【1】先排序， 10G数据分成40份，每份256M，排序，合并相同数据并加上计数器，写到临时文件chunk01~chunk20。 
2.  【2】对每一chunk, 读入内存，对每一条数据，再依次读入其后续个chunk, 合并相同数据的计数，后写入一个文件count。为了避免重复计数，在计数累加后需要将原来chunk的计数清零并回写文件。 
3.   以chunk01为例。假设chunk01中有数据A-8(数据A, 8次)，chunk02中有A-2，那么合并chunk02后 
4.   chunk01的内存中为A-10， chunk02中为A-0，这时把chunk02写回文件，然后读入chunk03继续处理处理。最后把chunk01中计数不为0的数据(chunk01里不会有计数为0的，但是后面的chunk会有)写入文件count. 
5.  【3】对count文件进行按重复次数排序。（分组，排序，然后每组选前10，再排序）

**思路二：**

**\[plain\]** [view plain][] [copy][view plain]

1.   对于问题二，个人觉得，分组统计，最后合并的方法是不可取的，因为有可能某个值A，在你每个分组中出现的次数都没有排进前10，但是将它在每个分组中的次数加起来，是能排进前10的。所以应该还是计数排序。 
2.   其次是这10G数据时什么，是10G个BYTE，还是10G个字符串。因为BYTE的范围0-255，也就是说这个问题就变成了，找0-255范围内，出现次数最多的10个数，用int64\[255\]来计数，遍历一次，每个数值对应下标里面记录其出现的次数就可以了，用int64是因为DWORD表示不了10G。如果是字符串，或者是其他2进制数据块，就比较复杂，需要多次遍历。2进制数据块有多少个字节，就需要准备多少个int64\[255\]计数数组 
3.   假定每条记录，就是每个2进制数据块长10个字节，对于不足10字节的记录，不足的部分以0计算需要的计数数组为int64\[10\]\[255\]，对于每条记录的第一个字节相同的，算为相同记录的情况下，得出表： 
4.  A\*\*\*\*\*\*\*\*\* 1000次 
5.  B\*\*\*\*\*\*\*\*\* 900次 
6.  C\*\*\*\*\*\*\*\*\* 900次 
7.  D\*\*\*\*\*\*\*\*\* 890次 
8.  ...统计结果计入int64\[0\]\[255\] 
9.  然后对于100次的A\*\*\*\*\*\*\*\*\*，统计 
10. AE\*\*\*\*\*\*\*\* 50次 
11. AA\*\*\*\*\*\*\*\* 50次 
12. AD\*\*\*\*\*\*\*\* 49次 
13. AC\*\*\*\*\*\*\*\* 47次 
14. ...统计结果计入int64\[1\]\[255\] 
15. 依此类推 
16. AEDBBCADE\* 10次 
17. AEDBBCADB\* 9次 
18. AEDBBCADC\* 9次 
19. AEDBBCADA\* 8次 
20. ...统计结果计入int64\[8\]\[255\] 
21. 最终 
22. AEDBBCADEA 3次 
23. AEDBBCADEF 3次 
24. AEDBBCADEC 2次 
25. AEDBBCADEB 2次 
26. ...统计结果计入int64\[9\]\[255\] 
27. 将这个结果放入另一个int64\[255\] res，这个就是当前的最终结果 
28. 然后逐个向前递归 
29. 对于int64\[8\]\[255\]中排行第二的“AEDBBCADB\* 9次” 
30. 统计出前10，得到一个新的int64\[9\]\[255\]，将其与res中的结果比较，得出这20个中的前10，更新res

依此类推，得出最终结果

来源:http://blog.csdn.net/guyuealian/article/details/51151674

[Link 1]: http://blog.csdn.net/guyuealian/article/details/51151674
[Center]: https://img-blog.csdn.net/20160414152305892?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20160414152314934?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: https://img-blog.csdn.net/20160414152458362?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[view plain]: http://blog.csdn.net/guyuealian/article/details/51151674#