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

排序算法C++

article 2024/11/17 3:24:50

冒泡排序

冒泡排序是一种简单直观的排序算法，它通过多次遍历列表，逐步将最大（或最小）的元素“冒泡”到列表的末尾。其名称源于算法的运行方式：较大的元素逐渐向上浮动，就像水中的气泡一样。

工作原理

  1. 遍历数组：从数组的第一个元素开始，依次比较相邻的两个元素。
  2. 比较并交换：如果前一个元素大于后一个元素，交换它们的位置。这样大的元素会向右移动。
  3. 重复步骤：继续进行这样的遍历，直到不需要再交换为止。在每次遍历中，最大的元素会冒泡到数组的末尾。
  4. 优化：如果在一次遍历中没有发生任何交换，则说明数组已经是有序的，可以提前终止排序过程。

冒泡排序的步骤举例

假设我们有一个数组 [5, 1, 4, 2, 8]，使用冒泡排序对其排序：

  1. 第一次遍历：

    • 比较 5 和 1，交换，数组变成 [1, 5, 4, 2, 8]。
    • 比较 5 和 4，交换，数组变成 [1, 4, 5, 2, 8]。
    • 比较 5 和 2，交换，数组变成 [1, 4, 2, 5, 8]。
    • 比较 5 和 8，不交换。
    • 第一次遍历结束，最大值 8 冒泡到数组末尾。

  2. 第二次遍历：

    • 比较 1 和 4，不交换。
    • 比较 4 和 2，交换，数组变成 [1, 2, 4, 5, 8]。
    • 比较 4 和 5，不交换。
    • 第二次遍历结束，次大值 5 已经排好位置。

  3. 后续遍历：

    • 剩下的元素会依次比较并排序，最终数组变为 [1, 2, 4, 5, 8]。

冒泡排序的特点

  • 时间复杂度：

    • 最坏情况：O(n^2)（数组逆序时，需要最多的比较和交换）。
    • 最好情况：O(n)（数组已经有序时，只需一次遍历）。
    • 平均情况：O(n^2)。

  • 空间复杂度：O(1)，因为它是原地排序，不需要额外的存储空间。

  • 稳定性：冒泡排序是稳定的，即相等的元素在排序后相对顺序不会改变。

优缺点

  • 优点：
    • 实现简单，易于理解。
    • 当数组接近有序时，性能较好，尤其是优化版冒泡排序可以提前终止。
  • 缺点：
    • 对于较大规模的数据集，效率不高，时间复杂度为 O(n^2)。

适用场景

冒泡排序通常用于教学目的或小数据集，因为它的实现和理解都比较简单，但在实际应用中，效率低于其他高级排序算法（如快速排序、归并排序等）。

#include <iostream>
#include <vector>
using namespace std;

class Sorter {
public:
    // 冒泡排序算法
    void bubbleSort(vector<int>& arr) {
        int n = arr.size();  // 获取数组的长度
        for (int i = 0; i < n - 1; ++i) {  // 控制遍历次数，总共需要遍历 n-1 轮
            bool swapped = false;  // 标志位，用于检查是否发生交换
            for (int j = 0; j < n - i - 1; ++j) {  // 遍历数组，逐一比较相邻元素
                if (arr[j] > arr[j + 1]) {  // 如果前一个元素大于后一个元素
                    swap(arr[j], arr[j + 1]);  // 交换这两个元素
                    swapped = true;  // 记录发生了交换
                }
            }
            if (!swapped) break;  // 如果没有发生交换，说明数组已经有序，提前结束
        }
    }
};

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};  // 初始化一个待排序的数组
    Sorter sorter;  // 创建 Sorter 类的对象

    cout << "原数组: ";
    for (int i : arr) cout << i << " ";  // 输出排序前的数组
    cout << endl;

    sorter.bubbleSort(arr);  // 调用冒泡排序算法进行排序

    cout << "冒泡排序后数组: ";
    for (int i : arr) cout << i << " ";  // 输出排序后的数组
    cout << endl;

    return 0;
}

快速排序

