算法八股文：说一说快速排序和堆排序（C++）

发布于：2025-07-24 ⋅ 阅读:(23) ⋅ 点赞:(0)

算法八股文：说一说快速排序和堆排序

快速排序

​ 快速排序的基本思路其实不难，总体而言，思路就是分而治之，递归求解

从序列中选出一个“基准值（pivot）”，将数组划分为两部分，使得：

  • 左边所有元素 ≤ pivot；
  • 右边所有元素 ≥ pivot；

然后对这两部分分别递归排序。

​ 所以，现在我们实际上分出来了三个步骤：

  • Partition：对pivot左右两侧的数进行排序，
  • 由Partition步骤返回最终的Index，作为新的pivot
  • 再递归的对左右进行排序

Partition这个步骤

​ Partition就是简单的选定一个pivot，然后将比这个数小的左侧放到pivot的左边，比这个数大的放到右边，我们初始将 pivot 放在最右侧，循环过程中暂不动它，等到分类完成后再归位（笔者习惯选在最左侧）这样就满足了我们的条件了

int partition(std::vector<int>& vec, int left, int right) {
	int prev_pivot_value = vec[right]; // 我们总是选择最右侧的游标来完成我们的工作
	int new_pivot = left; // 我们设置左边的就是新的游标

	for (int i = left; i < right; i++) {
		if (vec[i] < prev_pivot_value) {
			std::swap(vec[new_pivot], vec[i]); // 交换，因为站错位置了
			new_pivot++;
		}
	}
	std::swap(vec[new_pivot], vec[right]); // 交换一下，将pivot进行归位，这是我们的新pivot下表
	return new_pivot; // 吐出去，后面分治使用
}

​ 我们拿到了新游标之后，就是进行左右的递归排序：

void my_quick_sort(std::vector<int>& vec, int left, int right) {
	if (left >= right)
		return; // only one left, we dont need to sort
	int new_pivot = partition(vec, left, right);

	// sort left
	my_quick_sort(vec, left, new_pivot - 1);
	my_quick_sort(vec, new_pivot + 1, right);
}

​ 这样我们的快排就写好了。递归的触控条件就是：剩下一个的数组天然有序，直接退出去就好了。

改进我们的快速排序

1️⃣随机化基准值：防止在近似有序的情况下发生O(N^2退化)

​ 当输入数组是有序/近乎有序时，如果总是选择最左或最右作为 pivot，时间复杂度退化为 O(n²)。这个时候问题也很简单，咱们随便选一个就行了

  • 在 left ~ right 区间内随机选一个元素作为 pivot
  • 然后将其与 right 位置元素交换，照常执行
int random_partition(std::vector<int>& vec, int left, int right) {
    int rand_idx = left + rand() % (right - left + 1); // [left, right]
    std::swap(vec[rand_idx], vec[right]);
    return partition(vec, left, right); // 用我们之前那个 partition
}

2️⃣ 三数取中法（Median-of-Three）

  • 之前介绍的随机数可能仍不稳定（本质上只是利用了随机化争取最大可能的不失衡）
  • 三数取中法在许多实际场景下比随机法更好（特别是近乎有序的数据）

​ 实际上就是在左中右三个部分上取出来中间值

int median_of_three(std::vector<int>& vec, int left, int right) {
    int mid = left + (right - left) / 2;
    if (vec[left] > vec[mid]) std::swap(vec[left], vec[mid]);
    if (vec[left] > vec[right]) std::swap(vec[left], vec[right]);
    if (vec[mid] > vec[right]) std::swap(vec[mid], vec[right]);
    std::swap(vec[mid], vec[right]); // 把中位数放到 right 当 pivot
    return partition(vec, left, right);
}

3️⃣ 小数组改用插入排序（Hybrid Sort）

​ 快速排序在处理小规模子数组时（例如元素数 ≤ 16），递归带来的开销反而比插入排序慢。这个时候，我们就可以考虑对小规模数组改用堆排序或者是插入排序。

void insertion_sort(std::vector<int>& vec, int left, int right) {
    for (int i = left + 1; i <= right; ++i) {
        int key = vec[i];
        int j = i - 1;
        while (j >= left && vec[j] > key) {
            vec[j + 1] = vec[j];
            j--;
        }
        vec[j + 1] = key;
    }
}

void hybrid_quick_sort(std::vector<int>& vec, int left, int right) {
    const int threshold = 16;
    if (right - left <= threshold) {
        insertion_sort(vec, left, right);
        return;
    }

    int pivot_index = median_of_three(vec, left, right);
    hybrid_quick_sort(vec, left, pivot_index - 1);
    hybrid_quick_sort(vec, pivot_index + 1, right);
}

📌 实际的 std::sort() 就是这种：三数取中 + 插排 + 堆排 的混合版（IntroSort）

优化策略 目的 适用场景
随机化 pivot 避免最坏情况 O(n²) 数据近乎有序时
三数取中 更稳定选择 pivot 工业级快排标准配置
小数组用插排 常数开销小 子数组元素 ≤ 16

堆排序

什么是堆？

​ 堆（Heap）实际上是一个特殊的完全二叉树（除了最后一层之外，所有的节点都有两个子节点，且最后一层的节点都尽可能地靠左排列。）

​ 而且，他会满足下面性质中的其中一个：

  • 大顶堆（或最大堆）：每个父节点的值都大于或等于其子节点的值。也就是说，最大的元素永远在树的顶端（根节点）。
  • 小顶堆（或最小堆）：每个父节点的值都小于或等于其子节点的值。也就是说，最小的元素永远在树的顶端。

