devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言数据结构——常见排序算法（二）_c语言数据结构的常见的算法时间复杂度排序

作者：繁依Fanyi0 | 2024-07-19 09:56:12

赞

踩

c语言数据结构的常见的算法时间复杂度排序

目录

0.前言

1.交换排序

1.1基本思想

1.2冒泡排序

1.2.1复杂度分析

1.3快速排序

1.3.1部分排序-PartSort

1.3.1.1左右指针法

1.3.1.2前后指针法

1.3.1.3挖坑法

1.3.2快速排序-QuickSort

1.3.2.1三数取中法

1.3.2.2完整代码

2.归并排序

2.1基本思想

2.2代码实现

2.3复杂度分析

3.非比较排序

3.1计数排序

3.2基数排序

4.常见排序算法时间复杂度&算法稳定性总结

4.1排序算法稳定性的含义

4.2比较

5.结语

（图像由AI生成） 

0.前言

在探索计算机科学的旅途中，排序算法无疑占据了一席重要的地位，它们不仅是理解数据结构与算法设计的基石，更是提高程序性能的关键工具。继C语言数据结构——常见排序算法（一）对插入排序、选择排序及其相关变种进行了深入的讲解之后，本篇文章旨在进一步扩展我们的视野，探讨如交换排序、归并排序和非比较排序等更多高效的排序策略。通过对这些高级排序技术的剖析，我们将揭示它们背后的设计思想、性能特点及适用场景，以加深对排序算法多样性和复杂性的理解。

1.交换排序

交换排序是基于交换操作来实现排序的一类算法。它包括了几种具体的排序方法，其中最著名的是冒泡排序和快速排序。这类排序算法的核心思想是通过比较数组中的元素值，并根据比较结果交换它们的位置，以达到排序的目的。

1.1基本思想

交换排序的基本思想很简单：对于给定的元素集合，重复地比较相邻元素的大小，如果它们的顺序错误就交换它们的位置。这个过程重复进行，直到整个序列变为有序。在这个过程中，较小的元素会逐渐“浮”到序列的前端，而较大的元素会“沉”到序列的后端，这就像水泡从水底上升到水面一样，因此得名冒泡排序。而快速排序则是选定一个基准值，通过一趟排序将未排序的序列分割成两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再递归地对这两部分数据分别进行快速排序，以此达到整个序列的有序。

交换排序的特点是实现简单，适用于少量数据的排序，在数据量较大时，其效率不是特别高，但快速排序是一个例外，它是交换排序的一种非常高效的实现，特别适用于大规模数据的排序。尽管快速排序在最坏情况下的时间复杂度为O(n^2)，但其平均时间复杂度为O(n log n)，并且它还有很好的实际性能。

1.2冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换，即该数列已经排序完成。

实现原理

冒泡排序的基本思想是通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐上浮到水面。

  1. void BubbleSort(int* a, int n)
  2. {
  3.     assert(a); // 确保数组指针有效
  4.     int end = n - 1; // 设置未排序序列的边界，每次排序后边界减1
  5.     while (end > 0)
  6.     {
  7.         int exchange = 0; // 用于标记本轮遍历是否发生了交换
  8.         for (int i = 0; i < end; i++)
  9.         {
  10.             // 如果当前元素大于后一个元素，则交换它们
  11.             if (a[i] > a[i + 1])
  12.             {
  13.                 Swap(&a[i], &a[i + 1]);
  14.                 exchange = 1; // 发生了交换，将标记置为1
  15.             }
  16.         }
  17.         // 如果某一轮没有发生交换，说明序列已经完全有序，可以提前结束排序
  18.         if (exchange == 0)
  19.         {
  20.             break;
  21.         }
  22.         end--; // 缩小未排序序列的边界
  23.     }
  24. }

 流程示意图如下（来自1.1 冒泡排序 | 菜鸟教程 (runoob.com)）

