C++ 排序算法面试题

1. 常见排序算法的时间复杂度是多少？

答案：

2. 快速排序的原理和实现？

答案：

原理分治算法选择基准元素（pivot）将小于pivot的放左边，大于的放右边递归处理左右两部分
实现

int partition(vector<int>& arr, int low, int high) {    int pivot = arr[high];    int i = low - 1;    for (int j = low; j < high; j++) {        if (arr[j] < pivot) {            i++;            swap(arr[i], arr[j]);        }    }    swap(arr[i + 1], arr[high]);    return i + 1;}void quickSort(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);    }}

优化三数取中选择pivot小数组使用插入排序尾递归优化
特点不稳定排序原地排序实际应用中最快

3. 归并排序的原理和实现？

答案：

原理分治算法将数组分成两半递归排序两半合并两个有序数组
实现

void merge(vector<int>& arr, int l, int m, int r) {    vector<int> left(arr.begin() + l, arr.begin() + m + 1);    vector<int> right(arr.begin() + m + 1, arr.begin() + r + 1);        int i = 0, j = 0, k = l;    while (i < left.size() && j < right.size()) {        if (left[i] <= right[j]) {            arr[k++] = left[i++];        } else {            arr[k++] = right[j++];        }    }    while (i < left.size()) arr[k++] = left[i++];    while (j < right.size()) arr[k++] = right[j++];}void mergeSort(vector<int>& arr, int l, int r) {    if (l < r) {        int m = l + (r - l) / 2;        mergeSort(arr, l, m);        mergeSort(arr, m + 1, r);        merge(arr, l, m, r);    }}

特点稳定排序需要额外空间O(n)适合链表排序

4. 堆排序的原理和实现？

答案：

原理建立大顶堆将堆顶（最大值）与末尾交换调整堆，重复上述步骤
实现

void heapify(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) {        swap(arr[i], arr[largest]);        heapify(arr, n, largest);    }}void heapSort(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--) {        swap(arr[0], arr[i]);        heapify(arr, i, 0);    }}

特点不稳定排序原地排序时间复杂度稳定O(n log n)

5. 冒泡排序和插入排序的区别？

答案：

冒泡排序相邻元素比较交换每轮将最大元素"冒泡"到末尾优化：如果一轮没有交换，说明已排序

void bubbleSort(vector<int>& arr) {    int n = arr.size();    for (int i = 0; i < n - 1; i++) {        bool swapped = false;        for (int j = 0; j < n - i - 1; j++) {            if (arr[j] > arr[j + 1]) {                swap(arr[j], arr[j + 1]);                swapped = true;            }        }        if (!swapped) break;    }}

插入排序将元素插入到已排序部分的正确位置类似整理扑克牌对于近乎有序的数组效率高

void insertionSort(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;    }}

对比插入排序通常比冒泡排序快都是稳定排序都适合小规模数据

6. 什么是计数排序？适用场景？

答案：

原理统计每个值出现的次数根据计数结果输出排序数组非比较排序
实现

void countingSort(vector<int>& arr) {    int maxVal = *max_element(arr.begin(), arr.end());    int minVal = *min_element(arr.begin(), arr.end());    int range = maxVal - minVal + 1;        vector<int> count(range, 0);    vector<int> output(arr.size());        for (int num : arr)        count[num - minVal]++;        for (int i = 1; i < range; i++)        count[i] += count[i - 1];        for (int i = arr.size() - 1; i >= 0; i--) {        output[count[arr[i] - minVal] - 1] = arr[i];        count[arr[i] - minVal]--;    }        arr = output;}

适用场景数据范围不大整数排序需要稳定排序
优缺点优点：线性时间O(n+k)缺点：需要额外空间，数据范围大时不适用

7. 如何选择合适的排序算法？

答案：

数据规模小（< 50）插入排序：简单高效
数据规模中等快速排序：平均最快归并排序：需要稳定性
数据规模大快速排序：通常最快堆排序：空间受限时
特殊情况近乎有序：插入排序数据范围小：计数排序需要稳定性：归并排序、计数排序链表：归并排序
STL的sort内省排序（快排+堆排+插入排序）综合性能最好

8. 什么是稳定排序？为什么重要？

答案：

定义相等元素的相对顺序不变例如：[(1,a), (2,b), (1,c)] 排序后 (1,a) 仍在 (1,c) 前面
稳定排序冒泡排序插入排序归并排序计数排序基数排序
不稳定排序选择排序快速排序堆排序
重要性多关键字排序保持原有顺序某些业务逻辑要求

9. 如何找到第K大的元素？

答案：

排序法完全排序，取第K个时间：O(n log n)
堆方法维护大小为K的小顶堆时间：O(n log k)空间：O(k)
快速选择（Quick Select）类似快速排序的partition只处理包含第K大元素的一侧平均时间：O(n)最坏时间：O(n²)

int quickSelect(vector<int>& arr, int left, int right, int k) {    if (left == right) return arr[left];        int pivotIndex = partition(arr, left, right);        if (k == pivotIndex)        return arr[k];    else if (k < pivotIndex)        return quickSelect(arr, left, pivotIndex - 1, k);    else        return quickSelect(arr, pivotIndex + 1, right, k);}