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

［大师C语言(第十六篇)］九种C语言排序算法详解

作者：不正经 | 2024-06-04 12:52:09

赞

踩

［大师C语言(第十六篇)］九种C语言排序算法详解

C语言排序算法详解：第一部分

在计算机科学中，排序算法是基本且重要的技术之一。C语言，作为一种高效、灵活的编程语言，被广泛用于实现各种排序算法。本文将深入探讨C语言中常用的排序算法，包括冒泡排序、选择排序和插入排序。我们将详细分析每种算法的原理、代码实现和性能特点，帮助读者全面理解排序算法的精髓。

冒泡排序（Bubble Sort）

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

原理

冒泡排序的基本思想是通过比较相邻的元素值，若发现顺序错误则交换它们，直到没有需要交换的元素，此时数列已排序完成。

代码实现

  1. #include <stdio.h>
  2.  
  3. void bubbleSort(int arr[], int n) {
  4.     int i, j, temp;
  5.     for (i = 0; i < n - 1; i++) {
  6.         for (j = 0; j < n - i - 1; j++) {
  7.             if (arr[j] > arr[j + 1]) {
  8.                 // 交换元素
  9.                 temp = arr[j];
  10.                 arr[j] = arr[j + 1];
  11.                 arr[j + 1] = temp;
  12.             }
  13.         }
  14.     }
  15. }
  16.  
  17. int main() {
  18.     int arr[] = {64, 34, 25, 12, 22, 11, 90};
  19.     int n = sizeof(arr) / sizeof(arr[0]);
  20.     bubbleSort(arr, n);
  21.     printf("Sorted array: \n");
  22.     for (int i = 0; i < n; i++) {
  23.         printf("%d ", arr[i]);
  24.     }
  25.     printf("\n");
  26.     return 0;
  27. }

性能分析

  • 时间复杂度：最坏情况下，冒泡排序需要进行n-1次遍历，每次遍历需要进行n-i次比较和交换，因此时间复杂度为O(n^2)。
  • 空间复杂度：冒泡排序是原地排序算法，除了交换元素需要的临时空间外，不需要额外空间，因此空间复杂度为O(1)。

选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的工作原理是不断地选择剩余元素中的最小（或最大）元素，放到已排序的序列的末尾，直到排序完成。

原理

选择排序每次循环找到未排序部分的最小值，将其与未排序部分的第一个元素交换，这样未排序部分的最小值就被移到了已排序部分的末尾。

代码实现

  1. #include <stdio.h>
  2.  
  3. void selectionSort(int arr[], int n) {
  4.     int i, j, min_idx, temp;
  5.     for (i = 0; i < n - 1; i++) {
  6.         min_idx = i;
  7.         for (j = i + 1; j < n; j++) {
  8.             if (arr[j] < arr[min_idx]) {
  9.                 min_idx = j;
  10.             }
  11.         }
  12.         // 将找到的最小值交换到未排序部分的起始位置
  13.         temp = arr[min_idx];
  14.         arr[min_idx] = arr[i];
  15.         arr[i] = temp;
  16.     }
  17. }
  18.  
  19. int main() {
  20.     int arr[] = {64, 25, 12, 22, 11};
  21.     int n = sizeof(arr) / sizeof(arr[0]);
  22.     selectionSort(arr, n);
  23.     printf("Sorted array: \n");
  24.     for (int i = 0; i < n; i++) {
  25.         printf("%d ", arr[i]);
  26.     }
  27.     printf("\n");
  28.     return 0;
  29. }

性能分析

  • 时间复杂度：选择排序需要进行n-1次遍历，每次遍历需要找到未排序部分的最小值并进行一次交换，因此时间复杂度为O(n^2)。
  • 空间复杂度：选择排序也是原地排序算法，除了交换元素需要的临时空间外，不需要额外空间，因此空间复杂度为O(1)。

插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

原理

插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

代码实现

  1. #include <stdio.h>
  2.  
  3. void insertionSort(int arr[], int n) {
  4.     int i, key, j;
  5.     for (i = 1; i < n; i++) {
  6.         key = arr[i];
  7.         j = i - 1;
  8.         
  9.         // 将arr[i]与已排序的arr[0...i-1]中的元素进行比较，找到合适的位置插入
  10.         while (j >= 0 && arr[j] > key) {
  11.             arr[j + 1] = arr[j];
  12.             j = j - 1;
  13.         }
  14.         arr[j + 1] = key;
  15.     }
  16. }
  17.  
  18. int main() {
  19.     int arr[] = {12, 11, 13, 5, 6};
  20.     int n = sizeof(arr) / sizeof(arr[0]);
  21.     insertionSort(arr, n);
  22.     printf("Sorted array: \n");
  23.     for (int i = 0; i < n; i++) {
  24.         printf("%d ", arr[i]);
  25.     }
  26.     printf("\n");
  27.     return 0;
  28. }

