排序

一、什么是排序？

在计算机里，排序的意思就是把一堆杂乱无章的数据，整理得整整齐齐、有条有理 。这是计算机在处理各种问题时，常常要做的一项工作。

打个比方，就好像你有一堆打乱顺序的纸牌，排序就是要按照一定的规则，比如从大到小或者从小到大，把这些纸牌重新整理好。

而排序算法呢，就是具体用来整理这堆数据的方法，它规定了按照什么样的特定方式，去把那些杂乱的数据变得有序。就好比整理纸牌时，你可以一张一张地比较大小，然后把它们摆好，这就是一种整理纸牌的 “算法” 。

二、为什么要排序？

排序在生活和计算机领域都非常有用，比如：

在生活中

• 找东西方便

  想象一下，你的书架上的书乱七八糟的，你想找一本《西游记》，可能得翻遍整个书架才能找到。但如果书架上的书是按书名的字母顺序排好的，你只需要找到“X”开头的那部分，很快就能找到《西游记》。这就是排序的好处，让找东西变得简单快捷。

• 节省时间

  你的衣柜里衣服乱成一团，找一件白色的T恤可能得花好几分钟。但如果衣服是按颜色和类型排好的，你直接去白色T恤的区域，一下子就能找到。这样就能节省很多时间，尤其是早上赶时间的时候。

• 看起来更整洁

  一个整齐的书架或者衣柜，看起来会让人感觉很舒服。东西摆放得整整齐齐，不仅看起来美观，还能让人心情舒畅。就像一个干净整洁的房间，让人感觉很舒服一样。

• 方便管理

  超市的货架如果没有排序，顾客找东西会很麻烦，店员管理起来也会很困难。但如果货架上的商品是按类别和品牌排好的，顾客能快速找到自己想要的东西，店员补货和整理也更方便。

在计算机领域

• 快速查找数据

  想象一下，你有一个很大的文件夹，里面有成千上万的文件。如果你想找到一个特定的文件，如果没有排序，可能得一个个翻找。但如果文件是按名字或者日期排好的，你就可以很快找到你需要的文件。计算机也是一样，排序可以让计算机更快地找到需要的数据。

• 提高效率

  搜索引擎要从海量的网页中找到最相关的网页给你。如果没有排序，可能得花很长时间才能找到合适的网页。但通过排序，搜索引擎可以很快地把最相关的网页排在前面，让你能快速找到需要的信息。

• 方便处理数据

  数据库里存储了大量的数据，比如订单信息。如果没有排序，处理这些数据会很麻烦。但如果订单是按日期或者金额排好的，处理起来就会更方便。比如，你想统计最近一个月的订单，排序后的数据可以让你快速找到这些订单。

• 提升用户体验

  在电商网站上，商品如果没有排序，用户很难找到自己想要的东西。但如果商品是按销量、价格或者评价排好的，用户可以很快找到自己想要的商品，购物体验就会更好。

排序就像是给东西排排队，让它们变得有条理。在生活中，排序可以帮助我们更快地找到东西，节省时间，让环境看起来更整洁，方便管理。在计算机领域，排序可以让计算机更快地处理数据，提高效率，提升用户体验。总之，排序是为了让事情变得更简单、更高效。

三、在计算机中有哪些排序算法？

在计算机中排序的方法分为以下几种类型：内部排序、外部排序、比较排序、非比较排序、稳定排序、不稳定排序、递归排序、非递归排序。

我们这里主要学习比较排序和非比较排序

3.1 冒泡排序

1.基本思想

冒泡排序的基本思想是基于相邻元素的比较和交换 ，通过多次重复比较相邻元素并交换位置，使值较大（或较小）的元素逐渐 “冒泡” 到数组的末尾（或开头），从而实现数组的排序。

2.算法描述

• 从序列的第一个元素开始，比较相邻的两个元素。

• 如果第一个元素小于第二个元素，则交换它们的位置。

• 继续比较下一对相邻元素，重复上述操作，直到遍历完序列。

• 重复上述过程，但每次遍历时，序列的末尾部分已经有序，因此可以减少比较的范围。

• 当完成所有遍历时，序列将变得有序。

3.动画演示

4.实现过程

• 从序列的第一个元素开始，比较相邻的两个元素。

  1
          a[ i ] > a[ i+1 ];
  

• 如果第一个元素大于第二个元素，则交换它们的位置。

  xxxxxxxxxx
  3
  1
  if ( a[i] > a[i+1] ){
  2
      swap(a[i],a[i+1]);
  3
  }
  

• 继续比较下一对相邻元素，重复上述操作，直到遍历完序列。

  xxxxxxxxxx
  5
  1
  for(int i = 1; i <= n - 1;i++){//一轮比较，最大值到最后
  2
      if ( a[i] > a[i+1] ){
  3
          swap(a[i],a[i+1]);
  4
      }
  5
  }
  

• 重复上述过程，但每次遍历时，序列的末尾部分已经有序，因此可以减少比较的范围 j<=n-i;。

  xxxxxxxxxx
  9
  1
  //n-1轮比较，最大值向后移动
  2
  for(int i = 1; i <= n - 1; i++){
  3
      //每轮比较后，序列长度减小j<=n-i不再比较上一轮的最大值
  4
      for(int j = 1; j <= n-i; j++){
  5
          if (a[i] > a[i+1]){
  6
              swap(a[i],a[i+1]);
  7
          }
  8
      }  
  9
  }
  

5.代码示例：