堆排序的思路是什么？

堆排序的思路非常简单，主要分为两步：

  1. 构建大顶堆：把待排序的数组变成一个大顶堆。这样一来，数组中最大的元素就跑到数组的第一个位置了。
  2. 排序：
    • 把数组的第一个元素（最大的）和最后一个元素交换位置。这样，最大的元素就被放到数组的末尾了。
    • 此时，数组的最后一个元素已经排好序了，我们不再理会它，只对剩下的 n−1 个元素重新调整，让它们再次成为一个大顶堆。
    • 重复这个过程，直到所有的元素都排好序。

简单来说，堆排序就是不断地把最大的元素“捞”出来，放到数组的末尾，然后对剩下的元素重复这个过程。

堆排序的例子

假设我们有一个数组 [4, 1, 3, 2]，我们想用堆排序把它从小到大排序。

第一步：构建大顶堆

我们将数组 [4, 1, 3, 2] 转化为大顶堆，从最后一个非叶子节点开始，依次向上调整。

  • 初始状态：数组可以看成一棵树，根节点是 4。
  • 调整：从倒数第二个节点 3 开始，它的子节点是 2。因为 3 > 2，不需要调整。
  • 调整：到节点 1，它的子节点是 3 和 2。因为 3 > 1，所以把 1 和 3 交换。现在数组变成 [4, 3, 1, 2]。
  • 调整：到节点 4，它的子节点是 3 和 1。因为 4 > 3，不需要调整。
  • 最终，我们得到了一个大顶堆，对应的数组是 [4, 3, 1, 2]。
第二步：排序
  1. 把最大的元素（4）和最后一个元素（2）交换。数组变成 [2, 3, 1, 4]。
    • 现在 4 已经排好序了。
    • 我们只关注 [2, 3, 1]。
  2. 对剩下的 [2, 3, 1] 重新调整为大顶堆。
    • 调整后，最大的元素 3 跑到最前面，数组变成 [3, 2, 1]。
    • 把 3 和 1 交换。数组变成 [1, 2, 3, 4]。
    • 现在 3 已经排好序了。
    • 我们只关注 [1, 2]。
  3. 对剩下的 [1, 2] 重新调整为大顶堆。
    • 调整后，最大的元素 2 跑到最前面，数组变成 [2, 1]。
    • 把 2 和 1 交换。数组变成 [1, 2, 3, 4]。
    • 现在 2 已经排好序了。
    • 我们只关注 [1]。
  4. 只剩一个元素 1，它天然就是排好序的。

至此，排序完成，数组变成了 [1, 2, 3, 4]。

堆排序的优缺点

优点
  • 性能稳定：不管数组最初是什么样子，它的时间复杂度总是 O(nlogn)。
  • 空间利用率高：它是一种原地排序算法，只需要极少的额外空间。
缺点
  • 不太稳定：如果数组中有相同的元素，排序后它们的相对位置可能会发生变化。
  • 实现上比快速排序或归并排序复杂一些。

Example Code

#include <iostream>
#include <vector>
#include <algorithm> // Required for std::swap

/**
 * @brief Adjusts a subtree rooted at index i into a max-heap.
 *
 * This function assumes that the children of node i (if they exist)
 * are already max-heaps. It ensures that the node at index i
 * satisfies the max-heap property.
 *
 * @param arr The vector representing the heap.
 * @param n The current size of the heap (number of active elements).
 * @param i The index of the root of the subtree to be heapified.
 */
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;       // Initialize largest as root
    int left = 2 * i + 1;  // Left child's index
    int right = 2 * i + 2; // Right child's index

    // If left child is within the bounds of the heap and is larger than current largest
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // If right child is within the bounds of the heap and is larger than current largest
    if (if (right < n && arr[right] > arr[largest])) {
        largest = right;
    }

    // If the largest element is not the root
    if (largest != i) {
        std::swap(arr[i], arr[largest]); // Swap the root with the largest child

        // Recursively heapify the affected sub-tree (where the swap occurred)
        heapify(arr, n, largest);
    }
}

/**
 * @brief Sorts a vector using the Heap Sort algorithm.
 *
 * Heap Sort works in two main phases:
 * 1. Building a max-heap from the input array.
 * 2. Repeatedly extracting the maximum element (root) and rebuilding the heap.
 *
 * @param arr The vector to be sorted.
 */
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 1. Build a max-heap
    // Iterate from the last non-leaf node up to the root.
    // The last non-leaf node is at index n/2 - 1 in a 0-indexed array.
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 2. Sort the array
    // Iterate from the last element down to the second element (index 1).
    for (int i = n - 1; i > 0; i--) {
        // Move current root (maximum element) to the end of the unsorted part
        std::swap(arr[0], arr[i]);

        // Call heapify on the reduced heap (excluding the already sorted elements).
        // The effective size of the heap is now 'i'.
        // The root (index 0) needs to be re-heapified.
        heapify(arr, i, 0);
    }
}

/**
 * @brief Prints the elements of a vector to the console.
 *
 * @param arr The vector to be printed.
 */
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}
/**
 * @brief Main function to demonstrate Heap Sort.
 */
int main() {
    std::vector<int> arr = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};

    std::cout << "Original array: ";
    printArray(arr);

    heapSort(arr);

    std::cout << "Sorted array: ";
    printArray(arr);

    return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布