快速排序（QuickSort）是一种基于分治法（divide and conquer）的高效排序算法。它通过不断将数组分成两部分，递归地对两部分分别进行排序，从而达到整体有序的效果。相比于冒泡排序和选择排序，快速排序的平均时间复杂度为 O(n log n)，具有更高的效率。

快速排序的步骤

  1. 选取基准元素（Pivot）：

    • 从数组中选择一个元素作为基准（Pivot）。这个基准元素可以是数组的任意元素，常见的选法包括选择数组的第一个元素、最后一个元素、或随机选择一个元素。

  2. 划分数组：

    • 遍历数组，将数组中的元素根据与基准的大小进行划分：
      • 所有小于基准的元素放在基准的左边；
      • 所有大于基准的元素放在基准的右边。

  3. 递归排序：

    • 对划分后的左右两部分数组，递归地继续执行上述步骤，直到每部分只有一个或零个元素（此时数组已经有序）。

  4. 合并结果：

    • 递归结束后，左部分、基准元素和右部分已经各自有序，组合起来即可得到完整的有序数组。

快速排序的原理示例

假设我们有一个数组 [8, 3, 1, 7, 0, 10, 2]，使用快速排序的过程如下：

  1. 选择基准：

    • 选择第一个元素 8 作为基准。

  2. 划分数组：

    • 遍历数组，将元素划分为两部分：
      • 小于 8 的元素：[3, 1, 7, 0, 2]
      • 大于 8 的元素：[10]
      • 划分结果：[3, 1, 7, 0, 2] 8 [10]

  3. 递归排序：

    • 对左边部分 [3, 1, 7, 0, 2] 递归进行快速排序：
      • 选择基准 3，划分为 [1, 0, 2] 和 [7]，递归继续。
    • 对右边部分 [10]，无需再排序。

  4. 合并结果：

    • 合并左边已排序的部分、基准 8、右边已排序的部分，最终结果是 [0, 1, 2, 3, 7, 8, 10]。
#include <iostream>
#include <vector>
using namespace std;

class QuickSorter {
public:
    // 快速排序的主函数
    void quickSort(vector<int>& arr, int low, int high) {
        if (low < high) {
            // 获取划分点
            int pivotIndex = partition(arr, low, high);
            // 递归地对左右两部分排序
            quickSort(arr, low, pivotIndex - 1);  // 排序左半部分
            quickSort(arr, pivotIndex + 1, high); // 排序右半部分
        }
    }

private:
    // 划分函数，返回基准的最终位置
    int partition(vector<int>& arr, int low, int high) {
        int pivot = arr[high];  // 选择最右边的元素作为基准
        int i = low - 1;  // 用于记录小于基准的元素位置

        for (int j = low; j < high; ++j) {
            if (arr[j] < pivot) {  // 如果当前元素小于基准
                i++;  // 增加小于基准元素的索引
                swap(arr[i], arr[j]);  // 交换小于基准的元素到前面
            }
        }
        // 将基准放置到正确的位置
        swap(arr[i + 1], arr[high]);
        return i + 1;  // 返回基准的最终位置
    }
};

int main() {
    vector<int> arr = {8, 3, 1, 7, 0, 10, 2};  // 初始化待排序数组
    QuickSorter sorter;

    cout << "原数组: ";
    for (int i : arr) cout << i << " ";
    cout << endl;

    sorter.quickSort(arr, 0, arr.size() - 1);  // 调用快速排序

    cout << "快速排序后数组: ";
    for (int i : arr) cout << i << " ";
    cout << endl;

    return 0;
}

代码细节解释：

  1. quickSort()：

    • 这是快速排序的主函数。它通过递归调用，持续地对数组进行划分，并对每一部分分别排序。
    • 参数 low 和 high 指定当前要排序的数组区间。
    • 当 low < high 时，意味着当前区间内有多个元素需要排序，否则直接返回。

  2. partition()：

    • 这是快速排序的核心部分，用于将数组划分为两部分。
    • 选择基准：在这里，我们选择数组最后一个元素 arr[high] 作为基准。
    • 双指针法：i 指针用于标记小于基准的部分，j 指针用于遍历数组。
    • 交换：每当找到小于基准的元素时，将其与 i 位置的元素交换，确保小于基准的元素都位于数组的前半部分。
    • 最后，将基准元素 arr[high] 放到正确的位置 i + 1，并返回这个位置。

  3. 递归调用：

    • quickSort(arr, low, pivotIndex - 1) 对基准左边的部分进行排序。
    • quickSort(arr, pivotIndex + 1, high) 对基准右边的部分进行排序。

