【排序算法】选择排序、堆排序

堆排序是一种基于堆（Heap）数据结构的排序算法。最大堆：每个节点的值都大于或等于其子节点的值。根节点是最大值。最小堆：每个节点的值都小于或等于其子节点的值。根节点是最小值。首先将无序数组构建为一个最大堆。然后，将堆顶（即最大值）与数组的最后一个元素交换，缩小堆的范围，对剩下的元素继续调整成最大堆，直到排序完成。

勇敢勇勇不怕困难_

2351人浏览 · 2024-09-25 20:32:51

勇敢勇勇不怕困难_ · 2024-09-25 20:32:51 发布

文章目录

选择排序
选择排序-优化
- 双向选择排序的步骤
堆

选择排序

选择排序的概念

选择排序是一种简单直观的排序算法。它的工作原理是每次从未排序的部分中选择一个最小（或最大）的元素，并将其与未排序部分的第一个元素进行交换。这个过程重复 n-1 次，直到数组排序完毕。

选择排序的基本步骤：

从未排序的部分中找到最小的元素。
将这个元素与未排序部分的第一个元素交换。
每次遍历数组，未排序部分就会减少，已排序部分逐渐扩大。
当所有元素都经过选择排序后，数组就变为有序的。

选择排序的特点

时间复杂度: O(n²)，因为对于每个元素，都需要扫描剩下的未排序元素来找到最小值。
空间复杂度: O(1)，因为它是原地排序算法，不需要额外的存储空间。
稳定性: 选择排序是不稳定的排序算法。因为元素交换时，可能会改变相同值元素的相对顺序。
虽然很好理解，效率不好，实际中很少使用。

选择排序的代码实现（C语言）

#include <stdio.h>

// 选择排序函数
void SelectionSort(int arr[], int n) {
    // 外层循环，逐渐缩小未排序部分
    for (int i = 0; i < n - 1; i++) {
        // 初始化最小值的索引为当前未排序部分的第一个元素
        int minIndex = i;
//注意i<n-1，因为i之后会比较j=i+1的值
//但j是<n,可以走到最后一个
        // 内层循环，从 i+1 开始查找未排序部分的最小元素
        for (int j = i + 1; j < n; j++) {
            // 如果找到比当前最小值更小的元素，更新最小值索引
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // 如果最小值的索引不是 i，则交换元素
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

// 打印数组函数
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    // 示例数组
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组: ");
    PrintArray(arr, n);

    // 执行选择排序
    SelectionSort(arr, n);

    printf("排序后的数组: ");
    PrintArray(arr, n);

    return 0;
}

输出示例

排序前的数组: 64 25 12 22 11 
排序后的数组: 11 12 22 25 64

详细讲解

外层循环 for (int i = 0; i < n - 1; i++):
- 控制循环次数，每次选择一个最小元素并将其放到正确位置。
- 循环结束后，前 i 个元素已经排好序。
初始化最小值索引int minIndex = i;:
- 在每一轮选择中，将当前未排序部分的第一个元素假设为最小元素。
内层循环 for (int j = i + 1; j < n; j++):
- 通过从 i+1 开始的未排序部分中寻找最小值。
- 如果发现比当前最小值更小的元素，更新 minIndex，标记该元素的索引。
元素交换 if (minIndex != i):
- 如果最小值不是当前元素，就交换最小值和未排序部分第一个元素。
- 交换之后，已排序部分扩大一个元素。
PrintArray()** 函数**:
- 一个简单的辅助函数，用于打印数组的当前状态。

选择排序的运行步骤举例

假设排序数组 arr[] = {64, 25, 12, 22, 11}:

第1轮:
- i = 0，未排序部分为 {64, 25, 12, 22, 11}。
- 找到最小值 11，将其与 64 交换，数组变为 {11, 25, 12, 22, 64}。
第2轮:
- i = 1，未排序部分为 {25, 12, 22, 64}。
- 找到最小值 12，将其与 25 交换，数组变为 {11, 12, 25, 22, 64}。
第3轮:
- i = 2，未排序部分为 {25, 22, 64}。
- 找到最小值 22，将其与 25 交换，数组变为 {11, 12, 22, 25, 64}。
第4轮:
- i = 3，未排序部分为 {25, 64}。
- 最小值是 25，不需要交换，数组保持 {11, 12, 22, 25, 64}。

最后得到有序数组 {11, 12, 22, 25, 64}。

总结

选择排序的核心思想就是每次从未排序的部分中选择最小的元素，并把它放到正确的位置。虽然算法实现简单，但它的时间复杂度为 O(n²)，效率较低，适用于小规模数组的排序问题。

选择排序-优化

双向选择排序或双端选择排序，这种方法通过同时从两个方向进行选择，以减少排序的时间复杂度。具体来说，它在每一轮中既选择最小值也选择最大值，并将它们放到数组的两端。

双向选择排序的步骤

初始化：设置两个指针，一个指向数组的开始位置（left），一个指向数组的结束位置（right）。
选择最小值和最大值：
- 遍历当前的未排序部分，找到最小值和最大值。
- 将最小值放到left指针指向的位置，将最大值放到right指针指向的位置。
更新指针：
- 将left指针向右移动一位（因为最小值已经放到正确的位置）。
- 将right指针向左移动一位（因为最大值已经放到正确的位置）。
重复步骤2和3，直到left指针与right指针交叉或重叠。

双向选择排序的C语言实现

#include <stdio.h>

// 函数用于交换两个整数的值
void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

// 双向选择排序函数
void biDirectionalSelectionSort(int arr[], int n) {
    int left = 0;          // 指向未排序部分的起始位置
    int right = n - 1;     // 指向未排序部分的结束位置

    while (left < right) {
        int minIndex = left;   // 初始化最小值的索引
        int maxIndex = right;  // 初始化最大值的索引

        // 遍历未排序部分，找到最小值和最大值
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[minIndex]) {
                minIndex = i;
            }
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }

        // 交换最小值到当前左边界
        swap(&arr[left], &arr[minIndex]);

        // 如果最大值在左边界位置，交换最大值到右边界位置
        if (maxIndex == left) {
            maxIndex = minIndex; // 更新最大值的索引
        }
        // 交换最大值到当前右边界
        swap(&arr[right], &arr[maxIndex]);

        // 更新边界
        left++;
        right--;
    }
}

