一、排序算法概览

算法	最好时间	平均时间	最坏时间	空间	稳定性
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
希尔排序	O(n)	O(n^1.3)	O(n²)	O(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
基数排序	O(nk)	O(nk)	O(nk)	O(n + k)	稳定

二、详细算法解析

1. 冒泡排序

原理：通过重复遍历待排序列表，比较相邻元素并交换顺序错误的元素，直到没有需要交换的元素为止。

特点：

• 简单易实现
• 适合小规模数据
• 优化：如果某次遍历没有交换，则提前结束

C++实现：

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 优化：已排序
    }
}

2. 选择排序

原理：每次从未排序部分找到最小元素，放到已排序部分的末尾。

特点：

• 实现简单
• 交换次数少（n-1次）
• 不稳定

C++实现：

void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        std::swap(arr[i], arr[min_idx]);
    }
}

3. 插入排序

原理：将数组分为已排序和未排序两部分，每次将未排序部分的第一个元素插入到已排序部分的适当位置。

特点：

• 对于接近有序的数组效率高
• 稳定
• 适合小规模数据

C++实现：

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

4. 希尔排序

原理：希尔排序是插入排序的改进版，通过"缩小增量"的方式，先对相距一定距离的元素进行排序，逐步缩小增量，最终进行插入排序。

特点：

• 通过预排序使数组接近有序
• 时间复杂度介于O(n)和O(n²)之间
• 不稳定
• 增量序列的选择影响性能

C++实现：

void shellSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

5. 归并排序

原理：分治法，将数组分成两半，递归排序，然后合并两个有序数组。

特点：

• 时间复杂度稳定O(n log n)
• 稳定
• 需要额外O(n)空间

C++实现：

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;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

6. 快速排序

原理：分治法，选择一个基准元素，将数组分为两部分，一部分小于基准，一部分大于基准，递归排序。

特点：

• 平均时间复杂度O(n log n)
• 最坏情况O(n²)（当数组已有序或接近有序时）
• 不稳定
• 原地排序，空间复杂度O(log n)

C++实现：

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

7. 堆排序

原理：利用堆（完全二叉树）的性质进行排序，构建大顶堆，然后交换堆顶和堆尾，调整堆。

特点：

• 时间复杂度O(n log n)
• 原地排序，空间复杂度O(1)
• 不稳定
• 性能稳定，不依赖于数据初始状态

C++实现：

void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] > arr[largest])
        largest = left;
    
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    
    // 构建大顶堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // 排序
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

8. 基数排序

原理：按数字的每一位（个位、十位、百位等）进行排序，使用稳定的排序算法（如计数排序）。

特点：

• 时间复杂度O(nk)，k为最大数字的位数
• 稳定
• 适合整数排序

C++实现：

void countingSort(std::vector<int>& arr, int exp) {
    std::vector<int> output(arr.size());
    std::vector<int> count(10, 0);
    
    for (int i = 0; i < arr.size(); i++)
        count[(arr[i] / exp) % 10]++;
    
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    
    for (int i = 0; i < arr.size(); i++)
        arr[i] = output[i];
}

void radixSort(std::vector<int>& arr) {
    int max = *std::max_element(arr.begin(), arr.end());
    
    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSort(arr, exp);
}

三、算法选择策略

1. 根据数据规模选择

数据规模	推荐算法	原因
小规模（<100）	插入排序、冒泡排序	常数因子小，实现简单
中规模（100-10000）	希尔排序、快速排序	有较好的平均性能
大规模（>10000）	归并排序、堆排序、快速排序	时间复杂度O(n log n)，性能稳定

2. 根据数据特性选择

数据特性	推荐算法	原因
接近有序	插入排序、希尔排序	时间复杂度接近O(n)
无序	快速排序、归并排序	平均性能好
需要稳定	归并排序、插入排序、基数排序	稳定性要求高
内存受限	堆排序、快速排序	原地排序，空间复杂度低

3. 根据编程语言特性选择

• C++：标准库std::sort通常使用快速排序（或混合排序），对大多数场景都是最优选择
• Java：Arrays.sort()对基本类型使用双轴快速排序，对对象使用归并排序
• Python：sorted()使用Timsort（归并排序和插入排序的混合）

四、面试常见问题解析

1. 为什么C++标准库的std::sort通常比手写排序算法快？

答案：C++标准库的std::sort是经过高度优化的，通常使用混合排序算法（如IntroSort，结合快速排序、堆排序和插入排序）：

1. 使用快速排序，平均时间复杂度O(n log n)
2. 当递归深度过大时，切换到堆排序，避免快速排序最坏情况O(n²)
3. 当子数组较小时，切换到插入排序，利用插入排序在小规模数据上的性能优势
4. 这种混合策略使std::sort在各种数据条件下都能保持高性能。

2. 为什么快速排序在实际应用中比归并排序更受欢迎？

答案：快速排序在实际应用中更受欢迎，主要有以下原因：

1. 原地排序：空间复杂度O(log n)（递归栈），而归并排序需要O(n)额外空间
2. 常数因子小：在实际数据中，快速排序的常数因子比归并排序小
3. 缓存友好：快速排序的访问模式更符合缓存局部性
4. 优化空间大：可以通过选择好的基准元素（如三数取中）避免最坏情况

3. 为什么归并排序在链表排序中比快速排序更好？

答案：归并排序在链表排序中比快速排序更好，主要有两个原因：

1. 链表不支持随机访问：快速排序需要随机访问元素，而链表只能顺序访问，实现起来效率低
2. 归并排序的分割和合并操作：链表天然适合分割和合并，而快速排序的分区操作在链表中实现复杂

4. 希尔排序和插入排序有什么关系？

答案：希尔排序是插入排序的改进版本。希尔排序通过"缩小增量"的方式，先对相距一定距离的元素进行排序，逐步缩小增量，最终进行插入排序。这样做的目的是使数组在进行最终的插入排序前已经"基本有序"，从而大幅减少插入排序的移动次数。

五、总结

面试金句：在C++排序算法选择中，没有"最好"的算法，只有"最适合"当前场景的算法。对于大多数C++应用场景，标准库的std::sort是最佳选择，它结合了快速排序、堆排序和插入排序的优势，提供了最优的平均性能。在需要自己实现排序算法时，应根据数据规模、数据特性、内存限制等因素进行选择。

"排序算法是计算机科学的基石，但没有银弹。理解各种排序算法的原理、优缺点和适用场景，才能在实际项目中做出正确的技术决策，避免'排序算法选择不当导致性能下降10倍'的悲剧。"

通过掌握这些常见排序算法，你可以在C++面试中展示对算法基础的深刻理解，同时也能在实际项目中做出更合理的技术决策。