当前位置： 首页 > article >正文

常见的排序算法（二）

article 2024/12/25 1:39:00

归并排序

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的排序算法。它将一个大的问题分解成小的问题，然后递归地解决这些小问题，最后合并（merge）得到最终的排序结果。归并排序的时间复杂度为 ( O(n \log n) )，它是一种稳定的排序算法。由于其稳定性和良好的最坏情况表现，归并排序在许多实际应用中都有着重要的地位。

一、归并排序的基本思想

归并排序的核心思想是将数组分成两个子数组，对这两个子数组分别进行排序，排序完成后再将它们合并成一个有序数组。归并排序的分治过程通常通过递归来实现：

  1. 分解：将数组分成两半。
  2. 解决：递归地对这两半数组分别进行归并排序。
  3. 合并：将两个有序的子数组合并成一个有序数组。

这种方法可以持续分解直到每个子数组只有一个元素，因为一个元素的数组默认是有序的。然后通过合并操作将这些有序的子数组组合成一个大的有序数组。

二、归并排序的具体步骤

1. 递归分解

首先，将一个大的数组分解成两个小数组，再递归地对这两个小数组进行归并排序，直到每个数组只有一个元素。

2. 合并操作

合并是归并排序的核心步骤。将两个已经排好序的数组合并成一个有序数组。对于每对元素，比较它们的大小，把较小的元素放入结果数组中，直到所有元素都合并完成。

3. 递归的终止条件

递归终止的条件是子数组的大小为1，此时该子数组已经是有序的，可以进行合并。

三、归并排序的时间复杂度分析

归并排序的时间复杂度为 ( O(n \log n) )，其中：

  • 分解的次数：每次将数组分成两半，直到每个子数组只有一个元素。这个过程是递归的，深度为 ( \log n )。
  • 合并的时间复杂度：每次合并操作需要遍历所有的元素，时间复杂度为 ( O(n) )。

因此，归并排序的总时间复杂度是 ( O(n \log n) )。

四、归并排序的空间复杂度分析

归并排序需要额外的空间来存储合并过程中生成的临时数组。每一次合并都需要额外的空间，因此空间复杂度为 ( O(n) )。

五、归并排序的特点

  1. 稳定性：归并排序是一个稳定的排序算法，即两个相等的元素在排序后相对位置不变。
  2. 时间复杂度：在最坏、最好、平均情况下，归并排序的时间复杂度都是 ( O(n \log n) )。
  3. 空间复杂度：归并排序需要额外的 ( O(n) ) 空间来存储临时数据。
  4. 适用场景：适用于大规模数据排序，尤其是当数据量很大时，归并排序表现非常稳定。特别适用于外部排序（比如磁盘上的数据排序）。

六、归并排序的C语言实现

下面是归并排序的 代码示例：

#include <stdio.h>

// 合并两个子数组 arr[left..mid] 和 arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;  // 左子数组的长度
    int n2 = right - mid;     // 右子数组的长度

    // 创建临时数组
    int leftArr[n1], rightArr[n2];

    // 将数据复制到临时数组
    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int i = 0; i < n2; i++)
        rightArr[i] = arr[mid + 1 + i];

    // 合并临时数组到原始数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 将剩余的元素复制到原数组
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// 归并排序的递归实现
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // 计算中间位置

        // 递归排序左半部分
        mergeSort(arr, left, mid);

        // 递归排序右半部分
        mergeSort(arr, mid + 1, right);

        // 合并已排序的子数组
        merge(arr, left, mid, right);
    }
}

// 打印数组
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 arr_size = sizeof(arr) / sizeof(arr[0]);

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

    mergeSort(arr, 0, arr_size - 1);  // 调用归并排序

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

    return 0;
}

代码解释：

  1. merge函数：合并两个已经排序的子数组。arr[left..mid] 和 arr[mid+1..right]，将它们合并成一个有序数组并放回原数组 arr 中。
  2. mergeSort函数：归并排序的递归实现，首先将数组分割成两个子数组，然后递归地对这两个子数组进行排序，最后合并它们。
  3. printArray函数：打印数组，用于显示排序前后的数组。