题目1：基本冒泡排序

题目描述：给定一个整数数组，使用冒泡排序算法对其进行排序，并输出排序后的数组。 输入： • 第一行是一个整数 n ，表示数组的长度（ 1 ≤ n ≤ 1000 ）。 • 第二行是 n 个整数，表示待排序的数组。 输出： • 输出排序后的数组，每个元素之间用空格隔开。 示例输入： 7 64 34 25 12 22 11 90 示例输出： 11 12 22 25 34 64 90

参考代码：

​x
1
#include <iostream>
2
using namespace std;
3
int main() {
4
    int n;
5
    cin >> n;
6
    int arr[1000];
7
    for (int i = 0; i < n; ++i)
8
        cin >> arr[i];
9

10
    for (int i = 0; i < n - 1; ++i) {
11
        for (int j = 0; j < n - i - 1; ++j) {
12
            if (arr[j] > arr[j + 1]) {
13
                swap(arr[j], arr[j + 1]);
14
            }
15
        }
16
    }
17

18
    for (int i = 0; i < n; ++i)
19
        cout << arr[i] << " ";
20
    cout << endl;
21
    return 0;
22
}
23

题目2：优化冒泡排序

题目描述：给定一个整数数组，使用优化后的冒泡排序算法对其进行排序。优化后的冒泡排序在某一轮中如果没有发生任何交换，则提前结束排序。输出排序后的数组以及实际进行的排序轮数。 输入： • 第一行是一个整数 n ，表示数组的长度（ 1 ≤ n ≤ 1000 ）。 • 第二行是 n 个整数，表示待排序的数组。 输出： • 第一行输出排序后的数组，每个元素之间用空格隔开。 • 第二行输出实际进行的排序轮数。 示例输入： 7 64 34 25 12 22 11 90 示例输出： 11 12 22 25 34 64 90 6

参考代码：

xxxxxxxxxx
28
1
#include <iostream>
2
using namespace std;
3
int main() {
4
    int n;
5
    cin >> n;
6
    int arr[1000];
7
    for (int i = 0; i < n; ++i)
8
        cin >> arr[i];
9

10
    int cnt = 0;
11
    for (int i = 0; i < n - 1; ++i) {
12
        bool f = false;
13
        for (int j = 0; j < n - i - 1; ++j) {
14
            if (arr[j] > arr[j + 1]) {
15
                swap(arr[j], arr[j + 1]);
16
                f = true;
17
            }
18
        }
19
        if (!f) break;
20
        cnt++;
21
    }
22

23
    for (int i = 0; i < n; ++i)
24
        cout << arr[i] << " ";
25
    cout << endl << cnt;
26
    return 0;
27
}
28

3.2 选择排序

1.基本思想

选择排序是从待排序的区间中选出最小（或最大）元素，并将该元素与该区间的第1个元素交换位置。这样通过n-1次选择未排序部分的最小（或最大）元素，将其放在正确位置从而达到对整个序列进行排序的效果。

选择排序的做法是这样的：在那堆等着被排序的数里面，每次都挑出最小（要是想从大到小排，就挑最大）的那个数，然后把这个挑出来的数和这堆数最前面的那个数交换一下位置。

就这样，一次又一次地从还没排好序的那些数里找最小（或最大）的数，一共找 n−1 次（这里的 n 是这堆数的总数）。每找一次，就把找到的最小（或最大）数放到它该在的位置上。经过这么多次操作后，这整个数列就排好序啦。

2.算法描述（以升充为例）

• 初始状态：假设有一个包含 n 个元素的数组 arr，整个数组被分为两个部分，左边是已排序部分（初始为空），右边是未排序部分（即整个数组）。

• 第一轮选择：

  • 从数组的第一个元素开始，遍历整个未排序部分，找出其中最小的元素。

  • 将找到的最小元素与未排序部分的第一个元素交换位置。此时，已排序部分增加了一个元素（即刚交换过来的最小元素），未排序部分减少了一个元素。

• 第二轮选择：

  • 在剩下的未排序部分（即数组中除了已排序部分的元素）中，再次找出最小元素。

  • 将这个最小元素与未排序部分的第一个元素交换位置。这样，已排序部分又增加了一个元素，未排序部分继续减少一个元素。

• 重复上述过程：重复进行选择最小元素并交换的操作，直到未排序部分只剩下一个元素（此时整个数组已经有序）。总共需要进行 (n - 1) 轮操作，因为当只剩下一个元素时，它自然就是有序的。

3.动画演示

4.实现过程

• 假设我们有一个数组 arr = [5, 3, 4, 2, 1]。初始时，整个数组都是未排序部分。

• 第一轮：选择未排序部分中最小值1，与第一个元素交换，得到： 1,[3, 4, 2, 5] 括号内为未排序部分，1为已排序部分。

• 第二轮： 1, 2, [3, 4, 5]

• 第三轮： 1, 2, 3, [4, 5]

• 第四轮： 1, 2, 3, 4, [5]

• 剩下一个元素时就不用再排序（此时整个数组已经有序）。

5.代码示例

核心代码：

xxxxxxxxxx
12
1
for (int i = 0; i < n - 1; ++i) {  // 外层循环控制排序轮数
2
        int pos = i;  // 假设当前轮次的最小元素索引为i
3
        // 内层循环从未排序部分找到最小元素
4
        for (int j = i + 1; j < n; ++j) {  
5
            if (arr[j] < arr[minIndex]) {
6
                pos = j;  // 更新最小元素索引
7
            }
8
        }
9
        if (pos != i) {  // 如果最小元素不是当前第一个元素
10
            swap(arr[i], arr[pos]);  // 交换元素
11
        }
12
    }