1.2.1复杂度分析

  • 时间复杂度：

    • 最好情况：如果数组已经是有序的，冒泡排序只需要进行一次遍历，即O(n)。
    • 最坏情况：如果数组是逆序的，冒泡排序需要进行n(n-1)/2次比较和交换，即O(n^2)。
    • 平均情况：考虑到平均情况下交换的次数，时间复杂度也是O(n^2)。

  • 空间复杂度：

    • 冒泡排序是一种原地排序算法，除了用于交换的临时空间外，不需要额外的存储空间，因此空间复杂度为O(1)。

  • 性能与特点：

    • 冒泡排序的主要优点是算法简单、易于理解和实现。
    • 然而，由于其O(n^2)的时间复杂度，使得冒泡排序在处理大规模数据集时效率低下。
    • 冒泡排序是稳定的排序算法，即相等的元素在排序后会保持其原有的相对顺序，这对某些应用场景非常重要。

1.3快速排序

快速排序是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它的基本思想是分而治之，即从数组中挑选一个元素作为基准（pivot），重新排列数组，所有比基准小的元素摆放在基准前面，所有比基准大的元素摆在基准的后面。这一过程称为一次分区（partition）。然后，递归地（recursive）在小于基准值的子数组和大于基准值的子数组上重复这一过程。

快速排序的关键步骤在于分区操作，有多种实现方式，这里介绍三种常见的分区方法：左右指针法、前后指针法和挖坑法。

1.3.1部分排序-PartSort

1.3.1.1左右指针法

左右指针法是最基本的分区策略，通过两个指针从数组两端向中间扫描。

  1. int PartSort1(int* a, int begin, int end)
  2. {
  3.     int key = a[end]; // 选取最后一个元素作为基准值
  4.     while (begin < end)
  5.     {
  6.         while (begin < end && a[begin] <= key) // 从左向右找第一个大于基准值的元素
  7.         {
  8.             begin++;
  9.         }
  10.         while (begin < end && a[end] >= key) // 从右向左找第一个小于基准值的元素
  11.         {
  12.             end--;
  13.         }
  14.         Swap(&a[begin], &a[end]); // 交换这两个元素
  15.     }
  16.     Swap(&a[begin], &a[keyindex]); // 将基准值交换到正确的位置
  17.     return begin; // 返回基准值的最终位置
  18. }

这是最直观的分区方式。选择数组最右侧的元素作为基准，然后使用两个指针begin和end分别从数组的左右两端开始，向中间移动。

  1. begin指针负责向右移动，寻找第一个大于基准值的元素。
  2. end指针负责向左移动，寻找第一个小于基准值的元素。
  3. 当这样的元素被找到后，交换这两个元素的位置。
  4. 重复这个过程，直到begin和end指针相遇，这时将基准元素与相遇点的元素交换位置。这样，基准元素左侧的所有元素都不大于基准元素，右侧的所有元素都不小于基准元素。
1.3.1.2前后指针法

前后指针法（或双指针法）优化了元素的交换次数，特别适用于存在大量相等元素的数组。

  1. int PartSort2(int* a, int begin, int end)
  2. {
  3.     int key = a[end];
  4.     int cur = begin;
  5.     int prev = cur - 1;
  6.     while (cur < end)
  7.     {
  8.         if (a[cur] < key && ++prev != cur)
  9.         {
  10.             Swap(&a[cur], &a[prev]);
  11.         }
  12.         cur++;
  13.     }
  14.     Swap(&a[++prev], &a[end]);
  15.     return prev;
  16. }

前后指针法也称为双指针法。它选取最右侧元素作为基准，然后使用一个cur指针遍历数组，prev指针标记小于基准值的区域边界。

  1. cur指针从数组的最左侧开始向右移动，寻找小于基准值的元素。
  2. 当发现这样的元素时，prev指针向前移动一位，并且如果prev和cur不同，则交换它们指向的元素。
  3. 重复这个过程直到cur指针遍历完数组，然后将基准元素与prev+1位置的元素交换。这样，保证了基准元素的左侧都是小于它的元素，右侧都是大于等于它的元素。
1.3.1.3挖坑法