性能分析

  • 时间复杂度：插入排序的最好情况是输入数组已经是有序的，此时时间复杂度为O(n)。最坏情况下，输入数组是逆序的，此时每个元素都需要向左移动到数组的起始位置，时间复杂度为O(n^2)。平均情况下，插入排序的时间复杂度也是O(n^2)。
  • 空间复杂度：插入排序是原地排序算法，除了交换元素需要的临时空间外，不需要额外空间，因此空间复杂度为O(1)。

总结

在本文的第一部分中，我们详细介绍了三种基本的排序算法：冒泡排序、选择排序和插入排序。这些算法虽然简单，但它们是理解更复杂排序算法的基础。每种算法都有其独特的原理和实现方式，同时也有各自的性能特点。

  • 冒泡排序通过不断交换相邻元素，将最大（或最小）的元素逐渐“冒泡”到数组的末端。
  • 选择排序通过每次选择未排序部分的最小（或最大）元素，将其放到已排序部分的末尾。
  • 插入排序通过将每个元素插入到已排序部分的正确位置，逐步构建有序数组。

这些算法的时间复杂度都是O(n^2)，在处理小规模数据时效率尚可，但在数据规模较大时，性能会成为瓶颈。因此，它们在实际应用中通常会被更高效的算法如快速排序、归并排序等所取代。然而，由于它们的简单性和直观性，这些基础排序算法仍然是算法学习和教学中的重要组成部分。

在下一部分中，我们将继续探讨更高级的排序算法，并分析它们在效率和适用性方面的差异。

C语言排序算法详解：第二部分

在第一部分中，我们讨论了冒泡排序、选择排序和插入排序，这些是基础的排序算法，适用于小型数据集。在本部分，我们将探讨更高效的排序算法，包括快速排序、归并排序和堆排序。这些算法在处理大规模数据时表现更佳，是实际应用中常用的排序技术。

快速排序（Quick Sort）

快速排序是一种高效的排序算法，采用分治法的一个典例。它的工作原理是选择一个“基准”元素，将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于或等于基准的元素，然后递归地对这两个子数组进行快速排序。

原理

  1. 选择基准（Pivot）：从数列中挑出一个元素，作为基准。
  2. 分割（Partitioning）：重新排列数列，所有比基准小的元素摆放在基准前面，所有比基准大的元素摆在基准的后面（相等的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。
  3. 递归排序子序列：递归地将小于基准元素的子序列和大于基准元素的子序列排序。

代码实现

  1. #include <stdio.h>
  2.  
  3. // 快速排序的递归函数
  4. void quickSort(int arr[], int low, int high) {
  5.     if (low < high) {
  6.         // pi是分区后基准元素的正确位置
  7.         int pi = partition(arr, low, high);
  8.  
  9.         // 分别对分区前后的子数组进行递归排序
  10.         quickSort(arr, low, pi - 1);
  11.         quickSort(arr, pi + 1, high);
  12.     }
  13. }
  14.  
  15. // 分区操作
  16. int partition(int arr[], int low, int high) {
  17.     int pivot = arr[high]; // 选择最后一个元素作为基准
  18.     int i = (low - 1); // 小于基准元素的区域边界
  19.  
  20.     for (int j = low; j <= high - 1; j++) {
  21.         // 当前元素小于或等于基准
  22.         if (arr[j] <= pivot) {
  23.             i++; // 移动边界
  24.             swap(&arr[i], &arr[j]); // 交换元素
  25.         }
  26.     }
  27.     swap(&arr[i + 1], &arr[high]);
  28.     return (i + 1);
  29. }
  30.  
  31. // 交换元素
  32. void swap(int *xp, int *yp) {
  33.     int temp = *xp;
  34.     *xp = *yp;
  35.     *yp = temp;
  36. }
  37.  
  38. int main() {
  39.     int arr[] = {10, 7, 8, 9, 1, 5};
  40.     int n = sizeof(arr) / sizeof(arr[0]);
  41.     quickSort(arr, 0, n - 1);
  42.     printf("Sorted array: \n");
  43.     for (int i = 0; i < n; i++) {
  44.         printf("%d ", arr[i]);
  45.     }
  46.     printf("\n");
  47.     return 0;
  48. }