题目1：基本选择排序 题目描述：给定一个整数数组，使用选择排序算法对其进行排序，并输出排序后的结果。 输入： • 第一行是一个整数 n ，表示数组的长度（ 1 ≤ n ≤ 1000 ）。 • 第二行是 n 个整数，表示待排序的数组。 输出： • 输出排序后的数组，每个元素之间用空格隔开。

参考代码：

xxxxxxxxxx
30
1
#include <iostream>
2
using namespace std;
3

4
int main() {
5
    int n;
6
    cin >> n;
7
    int arr[1000];
8
    for (int i = 0; i < n; ++i) {
9
        cin >> arr[i];
10
    }
11

12
    for (int i = 0; i < n - 1; ++i) {//外层循环控制排序轮数
13
        int pos = i;  // 假设当前轮次的最小元素下标为i
14
        // 内层循环从未排序部分找到最小元素
15
        for (int j = i + 1; j < n; ++j) {  
16
            if (arr[j] < arr[pos]) {// 如果找到更小的元素
17
                pos = j;  // 更新最小元素下标
18
            }
19
        }
20
        if (pos != i) {  // 如果最小元素不是当前第一个元素
21
            swap(arr[i], arr[pos]);  // 交换元素
22
        }
23
    }
24

25
    for (int i = 0; i < n; ++i) {
26
        cout << arr[i] << " ";
27
    }
28
    return 0;
29
}
30

3.3 插入排序

1.基本思想

将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增加1的有序表。类似于整理扑克牌的过程，假设手中已经有一部分牌是按顺序排列好的，每次从剩余未整理的牌中拿起一张，然后将其插入到已排好序的牌中的合适位置，使得插入后的牌仍然保持有序。

2.算法描述

1. 初始化：

   • 将数组分为两部分：已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，未排序部分为剩下的元素。

2. 插入过程：

   • 从未排序部分取出第一个元素（称为待插入元素）。

   • 在已排序部分从后向前查找，找到待插入元素的合适位置。

   • 将已排序部分中所有比待插入元素大的元素向后移动一位，为待插入元素腾出空间。

   • 将待插入元素插入到找到的位置。

3. 重复上述过程：

   • 重复上述步骤，直到未排序部分为空，整个数组有序。

3.动画演示

4.实现过程

假设我们有一个数组 arr ，长度为 n ，下面是插入排序的详细实现过程：

1. 外层循环：控制排序的轮数，从第二个元素开始，到第 n 个元素。

2. 内层循环：在每一轮中，从未排序部分取出第一个元素，然后在已排序部分从后向前查找合适的位置。

3. 移动元素：将已排序部分中所有比待插入元素大的元素向后移动一位。

4. 插入元素：将待插入元素插入到找到的位置。

5.代码示例

核心代码：

xxxxxxxxxx
9
1
for (int i = 1; i < n; ++i) {  // 外层循环控制排序轮数
2
    int t = arr[i];  // 待插入元素
3
    int j = i - 1;  // 已排序部分的最后一个元素索引
4
    while(j>=0&&arr[j]>t){// 在已排序部分从后向前查找合适位置
5
        arr[j + 1] = arr[j];  // 向后移动元素
6
        j --;
7
    }
8
    arr[j + 1] = t;  // 插入待插入元素
9
}

题目1：基本插入排序 题目描述：给定一个整数数组，使用插入排序算法对其进行排序，并输出排序后的结果。 输入： • 第一行是一个整数 n ，表示数组的长度（ 1 ≤ n ≤ 1000 ）。 • 第二行是 n 个整数，表示待排序的数组。 输出： • 输出排序后的数组，每个元素之间用空格隔开。

参考代码：

xxxxxxxxxx
29
1
#include <iostream>
2
using namespace std;
3

4
int main() {
5
    int n; 
6
    cin >> n;
7
    int arr[1000]; 
8
    // 输入数组的每个元素
9
    for (int i = 0; i < n; ++i) { 
10
        cin >> arr[i];
11
    }
12
    // 插入排序算法的实现
13
    for (int i = 1; i < n; ++i) { // 从第二个元素开始遍历数组
14
        int t = arr[i]; // 将当前元素存储在变量t中
15
        int j = i - 1; // 设置j为当前元素的前一个元素的索引
16
        // 将所有大于t的元素向后移动一个位置
17
        while (j >= 0 && arr[j] > t) {
18
            arr[j + 1] = arr[j]; // 将arr[j]向后移动
19
            j--; // 将j向前移动
20
        }
21
        arr[j + 1] = t; // 将t插入到正确的位置
22
    }
23
    // 输出排序后的数组
24
    for (int i = 0; i < n; ++i) {
25
        cout << arr[i] << " ";
26
    }
27
    return 0;
28
}
29

3.4 计数排序

1.基本思想

计数排序是一种非比较类排序算法，基本思想是利用数组下标来统计元素出现的次数，从而实现排序。它适用于知道待排序数据范围且数据范围相对较小的情况。

具体来说，先找出待排序数组中的最大值和最小值，确定计数数组的大小。然后遍历待排序数组，以数组元素的值为索引，在计数数组的对应位置记录该元素出现的次数。最后，根据计数数组，将元素按顺序放回原数组或新数组，完成排序。计数排序的核心在于“计数”和“定位”。