挖坑法通过“挖坑填坑”的方式进行元素的交换，这样可以减少数据的移动次数。

  1. int PartSort3(int* a, int begin, int end)
  2. {
  3.     int key = a[end]; // 初始化坑的位置为基准值的位置
  4.     while (begin < end)
  5.     {
  6.         while (begin < end && a[begin] <= key)
  7.         {
  8.             begin++;
  9.         }
  10.         a[end] = a[begin]; // 将大于基准值的元素移动到坑的位置，新的坑挖在begin的位置
  11.         while (begin < end && a[end] >= key)
  12.         {
  13.             end--;
  14.         }
  15.         a[begin] = a[end]; // 将小于基准值的元素移动到坑的位置，新的坑挖在end的位置
  16.     }
  17.     a[begin] = key; // 基准值填入最后的坑
  18.     return begin;
  19. }

挖坑法是一种直观的实现快速排序的方法。首先，选取最右侧元素作为基准，并认为这个位置是一个“坑”。

  1. 从左侧开始，寻找第一个大于基准值的元素，将其挖出并填到“坑”中，这样新挖出的位置成为了新的“坑”。
  2. 然后从右侧开始，寻找第一个小于基准值的元素，将其填到左侧的“坑”中。
  3. 重复这个过程，直到左右指针相遇，最后将基准值填入最后的“坑”中。

1.3.2快速排序-QuickSort

1.3.2.1三数取中法

在快速排序中，选择合适的基准值（pivot）是优化性能的关键之一。三数取中法是一种改进的基准值选择策略，旨在减少最坏情况发生的概率，提高算法在各种数据分布情况下的性能表现。

三数取中法指的是从数组的首元素、尾元素和中间元素中选取中位数作为基准值。相比随机选择或固定选择基准值，三数取中法能更好地适应数组的分布特点，避免了在特定数据集上的极端表现。

  1. int GetMidIndex(int* a, int begin, int end)
  2. {
  3.     int mid = begin + (end - begin) / 2; // 防止直接相加导致的溢出
  4.  
  5.     // 对begin、mid、end所指的三个元素进行排序
  6.     int arr[] = {a[begin], a[mid], a[end]};
  7.     InsertSort(arr, 3); // 使用插入排序，因为数组很小
  8.  
  9.     // 返回中位数对应的原始索引
  10.     if (arr[1] == a[begin]) return begin;
  11.     else if (arr[1] == a[mid]) return mid;
  12.     else return end;
  13. }

这段代码首先计算中间位置的索引，然后构造一个包含首元素、中间元素和尾元素的小数组，并对这个小数组进行排序，最后返回中间元素在原数组中的索引。这样选取的基准值接近于中位数，能有效避免在已经或几乎有序的数组上进行快速排序时的性能退化。

优化策略说明

  • 避免最坏情况：当数据已经是正序或逆序排列时，如果总是选择首元素或尾元素作为基准，快速排序将退化为O(n^2)的时间复杂度。通过三数取中法，可以在一定程度上避免这种最坏情况的发生。
  • 提高效率：三数取中法能够使得基准值更加接近于序列的中位数，从而使得分区更加均衡，减少递归深度，提高排序效率。
  • 实践中的应用：虽然三数取中法增加了少量的计算，但在大多数情况下，这种增加的开销被分区操作的效率提升所抵消。因此，这是一种在实际应用中广泛采用的优化策略。
