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<