性能分析

  • 时间复杂度：快速排序的平均时间复杂度为O(n log n)，但在最坏情况下会退化到O(n^2)。
  • 空间复杂度：快速排序的空间复杂度为O(log n)，这是因为递归栈的深度。

归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。它将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

原理

  1. 分割：将数组分成若干个小组，每个小组内部再继续分割，直到每组只有一个元素。
  2. 归并：将分割后的小组合并成大的有序组，不断重复这个过程，直到整个数组有序。

代码实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // 归并两个子数组
  5. void merge(int arr[], int l, int m, int r) {
  6.     int i, j, k;
  7.     int n1 = m - l + 1;
  8.     int n2 = r - m;
  9.  
  10.     // 创建临时数组
  11.     int L[n1], R[n2];
  12.  
  13.     // 拷贝数据到临时数组
  14.     for (i = 0; i < n1; i++)
  15.         L[i] = arr[l + i];
  16.     for (j = 0; j < n2; j++)
  17.         R[j] = arr[m + 1 + j];
  18.  
  19.     // 合并临时数组回到原数组
  20.     i = 0;
  21.     j = 0;
  22.     k = l;
  23.     while (i < n1 && j < n2) {
  24.         if (L[i] <= R[j]) {
  25.             arr[k] = L[i];
  26.             i++;
  27.         } else {
  28.             arr[k] = R[j];
  29.             j++;
  30.         }
  31.         k++;
  32.     }
  33.  
  34.     // 拷贝L[]的剩余元素
  35.     while (i < n1) {
  36.         arr[k] = L[i];
  37.         i++;
  38.         k++;
  39.     }
  40.  
  41.     // 拷贝R[]的剩余元素
  42.     while (j < n2) {
  43.         arr[k] = R[j];
  44.         j++;
  45.         k++;
  46.     }
  47. }
  48.  
  49. // 主函数，用于调用mergeSort
  50. void mergeSort(int arr[], int l, int r) {
  51.     if (l < r) {
  52.         // 找到中间点
  53.         int m = l + (r - l) / 2;
  54.  
  55.         // 分别对前半部分和后半部分进行归并排序
  56.         mergeSort(arr, l, m);
  57.         mergeSort(arr, m + 1, r);
  58.  
  59.         // 合并两个有序部分
  60.         merge(arr, l, m, r);
  61.     }
  62. }
  63.  
  64. int main() {
  65.     int arr[] = {12, 11, 13, 5, 6, 7};
  66.     int arr_size = sizeof(arr) / sizeof(arr[0]);
  67.  
  68.     printf("Given array is \n");
  69.     for (int i = 0; i < arr_size; i++) {
  70.         printf("%d ", arr[i]);
  71.     }
  72.     printf("\n");
  73.  
  74.     mergeSort(arr, 0, arr_size - 1);
  75.  
  76.     printf("Sorted array is \n");
  77.     for (int i = 0; i < arr_size; i++) {
  78.         printf("%d ", arr[i]);
  79.     }
  80.     printf("\n");
  81.     return 0;
  82. }

性能分析

  • 时间复杂度：归并排序的时间复杂度为O(n log n)，无论是最好、最坏还是平均情况，时间复杂度都是这个值。
  • 空间复杂度：归并排序需要与原数组等长的额外空间来存储临时数组，因此空间复杂度为O(n)。

堆排序（Heap Sort）

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

原理

  1. 建立堆：将待排序的序列构造成一个大顶堆（或小顶堆），使得每个父节点的值都大于或等于其左右孩子节点的值。
  2. 调整堆：将堆顶元素与最后一个元素交换，然后减少堆的大小，重新调整堆，重复这个过程直到堆的大小为1。