1.3.2.2完整代码
  1. // 三数取中法，用于优化基准值的选择
  2. int GetMidIndex(int* a, int begin, int end)
  3. {
  4.     int mid = begin + (end - begin) / 2;
  5.     int arr[] = {a[begin], a[mid], a[end]};
  6.     InsertSort(arr, 3); // 对三个数进行排序
  7.     if (arr[1] == a[begin]) return begin;
  8.     else if (arr[1] == a[mid]) return mid;
  9.     else return end;
  10. }
  11.  
  12. // 左右指针法
  13. int PartSort1(int* a, int begin, int end)
  14. {
  15.     int MidIndex = GetMidIndex(a, begin, end);
  16.     Swap(&a[MidIndex], &a[end]); // 将基准值交换到数组末尾
  17.     int key = a[end];
  18.     while (begin < end)
  19.     {
  20.         while (begin < end && a[begin] <= key) begin++;
  21.         while (begin < end && a[end] >= key) end--;
  22.         Swap(&a[begin], &a[end]);
  23.     }
  24.     Swap(&a[begin], &a[end]);
  25.     return begin; // 返回分区的界限
  26. }
  27.  
  28. // 前后指针法
  29. int PartSort2(int* a, int begin, int end)
  30. {
  31.     int MidIndex = GetMidIndex(a, begin, end);
  32.     Swap(&a[MidIndex], &a[end]); // 将基准值交换到数组末尾
  33.     int key = a[end];
  34.     int cur = begin;
  35.     int prev = cur - 1;
  36.     while (cur < end)
  37.     {
  38.         if (a[cur] < key && ++prev != cur) Swap(&a[cur], &a[prev]);
  39.         cur++;
  40.     }
  41.     Swap(&a[++prev], &a[end]);
  42.     return prev;
  43. }
  44.  
  45. // 挖坑法
  46. int PartSort3(int* a, int begin, int end)
  47. {
  48.     int MidIndex = GetMidIndex(a, begin, end);
  49.     Swap(&a[MidIndex], &a[end]); // 将基准值交换到数组末尾
  50.     int key = a[end];
  51.     while (begin < end)
  52.     {
  53.         while (begin < end && a[begin] <= key) begin++;
  54.         a[end] = a[begin];
  55.         while (begin < end && a[end] >= key) end--;
  56.         a[begin] = a[end];
  57.     }
  58.     a[begin] = key;
  59.     return begin;
  60. }
  61.  
  62. // 快速排序主函数
  63. void QuickSort(int* a, int left, int right)
  64. {
  65.     assert(a);
  66.     if (left >= right) return;
  67.     
  68.     if(right - left + 1 < 10)
  69.     {
  70.         // 对小数组使用插入排序
  71.         InsertSort(a + left, right - left + 1);
  72.     }
  73.     else
  74.     {
  75.         // 递归快速排序
  76.         int div = PartSort3(a, left, right); // 使用挖坑法分区
  77.         QuickSort(a, left, div - 1);
  78.         QuickSort(a, div + 1, right);
  79.     }
  80. }

流程示意图如下（来自1.6 快速排序 | 菜鸟教程 (runoob.com)）

1.3.3复杂度分析

时间复杂度

  • 最好情况：当每次分区都能将数组分成长度相等的两部分时，排序的深度为log n，每一层的总工作量为n，因此最好情况下的时间复杂度为O(n log n)。

  • 最坏情况：当每次分区操作都将数组分成长度为1和n-1的两部分时，排序的深度为n，这导致时间复杂度退化为O(n^2)。这种情况通常发生在数组已经是有序或几乎有序的情况下。

  • 平均情况：对于随机分布的数据，快速排序的平均时间复杂度为O(n log n)。通过合理的基准值选择，可以确保算法在大多数情况下都接近于最好情况的性能。

三数取中法对时间复杂度的影响

三数取中法通过从数组的首部、中部、尾部取出三个元素，并选择它们的中位数作为基准值，这种方法旨在减少最坏情况发生的概率，从而改善快速排序的平均性能。

  • 减少最坏情况发生的概率：三数取中法使得基准值的选择更加靠近数组的中位数，减少了在极端数据分布情况下的性能退化，避免了算法时间复杂度频繁达到O(n^2)的情况。

  • 提升平均性能：虽然三数取中法增加了少量的前期计算（需要对三个元素进行比较和可能的排序），但它通过更合理的基准值选择，使得分区过程更加均衡，减少了递归深度，提高了排序的平均效率。

  • 对最好和最坏情况的影响：三数取中法不改变快速排序在最好情况下的时间复杂度（O(n log n)），但它有效地减少了最坏情况的发生频率，使得算法的平均时间复杂度接近最好情况。

2.归并排序

归并排序是一种高效的排序算法，采用分治法的思想来实现。其基本原理是将一个数组分成两半，分别对它们进行排序，然后将两个有序数组合并成一个整体有序数组。

2.1基本思想

归并排序的核心思想可以概括为三个步骤：

  1. 分解：将当前区间一分为二，即求出分割点mid = (left + right) / 2。
  2. 递归解决：递归地对两个子区间a[left,mid]和a[mid+1,right]进行归并排序。
  3. 合并：将两个有序子区间合并成一个整体有序区间。

