面试题：C++ 混合排序算法设计

Question

设计一个C++ 混合排序算法，结合插入排序和归并排序的优点。当数组规模较小时（例如小于16）使用插入排序，当数组规模较大时使用归并排序。请详细阐述设计思路并完成代码实现，同时分析该混合排序算法在不同规模数据下的性能优势。

Answer 1

设计思路

1. 确定规模阈值：设定一个数组规模的阈值，这里为16。当数组规模小于该阈值时，使用插入排序；大于等于该阈值时，使用归并排序。
2. 插入排序：插入排序是一种简单的排序算法，对于小规模数据效率较高。它将一个数据插入到已经排好序的数组中的适当位置。
3. 归并排序：归并排序是一种分治算法，对于大规模数据表现良好。它将数组不断分成两半，分别排序，然后再将两个有序的子数组合并成一个有序数组。
4. 结合方式：在排序函数中，根据数组规模判断使用哪种排序算法。如果规模小，调用插入排序；规模大，则递归调用归并排序。

代码实现

#include <iostream>
#include <vector>

// 插入排序函数
void insertionSort(std::vector<int>& arr, int left, int right) {
    for (int i = left + 1; i <= right; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

// 合并两个子数组
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            ++i;
        } else {
            arr[k] = R[j];
            ++j;
        }
        ++k;
    }

    while (i < n1) {
        arr[k] = L[i];
        ++i;
        ++k;
    }

    while (j < n2) {
        arr[k] = R[j];
        ++j;
        ++k;
    }
}

// 归并排序函数
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        if (right - left + 1 < 16) {
            insertionSort(arr, left, right);
        } else {
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
}

// 混合排序函数
void hybridSort(std::vector<int>& arr) {
    mergeSort(arr, 0, arr.size() - 1);
}

性能优势分析

1. 小规模数据：插入排序在小规模数据下性能较好，因为它不需要像归并排序那样进行复杂的分治和合并操作。插入排序的时间复杂度在最好情况下为O(n)，平均和最坏情况下为O(n^2)。对于小规模数据，其常数因子较小，所以实际运行效率高。
2. 大规模数据：归并排序在大规模数据下性能优异，其时间复杂度稳定为O(n log n)。通过将数组不断分割并合并，归并排序能有效处理大规模数据。而插入排序在大规模数据下时间复杂度为O(n^2)，性能会急剧下降。因此，结合两种排序算法，在不同规模数据下都能有较好的性能表现。