代码实现

  1. #include <stdio.h>
  2.  
  3. // 用于交换元素的辅助函数
  4. void swap(int *a, int *b) {
  5.     int temp = *a;
  6.     *a = *b;
  7.     *b = temp;
  8. }
  9.  
  10. // 调整堆
  11. void heapify(int arr[], int n, int i) {
  12.     int largest = i; // 初始化最大值为根节点
  13.     int left = 2 * i + 1; // 左子节点
  14.     int right = 2 * i + 2; // 右子节点
  15.  
  16.     // 如果左子节点大于根节点
  17.     if (left < n && arr[left] > arr[largest])
  18.         largest = left;
  19.  
  20.     // 如果右子节点大于最大值
  21.     if (right < n && arr[right] > arr[largest])
  22.         largest = right;
  23.  
  24.     // 如果最大值不是根节点，交换之，并递归地调整受影响的子树
  25.     if (largest != i) {
  26.         swap(&arr[i], &arr[largest]);
  27.         heapify(arr, n, largest);
  28.     }
  29. }
  30.  
  31. // 主函数，用于执行堆排序
  32. void heapSort(int arr[], int n) {
  33.     // 建立大顶堆
  34.     for (int i = n / 2 - 1; i >= 0; i--)
  35.         heapify(arr, n, i);
  36.  
  37.     // 一个个从堆顶取出元素
  38.     for (int i = n - 1; i >= 0; i--) {
  39.         // 移动当前根节点到数组末尾
  40.         swap(&arr[0], &arr[i]);
  41.  
  42.         // 调整堆
  43.         heapify(arr, i, 0);
  44.     }
  45. }
  46.  
  47. int main() {
  48.     int arr[] = {12, 11, 13, 5, 6, 7};
  49.     int n = sizeof(arr) / sizeof(arr[0]);
  50.  
  51.     heapSort(arr, n);
  52.  
  53.     printf("Sorted array is \n");
  54.     for (int i = 0; i < n; i++) {
  55.         printf("%d ", arr[i]);
  56.     }
  57.     printf("\n");
  58.     return 0;
  59. }

性能分析

  • 时间复杂度：堆排序的时间复杂度为O(n log n)，这是因为在建立堆的过程中，每个元素都需要比较和下沉，而在排序过程中，每个元素都需要从堆顶移除并重新调整堆。
  • 空间复杂度：堆排序是原地排序算法，除了交换元素需要的临时空间外，不需要额外空间，因此空间复杂度为O(1)。

总结

在本文的第二部分中，我们介绍了三种更高效的排序算法：快速排序、归并排序和堆排序。这些算法在处理大规模数据时表现更佳，是实际应用中常用的排序技术。

  • 快速排序通过分治法，选择基准元素，将数组分割成两部分，然后递归地对这两部分进行排序。
  • 归并排序同样采用分治法，先将数组分割成最小单元，然后两两合并，最终得到有序数组。
  • 堆排序利用堆这种数据结构，首先建立堆，然后不断将堆顶元素与堆底元素交换，并重新调整堆，直到堆为空。

这些算法的时间复杂度都为O(n log n)，在平均情况下能够提供较好的性能。快速排序和堆排序是原地排序算法，而归并排序需要额外的空间来存储临时数组。在实际应用中，选择哪种排序算法取决于数据的特性和需求。

在下一部分中，我们将探讨特殊场景下的排序算法，例如计数排序、桶排序和基数排序，这些算法在特定条件下能够提供线性时间复杂度的排序性能。

C语言排序算法详解：第三部分

在前两部分中，我们讨论了冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序。这些算法在各种情况下都有其适用性，但在某些特定场景中，我们可以使用更高效的算法。在第三部分，我们将探讨计数排序、桶排序和基数排序，这些算法在特定条件下能够提供线性时间复杂度的排序性能。

计数排序（Counting Sort）

计数排序是一种非比较型整数排序算法，其原理是将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

原理

  1. 找出待排序的数组中最大和最小的元素。
  2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项。
  3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）。
  4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

代码实现

  1. #include <stdio.h>
  2.  
  3. void countingSort(int arr[], int n) {
  4.     int max = arr[0];
  5.     for (int i = 1; i < n; i++) {
  6.         if (arr[i] > max)
  7.             max = arr[i];
  8.     }
  9.  
  10.     int count[max + 1]; // 创建计数数组
  11.     for (int i = 0; i <= max; i++) {
  12.         count[i] = 0;
  13.     }
  14.  
  15.     // 计数每个元素出现的次数
  16.     for (int i = 0; i < n; i++) {
  17.         count[arr[i]]++;
  18.     }
  19.  
  20.     // 重建原始数组
  21.     int index = 0;
  22.     for (int i = 0; i <= max; i++) {
  23.         while (count[i] > 0) {
  24.             arr[index++] = i;
  25.             count[i]--;
  26.         }
  27.     }
  28. }
  29.  
  30. int main() {
  31.     int arr[] = {4, 2, 2, 8, 3, 3, 1};
  32.     int n = sizeof(arr) / sizeof(arr[0]);
  33.     countingSort(arr, n);
  34.     printf("Sorted array: \n");
  35.     for (int i = 0; i < n; i++) {
  36.         printf("%d ", arr[i]);
  37.     }
  38.     printf("\n");
  39.     return 0;
  40. }

