Skip to content

算法

讲讲快速排序的原理？

快速排序（Quick Sort）是由 Tony Hoare 在1960年代初期发明的一种排序算法。它是一种高效、就地、不稳定的比较排序算法。

快速排序的基本思想很简单：选择数组中的一个元素作为“基准”（pivot），然后将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素。这个分区操作是线性时间的，且可以原地完成。然后，算法递归地排序这两个子数组。

快速排序的性能取决于选择的基准元素。在最理想的情况下，选择的基准恰好将数组分成两个相等的部分，使得快速排序的性能最大化。这导致一个 \( O(n \log n) \) 的平均时间复杂度。但在最坏的情况下，例如当输入数组已经排序，并且我们总是选择第一个或最后一个元素作为基准，快速排序的时间复杂度会退化到 \(O(n^2)\)。

为了防止最坏情况的发生，实际的快速排序实现通常使用了一些策略，例如随机选择基准，或者使用“三分中值”策略（从数组的首部、中部、尾部选择三个元素，并使用它们的中值作为基准）。

尽管在最坏的情况下快速排序可能不是最佳的，但由于它的平均性能非常好并且有较好的缓存性能，它通常比其他 \(O(n \log n)\) 算法（如归并排序和堆排序）更快。

快排时间复杂度是多少？为什么？

为了证明快速排序的平均时间复杂度为 \( \Theta(n \log n) \)，我们需要考虑所有可能的基准元素的选择。证明的核心思想是利用随机选择的基准元素将数组均匀地分成两部分。

以下是简化的证明步骤：

  1. 分区的期望时间：

    我们考虑对大小为 \( n \) 的数组进行分区。无论如何选择基准，分区操作都是线性的，所以它的时间复杂度是 \( O(n) \)。

  2. 递归的期望次数：

    我们想要求的是，如果我们随机选择基准，那么递归调用的期望深度是多少。考虑最好的情况，我们每次都均匀地将数组分为两半，那么深度是 \( \log n \)。而最坏的情况是我们每次选择最小或最大的元素为基准，导致深度为 \( n \)。

    但是，随机选择基准意味着我们有相同的概率选择任何元素。因此，我们不太可能总是选择最差的基准。事实上，有相当大的概率选择将数组分为至少 \( 1/4 \) 到 \( 3/4 \) 的基准。这意味着，在平均情况下，我们的递归深度接近 \( \log n \)。

  3. 结合上述结果：

    考虑快速排序的递归树，每层的工作量是 \( O(n) \)，并且期望的层数为 \( O(\log n) \)。因此，平均情况下的总工作量是 \( O(n \log n) \)。

这是一个简化的证明，并且省略了一些细节和数学推导，但它提供了快速排序平均时间复杂度为 \( \Theta(n \log n) \) 的直观理由。

详细的证明需要用到主定理，分析递归算法的时间复杂度。

堆排序是怎么做的？

堆排序是基于二叉堆（通常是最大堆）数据结构的一种比较排序算法。它的主要思想是将数组转化为最大堆形式，然后通过不断地取出最大值（位于堆的顶部）并调整堆结构以保持其性质，达到排序的目的。

堆排序的过程可以分为两个主要步骤：

  1. 建堆：将输入的无序数组转化为一个最大堆（一般升序采用大顶堆，降序采用小顶堆）。
  2. 堆调整与排序：重复从最大堆中取出最大值（堆的顶部）并与堆的最后一个元素交换，然后调整堆的大小并重新调整剩余元素以满足最大堆的性质。

以下是堆排序的详细步骤：

  1. 建堆：

    • 从最后一个非叶子节点开始（即 n/2，其中 n 是数组的长度），执行下沉操作，确保子树满足最大堆的性质。
    • 逐渐向上处理每一个非叶子节点，直到整个数组变成一个最大堆。

  2. 堆调整与排序：

    • 将堆的根节点（当前最大值）与堆的最后一个节点交换，这样最大值就被放在了其正确的位置。
    • 减小堆的大小，排除刚刚处理的最大值。
    • 对当前的根节点进行下沉操作，以恢复最大堆的性质。
    • 重复上述步骤，直到堆的大小变为1。

以下是堆排序的简化版本的伪代码：

function heapify(arr, n, i) {
    largest = i;
    left = 2*i + 1;
    right = 2*i + 2;

    if left < n and arr[left] > arr[largest]
        largest = left;

    if right < n and arr[right] > arr[largest]
        largest = right;

    if largest != i
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
}

function heapSort(arr) {
    n = length(arr);

    // Build max heap
    for i from n/2 - 1 down to 0
        heapify(arr, n, i);

    // Extract elements from heap one by one
    for i from n-1 down to 1
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
}

堆排序的时间复杂度在最好、最坏和平均情况下都是 \(O(n \log n)\)。

哪些排序算法是稳定的？

稳定的排序算法保证相等的元素在排序后保持它们原始的相对顺序。以下是一些常见的稳定排序算法：

  1. 插入排序 (Insertion Sort)：在插入排序中，每个元素按顺序被插入到已排序的子数组中，确保已排序的子数组始终是稳定的。

  2. 冒泡排序 (Bubble Sort)：在冒泡排序中，相邻的元素被比较并交换，以确保最大的元素“冒泡”到数组的末尾。因为交换是基于相邻元素的比较，所以它保持了相等元素的相对顺序。

  3. 归并排序 (Merge Sort)：在归并排序中，数组被递归地分成两半，每半都独立地排序，然后这两半被合并。在合并过程中，如果两个元素相等，我们总是先选择来自左边子数组的元素，从而保持稳定性。

  4. 计数排序 (Counting Sort)：这是一个非比较排序，它根据整数键值的数量来确定每个元素的输出位置。由于元素按键值和原始顺序被处理，所以排序是稳定的。

  5. 桶排序 (Bucket Sort)：这也是一个非比较排序，它将元素分配到多个桶中，并对每个桶中的元素进行排序，通常使用另一个稳定的排序算法。最后，桶按顺序被连接起来以获得排序结果。

  6. 基数排序 (Radix Sort)：基数排序按照每一位来排序数字，从最低有效位（LSB）到最高有效位（MSB）或相反。每一位的排序通常使用稳定的排序算法，如计数排序。

要注意的是，某些排序算法可以被实现为稳定的或不稳定的，取决于实现的具体细节。例如，快速排序（Quick Sort）通常被实现为不稳定的，但可以通过某些技巧来实现其稳定性。然而，常见的快速排序实现通常是不稳定的。