2.算法描述

1. 确定范围：

   • 找出待排序数组中的最大值和最小值，确定数组的范围。

2. 初始化计数数组：

   • 创建一个大小为 k 的计数数组（ count ），其中 k 是最大值与最小值的差加1。初始化计数数组的所有元素为0。

3. 统计每个元素的出现次数：

   • 遍历待排序数组，对于每个元素，将其在计数数组中对应位置的值加1。这一步记录了每个元素在待排序数组中出现的次数。

4. 生成有序数组

   • 创建一个新的数组（也可以在原数组上覆盖）用于存储排序后的结果。从计数数组的第一个元素开始遍历，对于计数数组中的每个非零元素 ，将计数数组下标按其值的次数依次放入结果数组中。这样，结果数组就是按升序排列的。

3.动画演示

4.实现过程

假设有一个数组 arr = {4, 2, 2, 5, 3, 3, 1} ，计数排序过程：

• 确定范围：1-5

• 创建并初始化计数数组cnt：创建大小为6的数组cnt，初始化为0

• 遍历待排序数组arr，统计每个元素出现的次数：cnt={0,1,2,2,1,1}

• 遍历cnt数组，按元素的值大小输出多次cnt[i]下标：1,2,2,3,3,4,5

5.代码示例

题目1：基本计数排序 题目描述：给定一个整数数组，使用计数排序算法对其进行排序，并输出排序后的结果。 输入： • 第一行是一个整数 n ，表示数组的长度（ 1 ≤ n ≤ 1000 ）。 • 第二行是 n 个整数，表示待排序的数组。数组中的每个元素都在 0 到 100 之间。 输出： • 输出排序后的数组，每个元素之间用空格隔开。

参考代码：

xxxxxxxxxx
23
1
#include <iostream>
2
using namespace std;
3

4
int main() {
5
    int n;
6
    cin >> n;
7
    int arr[1000];
8
    for (int i = 0; i < n; ++i) {
9
        cin >> arr[i];
10
    }
11
//计数
12
    int cnt[101] = {0};
13
    for (int i = 0; i < n; ++i) {
14
        cnt[arr[i]]++;
15
    }
16
//输出
17
    for (int i = 0; i < 101; ++i) {
18
        for(int j = 0; j<cnt[i]; ++j){
19
            cout<< i << " ";
20
        }
21
    }
22
    return 0;
23
}

以下排序算法为提高级内容

3.5 归并排序

3.5.1 基本思想：分治与递归

• 归并排序基于分治思想，将一个大问题分解为多个小问题，分别解决小问题后再将结果合并起来。

• 对于一个待排序的数组，归并排序先把数组从中间分成两个子数组，然后对这两个子数组分别进行排序，最后将两个已排序的子数组合并成一个有序的数组。这个过程不断递归进行，直到每个子数组只有一个元素（一个元素的数组自然是有序的）。通过这种方式，最终将整个数组排序。

3.5.2 算法描述

1. 分解：

   • 找到数组的中间位置 mid，将数组 arr 分成两个子数组，即左子数组 left 从 arr[0] 到 arr[mid]，右子数组 right 从 arr[mid + 1] 到 arr[n - 1]，其中 n 是数组 arr 的长度。

   • 对左子数组和右子数组分别递归调用归并排序函数，持续分解子数组，直到子数组长度为 1。

2. 合并：

   • 当子数组长度为 1 时，开始进行合并。准备两个指针，分别指向左子数组和右子数组的起始位置。

   • 创建一个临时数组 temp 用于存储合并后的结果。比较两个子数组当前指针指向的元素，将较小（或较大，取决于排序顺序，这里以升序为例）的元素放入 temp 数组，并将对应子数组的指针后移一位。

   • 重复上述比较和放入的操作，直到其中一个子数组的元素全部放入 temp 数组。

   • 将另一个子数组剩余的元素直接复制到 temp 数组的末尾。

   • 最后，将 temp 数组中的内容复制回原数组 arr 对应的位置，完成一次合并。随着递归的返回，不断进行合并操作，最终整个数组有序。

3.5.3 动画演示

3.5.4 实现过程

归并排序主要分为两个大的阶段：分解阶段和合并阶段。

1. 分解阶段

   • 步骤一：确定分解点

     • 对于给定的待排序数组 arr，首先计算数组的中间位置 mid。例如，数组长度为 n，则 mid = left + (right - left) / 2，其中 left 是数组起始索引，初始为 0，right 是数组末尾索引，初始为 n - 1。这个计算方式可以避免 left + right 可能产生的溢出问题。

   • 步骤二：递归分解

     • 以 mid 为界，将数组分为左子数组 arr[left...mid] 和右子数组 arr[mid + 1...right]。然后对左子数组和右子数组分别递归调用归并排序函数。这意味着每个子数组又会经历同样的分解过程，不断将子数组一分为二，直到子数组的长度为 1。因为长度为 1 的数组天然是有序的，所以分解的递归过程到这里结束。

     • 例如，对于数组 [12, 11, 13, 5, 6, 7]，初始时 left = 0，right = 5，mid = 2。左子数组为 [12, 11, 13]，右子数组为 [5, 6, 7]。接着对 [12, 11, 13] 继续分解，mid = 1，左子数组变为 [12]，右子数组变为 [11, 13]，以此类推，直到每个子数组只有一个元素。