测试结果：

原始数组: 12 11 13 5 6 7 排序后的数组: 5 6 7 11 12 13

七、归并排序的改进

尽管归并排序是一种非常有效的排序算法，但它的空间复杂度 ( O(n) ) 使得它在某些情况下表现不如其他排序算法。例如，对于小规模的数据，快速排序和堆排序可能会有更好的表现。为了优化归并排序的一些空间消耗，有人提出了优化版本：

  1. 原地归并排序：将归并过程进行修改，避免使用额外的数组来存储临时数据，减少空间开销。但这会使代码变得更加复杂。

  2. 优化合并过程：对于已经部分有序的数组，优化合并过程，减少不必要的操作。

小结：

归并排序作为一种稳定的、时间复杂度为 ( O(n \log n) ) 的排序算法，适用于大规模数据的排序。尽管它需要额外的空间，但其性能非常稳定，在最坏情况下也不会退化。归并排序尤其在外部排序中有重要应用，比如对磁盘中的大量数据进行排序。

堆排序

堆排序（Heap Sort）是一种利用堆（Heap）数据结构的排序算法。它的核心思想是通过构建最大堆或最小堆来排序。堆是一种完全二叉树，满足堆的性质，即每个节点的值都大于或小于其子节点的值。堆排序通过不断地调整堆的结构来实现排序。

一、堆的定义与性质

堆是一个完全二叉树，并且满足以下两个性质之一：

  • 最大堆：对于树中的任意节点 ( i )，有 ( A[i] \geq A[2i+1] ) 和 ( A[i] \geq A[2i+2] )，即父节点的值大于或等于子节点的值。
  • 最小堆：对于树中的任意节点 ( i )，有 ( A[i] \leq A[2i+1] ) 和 ( A[i] \leq A[2i+2] )，即父节点的值小于或等于子节点的值。

二、堆排序的基本步骤

堆排序的过程可以分为两大部分：

  1. 构建堆：将无序数组构建成一个堆。堆可以是最大堆或最小堆，通常我们使用最大堆来实现升序排序。
  2. 堆调整：将堆顶元素（最大值）与堆的最后一个元素交换，然后减少堆的大小（忽略最后一个元素），重新调整堆，使其恢复堆的性质。重复这个过程直到堆的大小为1。

堆排序的时间复杂度为 ( O(n \log n) )，其中 ( n ) 是待排序数组的元素个数。

三、 堆排序的工作原理

构建最大堆：
  1. 从最后一个非叶子节点开始，逐个向上调整每个节点的位置，使其满足最大堆的性质。
  2. 调整过程涉及比较父节点与子节点的值，若父节点小于任何一个子节点，就交换它们的位置，并递归地对交换后的子树进行调整。
堆排序的具体过程：
  1. 构建最大堆：从数组的最后一个非叶子节点开始，调整堆，直到根节点。
  2. 交换根节点与最后一个节点：将堆顶元素（最大元素）与数组最后一个元素交换。
  3. 减少堆的大小：忽略最后一个元素（它已经是排好序的），调整剩下的元素，使其重新成为最大堆。
  4. 重复上述步骤：直到堆中只剩下一个元素为止。

四、 堆排序的代码实现

接下来，通过C语言实现堆排序的具体过程。我们首先需要实现最大堆的调整操作，然后通过交换堆顶元素与堆的最后一个元素来实现排序。

#include <stdio.h>