归并过程需要额外的空间来暂存数据，这是归并排序空间复杂度高于O(1)的主要原因。

2.2代码实现

  1. void _MergeSort(int* a, int left, int right, int* tmp)
  2. {
  3.     if (left < right)
  4.     {
  5.         int mid = left + (right - left) / 2; // 避免溢出
  6.         _MergeSort(a, left, mid, tmp); // 排序左半部分
  7.         _MergeSort(a, mid + 1, right, tmp); // 排序右半部分
  8.         int i = left;
  9.         int j = mid + 1;
  10.         int k = left;
  11.  
  12.         // 合并两个有序区间
  13.         while (i <= mid && j <= right) {
  14.             if (a[i] <= a[j]) {
  15.                 tmp[k++] = a[i++];
  16.             }
  17.             else {
  18.                 tmp[k++] = a[j++];
  19.             }
  20.         }
  21.  
  22.         // 处理剩余的元素
  23.         while (i <= mid) {
  24.             tmp[k++] = a[i++];
  25.         }
  26.         while (j <= right) {
  27.             tmp[k++] = a[j++];
  28.         }
  29.  
  30.         // 将合并后的数组复制回原数组
  31.         for (i = left; i <= right; i++) {
  32.             a[i] = tmp[i];
  33.         }
  34.     }
  35. }
  36.  
  37. void MergeSort(int* a, int n) {
  38.     assert(a);
  39.     int* tmp = (int*)malloc(sizeof(int) * n);
  40.     if (tmp == NULL) {
  41.         printf("malloc fail\n");
  42.         exit(-1);
  43.     }
  44.     _MergeSort(a, 0, n - 1, tmp);
  45.     free(tmp);
  46. }

_MergeSort函数详解

  1. 分解：计算中间位置mid = left + (right - left) / 2，这样做可以避免大数相加可能导致的整数溢出问题。然后将数组从中间分割成两个部分，分别对这两部分递归地执行归并排序。

  2. 递归排序：递归调用_MergeSort(a, left, mid, tmp)对左半数组进行排序，_MergeSort(a, mid + 1, right, tmp)对右半数组进行排序。递归的基准情况是子数组只包含一个元素（此时子数组自然是有序的）。

  3. 合并：

    • 创建两个指针i和j，分别指向左半部分和右半部分的起始位置。
    • 比较这两个指针所指向的元素，将较小的元素先复制到临时数组tmp中，并移动相应的指针。
    • 当左半部分或右半部分的元素全部复制到tmp后，如果还有剩余的元素，直接将剩余元素复制到tmp中，这确保了没有遗漏任何元素。

  4. 复制回原数组：将临时数组tmp中的有序元素复制回原数组a[left...right]。这一步是必要的，因为归并过程在tmp中进行，原数组a的相应部分在这个过程中还是无序的。

MergeSort函数详解

  • MergeSort函数是归并排序的对外接口，主要负责初始化所需的额外空间（即临时数组tmp）并调用_MergeSort函数。
  • int* tmp = (int*)malloc(sizeof(int) * n);通过动态内存分配，为临时数组tmp分配足够的空间。这一空间将用于在归并过程中暂存元素。
  • _MergeSort(a, 0, n - 1, tmp);从数组的最左侧到最右侧对整个数组进行排序。
  • free(tmp);在排序完成后，释放tmp所占用的内存空间。这一步骤是必要的，以避免内存泄露。

  流程示意图如下（来自1.5 归并排序 | 菜鸟教程 (runoob.com))

2.3复杂度分析

时间复杂度

  • 最好、最坏和平均情况：归并排序在最好、最坏和平均情况下的时间复杂度都是O(n log n)。这是因为归并排序总是均匀地将数组分成两半，并且对这两半进行递归排序，然后再将它们合并。无论数组的初始状态如何，分解和合并操作所需的时间总是相同的。

    • 分解过程：每次递归调用都将问题规模减半，总共需要进行log n层递归。
    • 合并过程：每层递归都需要完整地遍历n个元素以完成合并，因此每层的时间复杂度是O(n)。
    • 综合考虑，归并排序的总时间复杂度是O(n log n)。