2. 合并阶段

   • 步骤一：初始化临时数组和指针

     • 当子数组长度为 1 时，开始进行合并。对于要合并的两个子数组（假设左子数组为 leftSub，右子数组为 rightSub），先创建一个临时数组 temp 来存储合并后的结果。同时，初始化两个指针，一个指向左子数组的起始位置（设为 i），另一个指向右子数组的起始位置（设为 j），还需要一个指针（设为 k）指向临时数组 temp 要填充的起始位置。

   • 步骤二：比较与填充

     • 比较两个子数组当前指针指向的元素。如果左子数组当前元素小于等于右子数组当前元素（以升序排序为例），则将左子数组当前元素放入临时数组 temp 中，并将左子数组指针 i 后移一位；否则，将右子数组当前元素放入 temp 中，并将右子数组指针 j 后移一位。然后将 temp 数组的指针 k 后移一位。

     • 例如，假设左子数组 leftSub = [11, 13]，右子数组 rightSub = [5, 6, 7]。首先比较 11 和 5，因为 5 < 11，所以将 5 放入 temp 数组，j 后移指向 6，k 后移。接着比较 11 和 6，因为 6 < 11，将 6 放入 temp 数组，j 后移指向 7，k 后移。再比较 11 和 7，因为 7 < 11，将 7 放入 temp 数组，j 后移，此时右子数组遍历完。

   • 步骤三：处理剩余元素

     • 当其中一个子数组的元素全部放入 temp 数组后，另一个子数组可能还有剩余元素。直接将剩余元素依次复制到 temp 数组的末尾。例如上述例子中，左子数组 [11, 13] 还有 11 和 13 未放入 temp，将它们依次放入，此时 temp 数组为 [5, 6, 7, 11, 13]。

   • 步骤四：复制回原数组

     • 最后，将临时数组 temp 中的内容复制回原数组 arr 对应的位置，完成一次合并。随着递归的返回，不断进行这样的合并操作，最终整个数组有序。例如，将 [5, 6, 7, 11, 13] 复制回原数组中对应左右子数组的位置，逐步将整个数组排序。

3.5.5 示例

xxxxxxxxxx
41
1
#include <iostream>
2
using namespace std;
3

4
void mergeSort(int arr[], int left, int right) {
5
    if(left==right)return;
6
    int mid=left+(right-left)/2;
7
    //递归拆分左右两半元素，直到left==right只剩一个元素
8
    mergeSort(arr,left,mid);//拆分左边
9
    mergeSort(arr,mid+1,right);//拆右边
10
    //上边递归拆分完后，按元素大小进行合并
11
    //说明：函数的递归调用会保留调用时的状态，所以在返回时
12
    //  返回的数组是分为左右两半有序子序列。
13
    //  这里的处理方法：
14
    //  复制左右两半到两个数组来处理合并
15
    int n1=mid-left+1,n2=right-mid;
16
    int L[n1],R[n2];//创建左右两个子数组
17
    //复制arr数组左右两半到子数组。
18
    for(int i=0;i<n1;i++)L[i]=arr[left+i];
19
    for(int i=0;i<n2;i++)R[i]=arr[mid+1+i];
20
    //复制完后就可以把L、R两个数组的元素按大小顺序写回arr数组
21
    int i=0,j=0,k=left;
22
    //两个数组都有数据时
23
    while(i<n1&&j<n2)arr[k++]=(L[i]<=R[j])?L[i++]:R[j++];
24
    //只剩一个数组有数据时
25
    while(i<n1)arr[k++]=L[i++];
26
    while(j<n2)arr[k++]=R[j++];
27
}
28

29
int main() {
30
    int n;
31
    cin >> n;
32
    int arr[1000];
33
    for (int i = 0; i < n; ++i) {
34
        cin >> arr[i];
35
    }
36
    mergeSort(arr, 0, n - 1); // 对整个数组进行归并排序
37
    for (int i = 0; i < n; ++i) {
38
        cout << arr[i] << " "; // 输出排序后的数组
39
    }
40
    return 0;
41
}

3.6 快速排序

1.基本思想：分治与递归

• 快速排序基于分治思想，通过选择一个基准元素（pivot），将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。然后分别对左右两部分递归地进行快速排序，最终使整个数组有序。这种方式就像是把一堆杂乱的数字分成两拨，一拨是比某个数小的，另一拨是比这个数大的，然后再分别整理这两拨数字，直到所有数字都排好序。

2.算法描述

• 选择基准元素：从数组中选择一个元素作为基准元素。常见的选择方式有选择数组的第一个元素、最后一个元素或者中间元素等。这里以选择第一个元素作为基准元素为例。

• 划分操作：

  • 定义两个指针，一个 left 指向数组起始位置（除基准元素外），一个 right 指向数组末尾位置。

  • 从 right 指针开始，向左移动，找到第一个小于基准元素的元素；然后从 left 指针开始，向右移动，找到第一个大于基准元素的元素。

  • 交换这两个找到的元素位置。

  • 重复上述移动指针和交换元素的操作，直到 left 指针超过 right 指针。

  • 最后，将基准元素与 right 指针指向的元素交换位置。此时，数组被分为两部分，左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。

• 递归排序：对左右两部分分别递归调用快速排序函数，重复上述选择基准元素、划分操作和递归排序的过程，直到每个子数组的长度为 1 或 0（长度为 1 或 0 的数组自然是有序的）。

3.动画演示

4.实现过程

• 以数组 [6, 8, 1, 4, 3, 9, 5, 4, 11, 2] 为例，假设选择第一个元素 6 作为基准元素。