// 辅助函数：打印数组元素
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 测试双向选择排序的主函数
int main() {
    int arr[] = {64, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：\n");
    printArray(arr, n);

    biDirectionalSelectionSort(arr, n);

    printf("排序后的数组：\n");
    printArray(arr, n);

    return 0;
}

swap函数：
- 用于交换两个整数的值，以便在数组中重新排列元素。
biDirectionalSelectionSort函数：
- 初始化：left指针从数组的开始位置开始，right指针从数组的结束位置开始。
- 找到最小值和最大值：
  - 遍历当前未排序的部分，记录最小值和最大值的索引。
- 交换最小值和最大值：
  - 将最小值交换到left位置。
  - 如果最大值在left位置（也就是最小值交换后，最大值可能在左边），需要更新最大值的索引，然后将最大值交换到right位置。
- 更新边界：
  - 将left指针向右移动一位，将right指针向左移动一位，准备处理下一轮。
printArray函数：
- 用于打印数组中的元素，帮助观察排序的结果。
main函数：
- 初始化一个数组，打印原始数组，调用biDirectionalSelectionSort函数进行排序，然后打印排序后的数组。

性能分析

时间复杂度：最坏情况下是O(n^2)，因为每一轮的遍历操作都需要O(n)的时间，总共会执行n/2轮。
空间复杂度：O(1)，因为排序过程在原地完成，没有使用额外的存储空间。

双向选择排序通过同时选择最小值和最大值来减少了需要排序的次数，从而比传统的选择排序略微优化了性能。

堆

堆的基本概念

堆是一种特殊的完全二叉树，满足以下条件：

最大堆（Max-Heap）：在最大堆中，每个父节点的值都大于或等于其子节点的值。因此，堆顶（根节点）是最大值。
最小堆（Min-Heap）：在最小堆中，每个父节点的值都小于或等于其子节点的值，因此堆顶是最小值。

堆是一个完全二叉树，因此它可以用数组来高效地表示。对于任意节点i：

左子节点的索引是2 * i + 1
右子节点的索引是2 * i + 2
父节点的索引是(i - 1) / 2

堆排序详细步骤

1. 构建最大堆

构建最大堆的过程是从最后一个非叶子节点开始，依次对每一个节点执行“堆化”操作。堆化（Heapify）是一个过程，它将以某个节点为根的子树调整为最大堆。

构建最大堆的过程：

从数组的最后一个非叶子节点开始（索引为n/2 - 1），向前逐步调整每个节点，保证每个子树都是最大堆。

2. 排序过程

将堆顶（最大值）与堆的最后一个元素交换，堆的大小减1。
重新调整堆（heapify），以确保剩下的部分仍然是最大堆。
重复上述步骤，直到堆的大小减小到1。

代码实现

#include <stdio.h>

// 函数用于交换两个整数的值
void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

// 函数用于维护最大堆的性质
void heapify(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(int arr[], int n) {
    // 构建最大堆
    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);
    }
}

// 辅助函数：打印数组元素
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 测试堆排序的主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：\n");
    printArray(arr, n);

    heapSort(arr, n);

    printf("排序后的数组：\n");
    printArray(arr, n);

    return 0;
}

代码逐步讲解

swap函数：
- 交换两个整数的值，用于调整堆中元素的位置。
heapify函数：
- heapify用于维护最大堆的性质。它从节点i开始，调整以i为根的子树，确保子树符合最大堆的特性。
- largest变量用来追踪当前子树中的最大值索引。
- 如果largest不是i，说明子树不符合最大堆的特性，需要交换并递归调用heapify。
heapSort函数：
- 首先构建最大堆。for循环从最后一个非叶子节点开始，通过heapify将整个数组调整为最大堆。
- 然后逐个取出堆顶元素（最大值）并将其与数组的最后一个元素交换，接着调整剩余部分，保持最大堆的性质。
printArray函数：
- 打印数组中的元素，帮助观察排序的结果。
main函数：
- 初始化一个数组，打印原始数组，调用heapSort函数进行排序，然后打印排序后的数组。