快速排序的复杂度分析

  • 时间复杂度：

    • 最好情况：O(n log n)，这是当每次划分都能将数组均匀分割时的情况。
    • 平均情况：O(n log n)，大多数情况下，快速排序的性能接近最好情况。
    • 最坏情况：O(n^2)，这是当数组每次划分极不均匀时的情况，如数组已经有序时。

  • 空间复杂度：

    • 快速排序是原地排序算法，空间复杂度为 O(log n)，这是由于递归调用栈的开销。

快速排序的特点

  • 快：快速排序的平均时间复杂度为 O(n log n)，因此它在大多数情况下比冒泡排序、选择排序、插入排序等效率高得多。
  • 不稳定：快速排序不是稳定的排序算法，因为相同的元素在排序后可能改变相对位置。
  • 分治法：它通过递归不断划分问题，使得复杂问题转化为较小的问题。

适用场景

快速排序适用于大规模数据集，尤其是当对随机数据进行排序时，它的效率非常高。然而，对于小数据集或几乎有序的数据集，插入排序等可能更为高效。

归并排序

归并排序（Merge Sort）也是一种基于分治法（Divide and Conquer）的高效排序算法。它通过将数组逐步划分成更小的子数组，然后将这些子数组排序并合并，最终得到有序的数组。归并排序的时间复杂度为 O(n log n)，且是一种稳定排序，即相等的元素在排序后保持相对顺序不变。

归并排序的步骤

  1. 分割数组：

    • 将数组从中间一分为二，递归地将每个子数组再一分为二，直到每个子数组中只有一个元素（因为单个元素自然是有序的）。

  2. 合并数组：

    • 递归到最小子数组后，开始合并。从每个子数组中选择最小的元素，合并成有序的数组，逐步返回到上一层，最终将整个数组合并成一个有序的数组。

归并排序的示例

假设我们要对数组 [38, 27, 43, 3, 9, 82, 10] 进行排序，归并排序的过程如下：

  1. 分割数组：

    • 首先将数组分为两半：[38, 27, 43] 和 [3, 9, 82, 10]。
    • 继续将每一半再分为两部分，直到每个部分只包含一个元素：
      • [38, 27, 43] 分为 [38] 和 [27, 43]，再分为 [27] 和 [43]。
      • [3, 9, 82, 10] 分为 [3, 9] 和 [82, 10]，再分为 [3] 和 [9]，以及 [82] 和 [10]。

  2. 合并排序：

    • 从最小的子数组开始合并：
      • [27] 和 [43] 合并为 [27, 43]。
      • [38] 和 [27, 43] 合并为 [27, 38, 43]。
      • [3] 和 [9] 合并为 [3, 9]，[82] 和 [10] 合并为 [10, 82]。
      • [3, 9] 和 [10, 82] 合并为 [3, 9, 10, 82]。
    • 最后，将两部分 [27, 38, 43] 和 [3, 9, 10, 82] 合并为最终的有序数组 [3, 9, 10, 27, 38, 43, 82]。
#include <iostream>
#include <vector>
using namespace std;

class MergeSorter {
public:
    // 归并排序的主函数
    void mergeSort(vector<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);
        }
    }

private:
    // 合并函数，用于合并两个有序的子数组
    void merge(vector<int>& arr, int left, int mid, int right) {
        int n1 = mid - left + 1;  // 左半部分的长度
        int n2 = right - mid;     // 右半部分的长度

        // 创建临时数组用于存放两个子数组
        vector<int> L(n1), R(n2);

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

        // 归并两个有序子数组
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 复制左边剩余的元素
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // 复制右边剩余的元素
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
};

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};  // 初始化待排序数组
    MergeSorter sorter;

    cout << "原数组: ";
    for (int i : arr) cout << i << " ";
    cout << endl;

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

    cout << "归并排序后数组: ";
    for (int i : arr) cout << i << " ";
    cout << endl;

    return 0;
}