• 第一轮划分：

  • 初始化 left = 1，right = 9。

  • right 指针向左移动，找到 2 小于 6，left 指针向右移动，找到 8 大于 6，交换 2 和 8，数组变为 [6, 2, 1, 4, 3, 9, 5, 4, 11, 8]。

  • 继续移动指针，right 找到 4 小于 6，left 找到 9 大于 6，交换 4 和 9，数组变为 [6, 2, 1, 4, 3, 4, 5, 9, 11, 8]。

  • 继续移动，right 找到 3 小于 6，left 找到 5 大于 6，交换 3 和 5，数组变为 [6, 2, 1, 4, 5, 4, 3, 9, 11, 8]。

  • 继续移动，right 找到 4 小于 6，left 找到 9 大于 6，交换 4 和 9，数组变为 [6, 2, 1, 4, 5, 4, 3, 9, 11, 8]。

  • 当 left 超过 right 时，交换基准元素 6 和 right 指向的元素 4，数组变为 [4, 2, 1, 4, 3, 5, 6, 9, 11, 8]。此时，数组被划分为 [4, 2, 1, 4, 3, 5] 和 [9, 11, 8] 两部分。

• 递归排序：

  • 对左边部分 [4, 2, 1, 4, 3, 5] 重复上述过程，选择 4 作为基准元素，经过划分后变为 [3, 2, 1, 4, 4, 5]，再对 [3, 2, 1] 和 [4, 5] 递归排序，最终左边部分有序为 [1, 2, 3, 4, 4, 5]。

  • 对右边部分 [9, 11, 8] 重复上述过程，选择 9 作为基准元素，经过划分后变为 [8, 9, 11]，最终右边部分有序为 [8, 9, 11]。

• 整个数组最终变为 [1, 2, 3, 4, 4, 5, 6, 8, 9, 11]，完成排序。

5.示例

xxxxxxxxxx
36
1
#include <iostream>
2
using namespace std;
3

4
void quickSort(int arr[], int low, int high) {
5
    if (low < high) {
6
        int pivot = arr[low];// 选择第一个元素作为基准
7
        int i = low + 1; // i 是较大元素的索引
8
        // 分区操作
9
        for (int j = i; j <= high; j++) {
10
            if (arr[j] < pivot) {
11
                swap(arr[i], arr[j]);
12
                i++;
13
            }
14
        }
15
        swap(arr[low], arr[i - 1]); // 将基准放到正确的位置
16
        int pi = i - 1; // 返回基准的最终位置
17
        // 递归地对基准左边和右边的子数组进行排序
18
        quickSort(arr, low, pi - 1); // 对基准左边的子数组排序
19
        quickSort(arr, pi + 1, high); // 对基准右边的子数组排序
20
    }
21
}
22

23
int main() {
24
    int n;
25
    cin >> n;
26
    int arr[1000];
27
    for (int i = 0; i < n; ++i) {
28
        cin >> arr[i];
29
    }
30
    quickSort(arr, 0, n - 1); // 对整个数组进行快速排序
31
    for (int i = 0; i < n; ++i) {
32
        cout << arr[i] << " "; // 输出排序后的数组
33
    }
34
    return 0;
35
}
36

3.7 堆排序

1.基本思想

• 堆排序基于堆这种数据结构。堆是一种完全二叉树，分为大顶堆和小顶堆。大顶堆的特点是每个节点的值都大于或等于其左右子节点的值；小顶堆则是每个节点的值都小于或等于其左右子节点的值。

• 堆排序的基本思想是：首先将待排序的数组构建成一个大顶堆（升序排序时，若为降序排序则构建小顶堆），此时堆顶元素（即数组的第一个元素）就是整个数组中的最大值。然后将堆顶元素与数组的最后一个元素交换位置，这样数组的最后一个位置就存放了最大值，相当于该元素已排序。接着对剩余的 (n - 1) 个元素重新调整为大顶堆，再次得到当前堆中的最大值，将其与数组倒数第二个位置的元素交换，如此反复，直到整个数组有序。

2.算法描述

• 构建堆：

  • 从数组的中间位置开始，依次对每个非叶子节点进行 “下沉” 操作，将数组构建成大顶堆。对于一个具有 n 个元素的数组 arr，非叶子节点的索引范围是 n/2-1 到 0。

  • “下沉” 操作的目的是确保以当前节点为根的子树满足堆的性质。如果当前节点的值小于其某个子节点的值，则将当前节点与较大子节点交换位置，然后对交换后的子节点继续进行 “下沉” 操作，直到该子树满足堆的性质。

• 排序：

  • 将堆顶元素（即数组的第一个元素）与数组的最后一个元素交换位置。此时，数组的最后一个元素就是当前堆中的最大值，并且已处于正确的排序位置。

  • 对剩余的 (n - 1) 个元素（不包括已交换到最后的那个最大值）重新调整为大顶堆。从堆顶元素开始进行 “下沉” 操作，恢复堆的性质。

  • 重复上述交换和调整堆的过程，每次操作都会将当前堆中的最大值放到数组的合适位置，直到数组完全有序。

3.动画演示

4.实现过程

假设我们有一个数组 arr = {12, 11, 13, 5, 6, 7} ，我们来逐步实现堆排序：

1. 构建最大堆：

• 将数组构造成一个最大堆。从最后一个非叶子节点开始，逐个调整节点，使其满足最大堆的性质。