空间复杂度

  • 总体空间复杂度：归并排序需要一个与原数组相同大小的临时数组来存放在合并过程中排序后的数据，因此其空间复杂度为O(n)。

  • 归并排序的空间复杂度主要来源于两个方面：

    1. 临时数组：用于在每次合并操作中暂存元素，其大小与原数组相同。
    2. 递归调用栈：归并排序是通过递归实现的，递归的深度最大为log n，每层递归需要的额外空间相对较小。

3.非比较排序

非比较排序是一种不通过比较操作来决定元素间顺序的排序算法。与基于比较的排序算法（如快速排序、归并排序等）不同，非比较排序通常能在更快的时间内完成排序任务，尤其适用于特定类型的数据集。其中，计数排序是一种非常高效的非比较排序方法。

3.1计数排序

计数排序是一种稳定的排序算法，适用于一定范围内的整数排序。它的基本思想是对每一个输入的元素a[i]，确定小于a[i]的元素个数，然后直接将a[i]放到输出数组的相应位置上。

  1. void CountSort(int* a, int n)
  2. {
  3.     assert(a);
  4.     int min = a[0], max = a[0];
  5.     // 找到数组的最大值和最小值
  6.     for (int i = 0; i < n; i++)
  7.     {
  8.         if (a[i] < min) min = a[i];
  9.         if (a[i] > max) max = a[i];
  10.     }
  11.     
  12.     int range = max - min + 1; // 计算范围
  13.     int* count = (int*)calloc(range, sizeof(int)); // 创建计数数组
  14.     if (count == NULL)
  15.     {
  16.         printf("calloc fail\n");
  17.         exit(-1);
  18.     }
  19.     
  20.     // 对每个元素计数
  21.     for (int i = 0; i < n; i++)
  22.     {
  23.         count[a[i] - min]++;
  24.     }
  25.     
  26.     // 根据计数数组重建原数组
  27.     for (int i = 0, index = 0; i < range; i++)
  28.     {
  29.         while (count[i]--)
  30.         {
  31.             a[index++] = i + min;
  32.         }
  33.     }
  34.     
  35.     free(count); // 释放计数数组
  36. }

分析

  • 时间复杂度：计数排序的时间复杂度为O(n+k)，其中n是列表长度，k是整数范围。这是因为算法首先遍历一次原数组来计数，然后再遍历一次计数数组来重建原数组。

  • 空间复杂度：由于需要额外创建一个计数数组，其空间大小依赖于输入数据的范围（max - min + 1），因此空间复杂度为O(k)。

  • 适用场景：计数排序最适合范围不是很大的情况。如果max和min之间的范围远大于元素个数n，计数排序可能就不那么高效了，因为会产生大量未使用的空间。

流程示意图如下（来自1.8 计数排序 | 菜鸟教程 (runoob.com)）

3.2基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表示字符串（如姓名或日期）和特定格式的浮点数，所以基数排序不仅可以用于整数排序，也可以用于其他类型数据的排序。

实现原理

基数排序通过以下步骤进行：

  1. 找到最大数：确定需要排序数组中的最大数，并计算出最大数的位数digit。这是因为最大数的位数决定了排序进行的轮数。
  2. 创建计数数组：用于在每个位排序过程中计数。
  3. 排序过程：从最低位开始，依次对每一位进行排序。排序时，根据当前位的数值将整个数组的元素分配到相应的桶中，然后按照桶的顺序收集数组元素。这个过程重复进行，直到最高位排序完成。
  1. void RadixSort(int* a, int n)
  2. {
  3.     assert(a);
  4.     int max = a[0];
  5.     // 找出最大数
  6.     for (int i = 0; i < n; i++)
  7.     {
  8.         if (a[i] > max)
  9.         {
  10.             max = a[i];
  11.         }
  12.     }
  13.     // 计算最大数的位数
  14.     int digit = 0;
  15.     while (max)
  16.     {
  17.         max /= 10;
  18.         digit++;
  19.     }
  20.  
  21.     int* count = (int*)malloc(sizeof(int) * 10); // 计数数组
  22.     int* bucket = (int*)malloc(sizeof(int) * n); // 桶数组
  23.     int radix = 1;
  24.     for (int i = 0; i < digit; i++) // 按照位数进行的轮数
  25.     {
  26.         memset(count, 0, sizeof(int) * 10); // 初始化计数数组
  27.         // 计数
  28.         for (int j = 0; j < n; j++)
  29.         {
  30.             count[(a[j] / radix) % 10]++;
  31.         }
  32.         // 累加
  33.         for (int j = 1; j < 10; j++)
  34.         {
  35.             count[j] += count[j - 1];
  36.         }
  37.         // 分配
  38.         for (int j = n - 1; j >= 0; j--)
  39.         {
  40.             int k = (a[j] / radix) % 10;
  41.             bucket[count[k] - 1] = a[j];
  42.             count[k]--;
  43.         }
  44.         // 收集
  45.         memcpy(a, bucket, sizeof(int) * n);
  46.         radix *= 10;
  47.     }
  48.     free(count);
  49.     free(bucket);
  50. }