希望这些详细解释和代码示例能帮助你更好地理解堆排序。如果还有其他问题或需要更深入的解释，请告诉我！

堆排序代码讲解

堆排序简介

堆排序是一种基于堆（Heap）数据结构的排序算法。堆是一棵完全二叉树，可以通过数组表示：

最大堆：每个节点的值都大于或等于其子节点的值。根节点是最大值。
最小堆：每个节点的值都小于或等于其子节点的值。根节点是最小值。

堆排序的核心思想是：

首先将无序数组构建为一个最大堆。
然后，将堆顶（即最大值）与数组的最后一个元素交换，缩小堆的范围，对剩下的元素继续调整成最大堆，直到排序完成。

1. `AdjustDown` 函数分析（向下调整）

该函数用于维护最大堆的性质。它从父节点开始，将其与子节点比较，并向下调整，使得父节点的值始终大于等于它的子节点。

void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1; // 左孩子的索引
    while (child < n) // 确保孩子节点存在
    {
        // 找出两个孩子中较大的那个
        if (child + 1 < n && a[child + 1] > a[child])
        {
            ++child; // 右孩子比左孩子大，选择右孩子
        }

        // 如果孩子的值大于父节点，则进行交换
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]); // 交换父节点和较大孩子
            // 继续向下调整，将孩子当作新的父节点
            parent = child;
            child = parent * 2 + 1; // 更新左孩子的索引
        }
        else
        {
            break; // 如果父节点已经大于等于孩子，则无需再调整
        }
    }
}

解释：

child = parent * 2 + 1：左孩子节点的索引。因为堆是一棵完全二叉树，所以对于索引为 parent 的节点，左孩子的索引为 2 * parent + 1，右孩子的索引为 2 * parent + 2。
核心逻辑：找到较大的孩子（如果右孩子存在并且比左孩子大，则选择右孩子），并与父节点进行比较，如果父节点比孩子小，则交换它们的值，并继续向下调整。
while 循环确保只要存在孩子节点，继续调整，直到父节点大于等于孩子节点或到达树的底部。

2. `HeapSort` 函数分析（堆排序的实现）

void HeapSort(int* a, int n)
{
    // 建堆过程，从最后一个非叶子节点开始调整，逐步向上调整
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    // 逐步将堆顶元素（最大值）与最后一个未排序元素交换
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]); // 将堆顶元素与当前未排序部分的最后一个元素交换
        AdjustDown(a, end, 0); // 重新调整堆，使剩余部分维持最大堆的性质
        --end; // 排除最后一个已排序的元素
    }
}

详细讲解：

建堆过程：
- for (int i = (n - 1 - 1) / 2; i >= 0; i--)：
  - (n - 1 - 1) / 2 计算的是最后一个非叶子节点的索引。叶子节点不需要调整，所以从最后一个非叶子节点开始向上遍历，逐一调整每个节点，以确保整个数组满足最大堆的性质。
  - 调用 AdjustDown(a, n, i) 对从 i 开始的子树进行调整，确保以 i 为根节点的子树是一个最大堆。
排序过程：
- Swap(&a[0], &a[end])：将当前堆的堆顶元素（最大值）与最后一个未排序的元素交换。
- AdjustDown(a, end, 0)：交换后，堆顶元素可能破坏了堆的性质，需要再次从堆顶（即索引 0）开始进行向下调整，恢复最大堆性质。
- --end：每次处理完一个最大元素后，end 减少1，表示缩小待排序区域，直到所有元素都排序完成。

示例：堆排序的执行过程

假设我们有一个数组 [4, 10, 3, 5, 1]，我们将详细分析堆排序的执行过程。

建堆：
- 原数组为 [4, 10, 3, 5, 1]。
- 从最后一个非叶子节点开始（i = 1，即 10）。
  - 比较 10 与其孩子（5 和 1），10 已经大于它的孩子，不需要调整。
- 继续处理 i = 0（4）。
  - 比较 4 与其孩子（10 和 3），10 更大，交换 4 和 10。
  - 现在数组变为 [10, 4, 3, 5, 1]。
  - 继续向下调整，4 与它的孩子 5 比较，交换 4 和 5，得到 [10, 5, 3, 4, 1]。
- 完成建堆后，最大堆为 [10, 5, 3, 4, 1]。
排序：
- 交换堆顶 10 和最后一个元素 1，得到 [1, 5, 3, 4, 10]。
- 调整堆 [1, 5, 3, 4]，结果是 [5, 4, 3, 1, 10]。
- 继续交换堆顶 5 和 1，得到 [1, 4, 3, 5, 10]。
- 调整堆 [1, 4, 3]，结果是 [4, 1, 3, 5, 10]。
- 交换堆顶 4 和 3，得到 [3, 1, 4, 5, 10]，调整堆 [3, 1]，结果是 [3, 1, 4, 5, 10]。
- 最后交换 3 和 1，得到 [1, 3, 4, 5, 10]。