• 最后一个非叶子节点的索引为 parent(n-1) ，其中 n 是数组的长度。

• 调整节点时，比较当前节点与其子节点的值，如果子节点的值大于当前节点的值，则交换它们，并继续调整子节点。

2. 调整堆：

• 每次取出堆顶元素（最大值），将其与堆的最后一个元素交换，然后缩小堆的大小。

• 重新调整堆，使得新的堆顶元素满足最大堆的性质。

3. 重复调整：

• 重复上述过程，直到堆的大小为1，此时数组已经有序。

5.示例

xxxxxxxxxx
59
1
#include <iostream> 
2
using namespace std; 
3

4
// 非递归调整每一个子父节点为最大堆 ，从i节点开始向下调整
5
void heapify(int arr[], int n, int i) { 
6
    while (true) { 
7
        //下面3个变量记录的是下标（节点），而不是值。可以理解为指针
8
        int largest = i; // 初始化最大值为当前节点(根节点) 
9
        int left = 2 * i + 1; // 左子节点 
10
        int right = 2 * i + 2; // 右子节点 
11

12
        // 如果左子节点大于当前最大值 
13
        if (left < n && arr[left] > arr[largest]) { 
14
            largest = left; 
15
        } 
16

17
        // 如果右子节点大于当前最大值 
18
        if (right < n && arr[right] > arr[largest]) { 
19
            largest = right; 
20
        } 
21

22
        // 如果最大值不是当前节点 
23
        if (largest != i) { 
24
            swap(arr[i], arr[largest]); // 交换当前节点和最大值 
25
            i = largest; // 继续调整受影响的子树，即下一趟的父节点
26
        } else { 
27
            break; // 已经满足堆性质，退出循环 
28
        } 
29
    } 
30
} 
31

32
// 堆排序函数 
33
void heapSort(int arr[], int n) { 
34
    for (int i = n / 2 - 1; i >= 0; i--) { 
35
        heapify(arr, n, i); //n-元素总个数，i-元素下标（父节点）
36
    } 
37
    // 逐个取出堆顶元素并调整堆 
38
    for (int i = n - 1;  i > 0; i--) { 
39
        swap(arr[0], arr[i]); // 将堆顶元素与最后一个元素交换 
40
        heapify(arr, i, 0); // 调整剩余的堆 
41
    } 
42
} 
43

44
int main() { 
45
    int n; 
46
    cin >> n; 
47
    int arr[1000]; 
48
    for (int i = 0; i < n; ++i) { 
49
        cin >> arr[i]; 
50
    } 
51

52
    heapSort(arr, n); 
53

54
    for (int i = 0; i < n; ++i) { 
55
        cout << arr[i] << " "; 
56
    } 
57
    cout << endl; 
58
    return 0; 
59
} 

3.8 桶排序

1.基本思想

桶排序（Bucket Sort）是一种非比较类排序算法，基本思想是将待排序的数据分到不同的桶中，每个桶内的数据再单独进行排序，最后按照桶的顺序依次取出桶内已排序的数据，从而得到一个有序的序列。这种方法适用于数据分布较为均匀且范围相对固定的情况。

2.算法描述

• 步骤一：确定桶的数量和范围

  • 首先需要确定桶的数量 n。通常可以根据数据的范围和分布特点来选择，比如数据范围较小且分布均匀时，可以选择较少的桶；数据范围较大时，可能需要较多的桶。同时，确定每个桶所涵盖的数据范围。

• 步骤二：分配数据到桶中

  • 遍历待排序数组，根据每个数据的值，将其分配到对应的桶中。例如，如果数据 x 满足桶 i 的范围条件，就将 x 放入桶 i 中。

• 步骤三：对每个桶内的数据进行排序

  • 对于每个非空的桶，可以使用任意一种排序算法（如插入排序、快速排序等）对桶内的数据进行排序。一般来说，由于每个桶内的数据量相对较小，简单的排序算法如插入排序就可以高效地完成排序。

• 步骤四：收集桶内数据

  • 按照桶的顺序，依次将每个桶内已排序的数据取出，收集到一个新的数组中，这个新数组就是最终的有序数组。

3.动画演示

4.实现过程

假设我们有一个数组 arr = {12, 11, 13, 5, 6, 7, 999, 1, 1000} ，我们来逐步实现桶排序：

1. 确定桶的数量和范围

假设：我们使用10个桶，每个桶的范围为 [0, 100) , [100, 200) , ..., [900, 1000) 。计算：找出数组中的最大值和最小值，确定桶的数量和范围。

xxxxxxxxxx
3
1
int minValue = *min_element(arr.begin(), arr.end());//最小值
2
int maxValue = *max_element(arr.begin(), arr.end());//最大值
3
int bucketCount = (maxValue - minValue) / 100 + 1;//桶的数量

2. 分配元素到桶

xxxxxxxxxx
3
1
遍历数组：将每个元素根据其值分配到对应的桶中。
2

3
桶的索引为   (num - minValue) / 100  。

xxxxxxxxxx
5
1
vector<vector<int>> buckets(bucketCount);
2
for (int num : arr) {
3
 int bucketIndex = (num - minValue) / 100;
4
 buckets[bucketIndex].push_back(num);
5
}

3.对每个桶进行排序

排序：对每个桶中的元素进行排序，可以使用插入排序或其他排序算法。

xxxxxxxxxx
3
1
for (int i = 0; i < bucketCount; ++i) {
2
sort(buckets[i].begin(), buckets[i].end());
3
}

