数据结构之选择排序

简单选择排序

1. 基本思想

选择排序的主要思路是：

每一趟在未排序的部分中找到最小（或最大）元素。
将这个最小元素与当前排序部分的下一个位置的元素交换。
通过这种方式，不断扩展已排序的部分，直到所有元素都被排序。

2. 算法步骤

对于给定的排序表 $ L[1..n] $：

从第 1 个元素开始，依次进行以下操作，直到第 $ n-1 $ 趟：
- 假设当前未排序部分为 $ L[i..n] $。
- 在 $ L[i..n] $ 中找到最小元素，并记录其索引。
- 将最小元素与 $ L[i] $ 交换。
当所有趟次完成后，整个数组就会变得有序。

3. 代码实现

以下是简单选择排序的 C++ 代码实现：

#include <iostream>
using namespace std;

// 交换函数
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 简单选择排序函数
void SelectSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) { // 一共进行 n-1 趟
        int minIndex = i; // 记录最小元素位置
        // 在 A[i..n-1] 中选择最小的元素
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[minIndex]) { // 更新最小元素位置
                minIndex = j;
            }
        }
        // 如果找到的最小元素不是当前位置的元素，则进行交换
        if (minIndex != i) {
            swap(A[i], A[minIndex]); // 封装的 swap() 函数共移动元素 3 次
        }
    }
}

// 测试函数
int main() {
    int A[] = {64, 25, 12, 22, 11}; // 待排序数组
    int n = sizeof(A) / sizeof(A[0]); // 数组长度

    SelectSort(A, n); // 调用选择排序

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << A[i] << " "; // 输出排序后的数组
    }
    cout << endl;

    return 0;
}

4. 复杂度分析

1. 时间复杂度分析

选择排序的时间复杂度主要分为两个部分：比较操作和交换操作。

1.1 比较操作

在选择排序的过程中，每一趟都会遍历未排序部分的所有元素，以找到最小的元素。具体地：

第 1 趟：需要比较 $n-1$ 次（与第一个元素比较）。
第 2 趟：需要比较 $n-2$ 次（与第二个元素比较）。
...
第 $n-1$ 趟：需要比较 1 次（与倒数第二个元素比较）。

因此，总的比较次数为：

$ = (n-1) + (n-2) + ... + 1 = $

这表明选择排序在最坏情况下的比较次数为 $O(n^2)$，而无论输入数据的初始状态如何，总比较次数都是 $O(n^2)$。

1.2 交换操作

在选择排序的过程中，每一趟最多只会进行一次交换（即将找到的最小元素与当前元素交换），因此：

最坏情况下的交换次数：不超过 $n-1$ 次（在每一趟中最多交换一次）。
最好情况下的交换次数：可能是 0 次（如果数组已经有序）。

在任何情况下，交换操作的数量是相对较少的，相对于比较次数而言。

1.3 综述

由于选择排序的比较次数是主要的复杂度来源，综合考虑后，选择排序的时间复杂度为：

$ O(n^2) $

2. 空间复杂度分析

选择排序的空间复杂度是指算法在运行过程中需要额外的存储空间。

选择排序只使用了常数空间来存储一些变量（如最小元素的索引），而不需要额外的存储结构。因此，其空间复杂度为：

$ O(1) $

3. 稳定性分析

选择排序是一种不稳定的排序算法，原因如下：

在第 $i$ 趟选择排序中，如果当前最小元素与第 $i$ 个元素相同，交换操作会导致相同元素之间的相对顺序发生变化。
例如，考虑一个数组 $L = [2, 2, 1]$。在第一趟排序中，最小元素 $1$ 被找到并与 $2$ 交换，最终的数组将变为 $L = [1, 2, 2]$。此时，两个 $2$ 的相对顺序被改变，表明选择排序不是稳定的。

堆排序

1. 堆的定义

堆是一种特殊的完全二叉树，可以分为两种类型：

大根堆（Max Heap）：对于堆中的每一个节点 $L(i)$，都满足 $L(i) \geq L(2i)$ 且 $L(i) \geq L(2i + 1)$，即父节点的值大于等于其子节点的值，根节点是最大值。
小根堆（Min Heap）：对于堆中的每一个节点 $L(i)$，都满足 $L(i) \leq L(2i)$ 且 $L(i) \leq L(2i + 1)$，即父节点的值小于等于其子节点的值，根节点是最小值。

2. 堆排序的基本思路

堆排序的基本思路如下：

构造初始堆：将待排序数组构造成一个大根堆（或小根堆），使得堆顶元素为最大值（或最小值）。
输出堆顶元素：将堆顶元素（最大值或最小值）与堆的最后一个元素交换，然后减少堆的有效大小。
调整堆：对新的堆顶元素进行下调，以恢复堆的性质。
重复步骤2和步骤3：直到堆中仅剩一个元素。

3. 建堆过程

建堆的关键是从最后一个非叶子节点开始，对每个节点进行调整。对于一个包含 $n$ 个节点的完全二叉树，最后一个非叶子节点的索引为 $\lfloor n/2 \rfloor$。

伪代码：

void BuildMaxHeap(ElemType A[], int len) {
    for (int i = len / 2; i > 0; i--) {
        HeadAdjust(A, i, len);
    }
}

堆调整的过程：

在调整过程中，将节点 $k$ 的值与其左右子节点中的较大者进行比较，并交换位置，使得子树成为大根堆。

伪代码：

void HeadAdjust(ElemType A[], int k, int len) {
    ElemType temp = A[k]; // 暂存子树的根节点
    for (int i = 2 * k; i <= len; i *= 2) {
        if (i < len && A[i] < A[i + 1]) { // 选择较大的子节点
            i++; // i指向较大的子节点
        }
        if (temp >= A[i]) break; // 位置已符合堆的定义
        A[k] = A[i]; // 将较大子节点上移
        k = i; // 更新k的值
    }
    A[k] = temp; // 将暂存的根节点放到适当的位置
}

4. 堆排序算法

伪代码：

void HeapSort(ElemType A[], int len) {
    BuildMaxHeap(A, len); // 建立大根堆
    for (int i = len; i > 1; i--) {
        Swap(A[i], A[1]); // 将堆顶元素与最后一个元素交换
        HeadAdjust(A, 1, i - 1); // 重新调整堆
    }
}

5. 性能分析

时间复杂度：
- 建堆的时间复杂度为 $O(n)$。虽然每个节点的调整最多需要 $O(\log n)$，但由于树的高度为 $O(\log n)$，且叶子节点较多，所以总体建堆时间是线性的。
- 在堆排序过程中，交换和调整的总时间为 $O(n \log n)$。因此，堆排序的时间复杂度为：
$ O(n n) $
空间复杂度：
- 堆排序只使用了常数个额外的存储空间，因此空间复杂度为：
$ O(1) $
稳定性：
- 堆排序不是稳定的排序算法。在调整过程中，相同关键字的元素可能会改变相对顺序。例如，对于序列 $L = [1, 2, 2]$，在构造初始堆时可能将 $2$ 交换到堆顶，导致最终排序结果可能是 $L = [1, 2, 2]$，从而改变了 $2$ 的相对顺序。