- 正确答案：归并排序是一种基于分治思想的稳定排序算法，其核心是将一个数组不断二分，直到每个子数组只有一个元素，然后将这些子数组两两合并，合并过程中保持有序，最终得到一个完整的有序数组。时间复杂度为 O(n log n)，空间复杂度为 O(n)。 - 解答思路： 1. 分解：将当前数组从中间分成左右两个子数组，递归地对左右子数组进行归并排序。 2. 合并：当子数组长度为1时，开始回溯并合并两个已排序的子数组。使用一个临时数组来存放合并后的结果，合并完成后将临时数组的内容复制回原数组。 3. 关键点在于合并过程：需要两个指针分别指向左右子数组的起始位置，比较元素大小，将较小的元素放入临时数组，并移动对应指针，直到所有元素都被处理。 - 深度知识讲解：归并排序的核心是“分而治之”（Divide and Conquer）策略。它将问题分解为更小的相同子问题，解决后再合并结果。时间复杂度分析： - 分解阶段：每次将数组一分为二，共需 log n 层。 - 合并阶段：每一层的所有合并操作总共需要 O(n) 时间。 - 因此总时间复杂度为 O(n log n)，且最好、最坏、平均情况都一致。空间复杂度： - 需要一个与原数组等长的辅助数组用于合并，因此空间复杂度为 O(n)。 - 递归调用栈深度为 O(log n)，但由于辅助空间占主导，整体空间复杂度仍为 O(n)。稳定性： - 归并排序是稳定的，因为在合并时若左右元素相等，优先取左边的元素，保持了原有相对顺序。底层数据结构： - 使用数组作为主要存储结构，利用索引进行分段操作。 - 合并过程依赖临时数组避免覆盖原数据。与其他排序对比： - 相比快排，归并排序性能更稳定，但需要额外空间。 - 适合链表排序（此时空间复杂度可优化至 O(1)），也常用于外部排序（如大文件排序）。 - 代码示例（C++风格实现，手撕级别）： ``` #include using namespace std; // 合并两个有序子数组 void merge(int arr[], int temp[], int left, int mid, int right) { int i = left; // 左子数组起始 int j = mid + 1; // 右子数组起始 int k = left; // 临时数组起始 // 将较小的元素放入临时数组 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // 复制剩余左半部分 while (i <= mid) { temp[k++] = arr[i++]; } // 复制剩余右半部分 while (j <= right) { temp[k++] = arr[j++]; } // 将临时数组内容复制回原数组 for (int idx = left; idx <= right; idx++) { arr[idx] = temp[idx]; } } // 归并排序主函数 void mergeSort(int arr[], int temp[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2; // 防止整数溢出 mergeSort(arr, temp, left, mid); mergeSort(arr, temp, mid + 1, right); merge(arr, temp, left, mid, right); } } // 包装函数 void mergeSort(int arr[], int n) { int* temp = new int[n]; // 动态分配临时数组 mergeSort(arr, temp, 0, n - 1); delete[] temp; // 释放内存 } // 测试函数 int main() { int arr[] = {38, 27, 43, 3, 9, 82, 10}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Original array: "; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; mergeSort(arr, n); cout << "Sorted array: "; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; return 0; } ``` - 扩展知识点： 1. 自底向上的归并排序（非递归版本）： - 不使用递归，而是从子数组长度为1开始，逐步合并成长度为2、4、8……的有序段。 - 可避免递归带来的函数调用开销，适用于栈空间受限环境。 2. 链表的归并排序： - 链表中无法高效随机访问，但归并排序仅需顺序访问，非常适合链表。 - 空间复杂度可降至 O(1)（通过修改指针而非复制节点）。 3. 多路归并： - 在外部排序中，将数据分成多个块分别排序后写入磁盘，再进行k路归并（使用堆优化选择最小元素）。 4. 逆序对计数： - 归并排序可在合并过程中统计逆序对数量：当右子数组元素被选中时，左子数组剩余元素个数即为该元素引起的逆序对数。归并排序不仅是面试高频题，更是理解分治、递归、稳定性、复杂度分析的经典范例，建议熟练掌握其原理与实现细节。

26校招途虎养车前端二面45min

全站热榜

创作者周榜