// 调整堆的函数，确保根节点满足最大堆性质
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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // 递归地调整被交换位置的子树
        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 >= 1; i--) {
        // 交换根节点（最大值）与当前最后一个元素
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 调整堆的大小
        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;
}
代码解析：

  1. heapify函数：该函数用于调整堆的性质。它接收数组 arr，数组大小 n，和当前节点的索引 i。通过比较当前节点与左右子节点的值，决定是否交换它们，并递归地调整子树，直到整个子树满足堆的性质。

  2. heapSort函数：该函数实现堆排序的主逻辑。首先通过 heapify 构建一个最大堆，然后将堆顶的最大元素与堆的最后一个元素交换，减少堆的大小，再次调用 heapify 调整堆。重复这一过程，直到所有元素都被排好序。

  3. printArray函数：打印数组，用于查看排序前后的结果。

  4. main函数：主函数中，我们定义了一个待排序的数组，调用堆排序函数，并输出排序结果。

五、堆排序的时间复杂度分析

堆排序的时间复杂度是 ( O(n \log n) )，下面是详细分析：

  • 构建最大堆：从最后一个非叶子节点开始，调整堆。调整每个节点的时间复杂度是 ( O(\log n) )，总的构建堆的时间复杂度是 ( O(n) )。

  • 交换与堆调整：在堆排序过程中，每次将堆顶元素交换到数组末尾，然后减少堆的大小并调整堆。每次调整堆的时间复杂度是 ( O(\log n) )，总共需要进行 ( n-1 ) 次交换，因此总体时间复杂度是 ( O(n \log n) )。

综上所述，堆排序的时间复杂度为 ( O(n \log n) )。

六、 堆排序的空间复杂度

堆排序的空间复杂度是 ( O(1) )，因为它是原地排序算法，不需要额外的空间来存储数据，只需要常数空间来存储一些辅助变量。

七、堆排序的优缺点

优点：
  • 时间复杂度稳定：无论数据的初始状态如何，堆排序的时间复杂度始终是 ( O(n \log n) )，不像快速排序那样最坏情况下退化到 ( O(n^2) )。
  • 原地排序：堆排序不需要额外的存储空间，只需要常数空间。
缺点：
  • 不稳定排序：堆排序是一个不稳定的排序算法，即相等的元素可能会改变相对顺序。
  • 常数因子较大：与快速排序相比，堆排序常数因子较大，通常在实际应用中速度较慢。

八、总结

堆排序是一种基于堆数据结构的高效排序算法，它通过构建最大堆（或最小堆）来实现排序。堆排序具有 ( O(n \log n) ) 的时间复杂度，并且是原地排序算法，不需要额外的空间。然而，堆排序的主要缺点是它是一种不稳定排序，因此在一些需要稳定排序的场合，可能需要选择其他排序算法。


http://www.kler.cn/a/382116.html

相关文章：

  • AI可信论坛亮点：合合信息分享视觉内容安全技术前沿
  • Spring（三）-SpringWeb-概述、特点、搭建、运行流程、组件、接受请求、获取请求数据、特殊处理、拦截器
  • LAUNCHXL_F28379D_Workspace_CCS124
  • Spring Security 6 系列之七 - 自定义异常管理
  • BunkerWeb 开源项目安装与使用教程
  • Java字符串的|分隔符转List实现方案
  • 微信小程序的汽车维修预约管理系统
  • 【xml转JSON】
  • nginx 搭建网站
  • Django Admin
  • Redis 中 Bitmap 原理和应用
  • LeetCode 2487.从链表中移除节点
  • C++ | Leetcode C++题解之第523题连续的子数组和
  • pytorch学习：矩阵分解：奇异值分解（SVD分解）
  • DevOps-课堂笔记
  • 服了！这波大选，赚最肥的居然是搞AI写作的
  • 深入浅出：解读注意力机制，让神经网络更“聪明”
  • ubuntu 安装go和vscode
  • 二次封装 el-pagination 组件存在的问题
  • Mac使用记事
  • JAVA基础：多重循环、方法、递归 （习题笔记）
  • 看到你还在用Maven，Gradle难道不香吗？
  • 霍尼韦尔测厚仪51000372怎么工作
  • stm32 挂死定位（死循环）
  • 【LeetCode】【算法】160.相交链表
  • 微信小程序寓言童话创作APP设计与实现