2018届各大互联网公司面经以及答案

### 知识点：外部排序算法 #### 1. 外部排序概念 外部排序是指由于数据量太大，无法完全加载到内存中，需要借助外部存储（如硬盘）来辅助完成排序的算法。常见的外部排序算法包括外部归并排序、外部堆排序等。 #### 2. 内部排序与外部排序的区别 - 内部排序：数据量小，可以一次性加载到内存中进行排序，例如快速排序、插入排序、选择排序等。 - 外部排序：数据量太大，无法一次性加载到内存，需要分批次处理，例如外部归并排序。 #### 3. 外部归并排序的基本思想 外部归并排序的核心思想是将大文件分割成若干个小文件，每个小文件的大小可以被内存所容纳。接着对每个小文件进行内部排序，之后再将排序好的小文件归并成更大的有序文件，逐步扩大归并的文件规模，最终得到一个全局有序的大文件。 #### 4. 外部归并排序的步骤 1. **预处理**：将大文件分割为若干个可以被内存容纳的小文件，并在读入内存后对每个小文件进行内部排序。 2. **两路归并**：将两个有序小文件合并为一个更大的有序文件。通过比较两个文件的首元素，将较小元素写入新文件，重复此步骤直到所有小文件合并完成。 3. **多路归并**：在两路归并的基础上，可以将多个有序文件合并为更大的有序文件，重复此过程直到最终得到完全有序的大文件。 #### 5. 快速排序的优化策略 - **三数取中法**：选择基准值时，不是简单选择第一个或最后一个元素，而是取数组中间位置的元素，或者取首、中、尾三个元素的中位数作为基准。 - **聚集重复元素**：在划分区间的操作中，将所有等于基准值的元素聚集到一起，以减少不必要的比较和移动。 - **插入排序优化**：对于小数组（元素量小于10-20），使用插入排序比快速排序更高效。 #### 6. 堆排序的应用 在处理多个有序序列时，可以利用堆这种数据结构维护多个序列的最小元素。通过构建小根堆来不断得到当前所有序列的最小值，并通过堆的调整来更新堆。 #### 7. 时间与空间复杂度 - **外部归并排序**：时间复杂度为O(nlogn)，空间复杂度取决于归并时外部存储的使用量。 - **快速排序的优化**：时间复杂度可接近O(nlogn)，但由于分治和递归，空间复杂度较高，可达O(logn)。 - **堆排序**：时间复杂度为O(nlogn)，空间复杂度为O(1)。 #### 8. 分支思想与归并思想 - **分支思想**：将大任务分解为多个小任务，分别解决，最后再进行合并。 - **归并思想**：将多个有序的子序列合并成一个完全有序的序列。 #### 9. 海量数据处理方法 在处理100G量级的数据时，需要采取的策略包括： 1. 利用磁盘分块处理技术，将数据分布到多个文件上。 2. 对每个分块进行快速排序，并在排序过程中进行优化。 3. 使用多路归并策略逐步归并小块文件，直至形成完全有序的大文件。 #### 10. 优化策略 - **并行处理**：通过流水线并行的方式处理不同任务，可以极大提高排序效率。 - **小根堆的使用**：在处理有序文件组时，小根堆可以快速获取最小值，用于归并过程。 ### 总结 在面对海量数据排序时，内部排序算法由于内存限制无法直接应用。此时，采用外部排序算法，如外部归并排序，成为一种有效的解决方案。通过对大文件进行分块处理、优化内部排序算法，以及合理地利用外部存储设备，可以有效地完成大数据量的排序任务。此外，对于大数据处理，还需考虑算法的空间复杂度、时间复杂度以及如何优化算法效率等重要因素。以上便是对外部排序相关知识点的详细阐述。