代码细节解释：

  1. mergeSort()：

    • 这是归并排序的主函数。它通过递归将数组划分为两个部分，然后递归地对每个部分进行排序。
    • 参数 left 和 right 指定当前需要排序的数组区间。
    • 当 left < right 时，继续递归分割数组；当 left == right 时，数组中只有一个元素，不需要再分割。

  2. merge()：

    • 这是归并排序的核心部分，用于合并两个有序的子数组。
    • 临时数组：我们使用两个临时数组 L 和 R 分别存储待合并的左右两部分数据。
    • 归并操作：使用两个指针 i 和 j 分别遍历左半部分 L 和右半部分 R，将较小的元素复制回原数组 arr。
    • 处理剩余元素：当其中一个数组的所有元素都已经合并到 arr 中时，剩余的部分直接复制到 arr。

  3. 递归调用：

    • mergeSort(arr, left, mid) 对数组的左半部分进行排序。
    • mergeSort(arr, mid + 1, right) 对数组的右半部分进行排序。
    • 最后，使用 merge() 将已经排序的左右两部分合并。

归并排序的复杂度分析

  • 时间复杂度：
    • 归并排序的时间复杂度为 O(n log n)，其中 n 是数组长度，log n 是由于递归将数组分成两半的次数，n 是每次合并时的比较和复制操作。
  • 空间复杂度：
    • 归并排序需要 O(n) 的辅助空间，因为在合并时需要创建临时数组来存储左右两部分数据。

归并排序的特点

  • 稳定性：归并排序是稳定的排序算法，即相等的元素在排序后依然保持它们的相对顺序。
  • 适用于大规模数据：由于其时间复杂度为 O(n log n)，归并排序适用于大规模数据的排序任务。
  • 额外空间：归并排序需要额外的存储空间来进行合并操作，相比快速排序，空间开销较大，因此在空间敏感的场景中可能不如快速排序合适。

归并排序的应用场景

  • 需要稳定排序的场景：如果在排序过程中需要保持相等元素的相对顺序，归并排序是不错的选择。
  • 链表排序：归并排序由于不需要随机访问数据，因此在链表等数据结构上表现非常好，不需要额外的空间来合并节点。
  • 大数据集：适合用于大规模数据集的排序。

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

相关文章：

  • Java集合(Collection+Map)
  • 什么是项目完整性管理？
  • PCA 原理推导
  • SpringCloud基础 入门级 学习SpringCloud 超详细（简单通俗易懂）
  • Ubuntu24.04上安装和配置MariaDB
  • 大模型研究报告 | 2024年中国金融大模型产业发展洞察报告｜附34页PDF文件下载
  • 经济不好，但是遍地都是赚钱的机会
  • 万元购车平台源码开发总结与关键技术解析
  • 如何应对“.DevicData-C-XXXXXXXX”勒索病毒：建议与防范措施
  • fiddler抓包12_篡改请求（请求前断点）
  • *C++:list
  • 【C语言零基础入门篇 - 17】：排序算法
  • ubuntu系统下，c++图形库Matplot++配置
  • 深度学习(3):Tensor和Optimizer
  • 求职Leetcode题目（11）
  • 如何使用C语言接入Doris数据库
  • 线性表二——栈stack
  • 微信小程序开发系列之-在微信小程序中使用云开发
  • How to install JetBrains ToolBox in Ubuntu 22.04 LTS?
  • ELK-03-skywalking监控linux系统
  • JAVA JDK华为云镜像下载，速度很快
  • AIGC入门：Comfyui整合包，解压即用！
  • Goweb---Gorm操作数据库(二)
  • project_object_model_3d
  • ES6中迭代器与生成器知识浅析
  • Python知识点：如何使用Python与.NET进行互操作（IronPython）