复杂度分析

  • 时间复杂度：基数排序的时间复杂度为O(nk)，其中n是排序元素的个数，k是数字的最大位数。
  • 空间复杂度：基数排序的空间复杂度为O(n+k)，主要是计数数组和桶数组的开销。

性能和特点

  • 基数排序是稳定的排序算法。
  • 它的效率高于简单的比较排序，尤其是当k不大于log(n)时。
  • 基数排序适用于：
    • 需要排序的数字位数相近。
    • 分布均匀，且范围不是特别大的整数排序。
  • 基数排序的主要缺点是需要额外的空间来创建桶。

 流程示意图如下（来自1.10 基数排序 | 菜鸟教程 (runoob.com)）

4.常见排序算法时间复杂度&算法稳定性总结

4.1排序算法稳定性的含义

排序算法的稳定性是指在排序过程中，具有相等键值的元素之间的相对顺序在排序前后是否保持不变。如果排序算法能够保持相等元素之间的相对次序不变，那么这种排序算法被称为稳定的；反之，如果排序过程可能改变相等元素之间的相对次序，则该算法被认为是不稳定的。

稳定性在多关键字排序中尤为重要。例如，在对一组记录按照多个字段进行排序时，稳定的排序算法可以保证，当按照第二个字段排序时，第一个字段排序的结果仍然得以保留。这意味着稳定的排序算法可以通过顺序对每个关键字应用排序操作来实现多关键字排序，而不会打乱之前关键字的排序结果。

稳定排序算法示例

  • 冒泡排序：通过相邻元素的比较和交换来实现排序，能够保持相等元素的相对顺序，因此是稳定的。
  • 插入排序：每次将一个待排序的元素插入到前面已经排序的序列中的适当位置，插入过程不会改变相等元素的相对顺序，故而稳定。
  • 归并排序：在合并两个有序数组的过程中，当遇到相等元素时，总是先复制前面数组的元素，这保证了排序的稳定性。

不稳定排序算法示例

  • 快速排序：由于快速排序中基准元素的选择和元素的交换过程，可能会改变相等元素的初始相对位置，因此是不稳定的。
  • 堆排序：在调整堆的过程中，堆顶元素与最后一个元素的交换可能会破坏相等元素的原始顺序，所以是不稳定的。
  • 选择排序：每次从未排序的部分选出最小（或最大）元素，然后与未排序部分的首元素交换位置，这个选择过程可能改变相等元素之间的相对顺序，因而不稳定。

4.2比较

（来自1.0 十大经典排序算法 | 菜鸟教程 (runoob.com)）

5.结语

通过对常见排序算法的深入探讨，我们得以领略它们各自的独特魅力和应用场景。无论是插入排序的简洁、选择排序的直观、还是归并排序和快速排序的高效，每种算法都在特定条件下展现出了其价值。理解这些排序算法的原理和性质，不仅能够帮助我们更好地处理数据排序问题，还能深化我们对算法设计和优化的认识。在实际应用中，选择合适的排序算法可以显著提升程序的性能。希望本系列文章能为你的学习之旅提供有益的参考和启发。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/850783
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号