【C++】十大排序算法之 冒泡排序 & 选择排序

���次介绍内容参考自：十大经典排序算法（C++实现） - fengMisaka - 博客园 (cnblogs.com)

排序算法是《数据结构与算法》中最基本的算法之一。

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，时间复杂度为 O(nlogn)～O(n²)。
• 非比较类排序：不通过比较来决定元素间的相对次序，其时间复杂度可以突破 O(nlogn)，以线性时间运行。

  【十大经典排序算法分类】

  【十大经典排序算法的复杂度分析】

  名词解释：

  • 时间/空间复杂度：描述一个算法执行时间/占用空间与数据规模的增长关系。

  • n：待排序列的个数。

  • k：“桶”的个数（上面的三种非比较类排序都是基于“桶”的思想实现的）。

  • In-place：原地算法，指的是占用常量内存，不占用额外内存。即空间复杂度为 O(1) 。

  • Out-place：非原地算法，占用额外内存。

  • 稳定性：假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。

    ---

    ---

    一、冒泡排序（Bubble Sort）

            顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。

    1.1、算法描述

    • 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；
    • 从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；
    • 重复从左到后比较，而前一轮中得到的最后一个元素不参与比较，得出新一轮的最大元素；
    • 按照上述规则，每一轮结束会减少一个元素参与比较，直到没有任何一组元素需要比较。

      1.2、动图演示

      冒泡排序动图演示

      ---

      1.3、C++编码

      /*** @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved* @file BubbleSort.hpp* @brief 冒泡排序* @autor 写代码的小恐龙er* @date 2024/03/02*/// 交换宏#define swap(x,y) x=x+y,y=x-y,x=x-yvoid BubbleSort(int arr[], int n){bool bExchange = false; // 交换标志for (int i = 0; i  arr[j + 1]){swap(arr[j + 1], arr[j]);bExchange = true; // 发生了交换，故将交换标志置为真}}if (!bExchange) // 考虑有一趟排序未发生交换的理想情况，可以提前终止算法return;}}

      ---

      1.4 、算法分析

              冒泡排序属于交换排序，是稳定排序，平均时间复杂度为 O(n²)，空间复杂度为 O(1)。但是我们常看到冒泡排序的最优时间复杂度是 O(n)，那要如何优化呢？上面就是优化后的代码，用了一个 bExchange 参数记录新一轮的排序中元素是否做过交换，如果没有，说明前面参与比较过的元素已经是正序，那就没必要再从头比较了，就可以优化到 O(n) 。

      ---

      ---

      二、选择排序（Selection Sort）

              选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想就是，每一趟n - i + 1(i=1,2,…,n-1)个记录中选取值最小的索引作为有序序列的第 i 个索引。

      2.1 、算法描述

      • 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置;
      • 在剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾;
      • 重复步骤 2，直到所有元素排序完毕。

        2.2 、动图演示

        选择排序动图演示

        ---

        2.3、C++编码

        /*** @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved* @file SelectSort.hpp* @brief 选择排序* @autor 写代码的小恐龙er* @date 2024/03/02*/void SelectSort(int* arr, int n){int minIndex = 0;int temp;for (int i = 0; i  
        2.4 、算法分析
         
                选择排序是不稳定排序，时间复杂度固定为 O(n²)，因此它不适用于数据规模较大的序列。不过它也有优点，就是不占用额外的内存空间。