性能分析

  • 时间复杂度：计数排序的时间复杂度为O(n+k)，其中k是输入数据的范围。
  • 空间复杂度：计数排序的空间复杂度为O(n+k)，因为需要额外的数组来存储计数。

桶排序（Bucket Sort）

桶排序是计数排序的升级版，它将元素分到几个有序的桶里，每个桶里的元素再分别排序。桶排序适用于数据分布均匀且范围不大的情况。

原理

  1. 设置一个定量的数组当作空桶。
  2. 遍历输入数据，并且把数据一个一个放到对应的桶中。
  3. 对每个不是空的桶进行排序。
  4. 从不是空的桶里把排好序的数据拼接起来。

代码实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // 用于桶内排序的函数
  5. void insertionSort(int arr[], int n) {
  6.     int i, j, key;
  7.     for (i = 1; i < n; i++) {
  8.         key = arr[i];
  9.         j = i - 1;
  10.         while (j >= 0 && arr[j] > key) {
  11.             arr[j + 1] = arr[j];
  12.             j = j - 1;
  13.         }
  14.         arr[j + 1] = key;
  15.     }
  16. }
  17.  
  18. void bucketSort(int arr[], int n) {
  19.     int i, j;
  20.     // 找到最大值和最小值
  21.     int minValue = arr[0];
  22.     int maxValue = arr[0];
  23.     for (i = 1; i < n; i++) {
  24.         if (arr[i] < minValue)
  25.             minValue = arr[i];
  26.         else if (arr[i] > maxValue)
  27.             maxValue = arr[i];
  28.     }
  29.  
  30.     // 创建桶并分配数据
  31.     int bucketCount = (maxValue - minValue) / n + 1;
  32.     int** buckets = (int**)malloc(sizeof(int*) * bucketCount);
  33.     for (i = 0; i < bucketCount; i++) {
  34.         buckets[i] = (int*)malloc(sizeof(int) * n);
  35.         buckets[i][0] = 0; // 桶的索引从1开始
  36.     }
  37.  
  38.     // 将数组中的值分配到桶中
  39.     for (i = 0; i < n; i++) {
  40.         int bucketIndex = (arr[i] - minValue) / n;
  41.         buckets[bucketIndex][++buckets[bucketIndex][0]] = arr[i];
  42.     }
  43.  
  44.     // 对每个桶进行排序
  45.     for (i = 0; i < bucketCount; i++) {
  46.         insertionSort(buckets[i], buckets[i][0] + 1);
  47.     }
  48.  
  49.     // 合并桶
  50.     int index = 0;
  51.     for (i = 0; i < bucketCount; i++) {
  52.         for (j = 1; j <= buckets[i][0]; j++) {
  53.             arr[index++] = buckets[i][j];
  54.         }
  55.     }
  56.  
  57.     // 释放内存
  58.     for (i = 0; i < bucketCount; i++) {
  59.         free(buckets[i]);
  60.     }
  61.     free(buckets);
  62. }
  63.  
  64. int main() {
  65.     int arr[] = {4, 2, 2, 8, 3, 3, 1};
  66.     int n = sizeof(arr) / sizeof(arr[0]);
  67.     bucketSort(arr, n);
  68.     printf("Sorted array: \n");
  69.     for (int i = 0; i < n; i++) {
  70.         printf("%d ", arr[i]);
  71.     }
  72.     printf("\n");
  73.     return 0;
  74. }

性能分析

  • 时间复杂度：桶排序的平均时间复杂度为O(n+k)，其中k是桶的数量。最坏情况下，时间复杂度为O(n^2)，当所有元素都分配到同一个桶中时。
  • 空间复杂度：桶排序的空间复杂度为O(n+k)，因为需要额外的空间来存储桶和桶内的元素。

基数排序（Radix Sort）

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digit）或MSD（Most significant digit）。

原理

  1. 取得数组中的最大数，并取得位数。
  2. arr为原始数组，从最低位开始取每个位组成radix数组。
  3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）。