4.合并桶中的元素

合并：按顺序将所有桶中的元素依次取出，合并成一个有序数组。

xxxxxxxxxx
6
1
int index = 0;
2
for (int i = 0; i < bucketCount; ++i) {
3
 for (int num : buckets[i]) {
4
     arr[index++] = num;
5
 }
6
}

5.完整代码实现

xxxxxxxxxx
46
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
void bucketSort(vector<int>& arr) {
7
    int n = arr.size();
8
    if (n <= 1) return; // 如果数组长度小于等于1，直接返回
9
    // 找出数组中的最大值和最小值
10
    int minValue = *min_element(arr.begin(), arr.end());
11
    int maxValue = *max_element(arr.begin(), arr.end());
12
    // 计算桶的数量和每个桶的范围
13
    int bucketCount = (maxValue - minValue) / 100 + 1;
14
    vector<vector<int>> buckets(bucketCount);
15
    // 将元素分配到桶中
16
    for (int num : arr) {
17
        int bucketIndex = (num - minValue) / 100;
18
        buckets[bucketIndex].push_back(num);
19
    }
20
    // 对每个桶进行排序
21
    for (int i = 0; i < bucketCount; ++i) {
22
        sort(buckets[i].begin(), buckets[i].end());
23
    }
24
    // 合并桶中的元素
25
    int index = 0;
26
    for (int i = 0; i < bucketCount; ++i) {
27
        for (int num : buckets[i]) {
28
            arr[index++] = num;
29
        }
30
    }
31
}
32

33
int main() {
34
    vector<int> arr = {12, 11, 13, 5, 6, 7, 999, 1, 1000};
35
    for (int num : arr) {
36
        cout << num << " ";
37
    }
38

39
    bucketSort(arr);
40

41
    for (int num : arr) {
42
        cout << num << " ";
43
    }
44
    return 0;
45
}
46

3.9 基数排序

1.基本思想 基数排序（Radix Sort）是一种非比较排序算法，它基于数字的每一位进行排序。其核心思想是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。从最低位到最高位依次对所有数字进行排序，经过多轮排序后，整个序列就会变为有序。例如，对于一组三位数，先按个位数字排序，再按十位数字排序，最后按百位数字排序，最终得到有序数组。

2.算法描述

• 确定排序的基数和轮数：

  基数通常选择 10（10个桶），因为我们使用的是十进制数系统（对于二进制数，基数就是 2）。轮数取决于待排序数据中的最大数的位数。例如，最大数是 999，它是三位数，所以需要进行 3 轮排序。

• 从最低位到最高位逐位排序：

  对于每一轮排序，根据当前位的数字，将所有数据分配到 0 - 9 这 10 个桶（bucket）中。例如，在按个位排序时，数字 345 会被分配到个位数字为 5 对应的桶中。

  分配完成后，按照桶的顺序（从 0 到 9）依次将桶中的数据收集起来，此时数据在当前位上是有序的。

• 重复上述分配和收集的过程，直到所有位都排序完成。

3.动画演示

4.实现过程

假设我们有一个数组 arr = {170, 45, 75, 90, 802, 24, 2, 66} ，我们来逐步实现基数排序：

1. 确定最大值的位数：

   • 找出数组中的最大值 802 ，它有3位。

2. 按位排序：

   • 从最低位（个位）开始，依次对每一位进行排序。

   • 使用计数排序来处理每一位上的数字。

3. 个位排序：

   • 创建10个桶（0-9），将每个数字的个位放入对应的桶中。

   • 将桶中的数字依次取出，放回数组。

4. 十位排序：

   • 创建10个桶（0-9），将每个数字的十位放入对应的桶中。

   • 将桶中的数字依次取出，放回数组。

5. 百位排序：

   • 创建10个桶（0-9），将每个数字的百位放入对应的桶中。

   • 将桶中的数字依次取出，放回数组。

5.示例

xxxxxxxxxx
57
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5

6
// 计数排序作为基数排序的子程序
7
void cnt(vector<int>& arr, int exp) {
8
    int n = arr.size();
9
    vector<int> output(n);
10
    int count[10] = {0};
11

12
    // 计数每个数字在当前位上的出现次数
13
    for (int i = 0; i < n; ++i) {
14
        count[(arr[i] / exp) % 10]++;
15
    }
16

17
    // 累加计数数组，确定每个数字的最终位置
18
    for (int i = 1; i < 10; ++i) {
19
        count[i] += count[i - 1];
20
    }
21

22
    // 构建输出数组
23
    for (int i = n - 1; i >= 0; --i) {
24
        //从后向前把arr元素低效放到output数组对应位置
25
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
26
        count[(arr[i] / exp) % 10]--;
27
    }
28

29
    // 将输出数组复制回原数组
30
    for (int i = 0; i < n; ++i) {
31
        arr[i] = output[i];
32
    }
33
}
34

35
// 基数排序函数
36
void radixSort(vector<int>& arr) {
37
    //找出最大值
38
    int maxVal = *max_element(arr.begin(), arr.end());
39
    int exp = 1; // 当前位的指数
40
    while (maxVal / exp > 0) {
41
        cnt(arr, exp);
42
        exp *= 10;
43
    }
44
}
45

46
int main() {
47
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
48

49
    radixSort(arr);
50

51
    for (int num : arr) {
52
        cout << num << " ";
53
    }
54

55
    return 0;
56
}
57

3.10 各种排序方法的比较