代码实现

  1. #include <stdio.h>
  2.  
  3. // 用于获取最大数的位数
  4. int maxDigits(int arr[], int n) {
  5.     int max = arr[0];
  6.     for (int i = 1; i < n; i++) {
  7.         if (arr[i] > max) {
  8.             max = arr[i];
  9.         }
  10.     }
  11.     int count = 0;
  12.     while (max != 0) {
  13.         count++;
  14.         max /= 10;
  15.     }
  16.     return count;
  17. }
  18.  
  19. void countingSortForRadix(int arr[], int n, int exp) {
  20.     int output[n]; // 输出数组
  21.     int count[10] = {0}; // 计数数组
  22.  
  23.     // 计数每个元素的位
  24.     for (int i = 0; i < n; i++) {
  25.         count[(arr[i] / exp) % 10]++;
  26.     }
  27.  
  28.     // 更改count[i]使其包含前i个数的总数
  29.     for (int i = 1; i < 10; i++) {
  30.         count[i] += count[i - 1];
  31.     }
  32.  
  33.     // 构建输出数组
  34.     for (int i = n - 1; i >= 0; i--) {
  35.         output[count[(arr[i] / exp) % 10] - 1] = arr[i];
  36.         count[(arr[i] / exp) % 10]--;
  37.     }
  38.  
  39.     // 将输出数组的值复制回原数组
  40.     for (int i = 0; i < n; i++) {
  41.         arr[i] = output[i];
  42.     }
  43. }
  44.  
  45. void radixSort(int arr[], int n) {
  46.     // 找到最大数的位数
  47.     int maxDigitsCount = maxDigits(arr, n);
  48.  
  49.     // 从最低位开始排序
  50.     for (int exp = 1; maxDigitsCount > 0; maxDigitsCount--, exp *= 10) {
  51.         countingSortForRadix(arr, n, exp);
  52.     }
  53. }
  54.  
  55. int main() {
  56.     int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
  57.     int n = sizeof(arr) / sizeof(arr[0]);
  58.     radixSort(arr, n);
  59.     printf("Sorted array: \n");
  60.     for (int i = 0; i < n; i++) {
  61.         printf("%d ", arr[i]);
  62.     }
  63.     printf("\n");
  64.     return 0;
  65. }

 

性能分析

  • 时间复杂度：基数排序的时间复杂度为O(n * k)，其中k是最大数的位数。这是因为每个位数都需要进行一次计数排序，而计数排序的时间复杂度是O(n + k)，在这里k是一个常数，因为每一位的数字范围是固定的（0-9）。
  • 空间复杂度：基数排序的空间复杂度为O(n + k)，其中k是最大数的位数。这是因为需要额外的空间来存储计数数组和输出数组。

总结

在本文的第三部分中，我们介绍了三种特殊场景下的排序算法：计数排序、桶排序和基数排序。这些算法在特定条件下能够提供线性时间复杂度的排序性能。

  • 计数排序适用于整数排序，特别是当数据范围较小的时候。
  • 桶排序适用于数据分布均匀且范围不大的情况。
  • 基数排序适用于整数排序，特别是当数据量较大且位数不多时。

这些算法的时间复杂度都是线性的，但是在某些情况下，它们可能需要额外的空间来存储中间结果。在实际应用中，选择哪种排序算法取决于数据的特性和需求。

总结

本文详细介绍了C语言中常用的排序算法，包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序、计数排序、桶排序和基数排序。每种算法都有其独特的原理和实现方式，同时也有各自的性能特点。

冒泡排序、选择排序和插入排序是基础排序算法，适用于小型数据集。快速排序、归并排序和堆排序是高效的排序算法，适用于大规模数据。计数排序、桶排序和基数排序在特定条件下能够提供线性时间复杂度的排序性能。

在实际应用中，选择哪种排序算法取决于数据的特性和需求。例如，对于小规模数据或者对稳定性有要求的情况，可以选择插入排序或冒泡排序；对于大规模数据，快速排序、归并排序和堆排序是更好的选择；对于特定类型的数据，如整数，可以选择计数排序、桶排序或基数排序。

总之，排序算法是计算机科学中的重要组成部分，理解各种排序算法的原理和性能对于编程和数据处理都非常重要。希望本文能够帮助读者深入理解C语言中的排序算法，并在实际应用中做出合适的选择。

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

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

  

闽ICP备14008679号