• 十种排序方法

    目录

    1.冒泡排序（Bubble Sort）代码实现

    2.选择排序（Selection Sort）代码实现

    3.插入排序（Insertion Sort）

    4.希尔排序（Shell Sort）代码实现

    5.快速排序（Quick Sort）代码实现

    6.归并排序（Merge Sort）代码实现

    7.堆排序（Heap Sort）代码实现

    8.计数排序（Counting Sort）代码实现

    9.桶排序（Bucket Sort）代码实现

    10.基数排序（Radix Sort）代码实现

    在C语言中，有多种排序算法可供选择，每种都有其独特的特点和应用场景。以下是几种常见的排序算法及其在C语言中的总结：

    1. 冒泡排序（Bubble Sort）

    原理：通过重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
    时间复杂度：O(n^2)，其中n是待排序数组的长度。
    空间复杂度：O(1)，只需要常数个额外空间。

    2. 选择排序（Selection Sort）

    原理：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
    时间复杂度：O(n^2)，其中n是待排序数组的长度。
    空间复杂度：O(1)，只需要常数个额外空间。

    3. 插入排序（Insertion Sort）

    原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
    时间复杂度：O(n^2)，最坏情况下；O(n)，最好情况下（已排序数组）。
    空间复杂度：O(1)，只需要常数个额外空间。

    4. 希尔排序（Shell Sort）

    原理：是插入排序的一种更高效的改进版本，也称为缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
    时间复杂度：依赖于增量序列的选择，最坏情况下O(n^2)，最好情况下O(n log n)。空间复杂度：O(1)，只需要常数个额外空间。

    5. 快速排序（Quick Sort）

    原理：通过一次排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
    时间复杂度：O(n log n)，平均情况；O(n^2)，最坏情况下（例如当输入数据已经排序或接近排序时）。
    空间复杂度：O(log n)，递归栈空间；但在最坏情况下需要O(n)的额外空间。

    6. 归并排序（Merge Sort）

    原理：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
    时间复杂度：O(n log n)，其中n是待排序数组的长度。
    空间复杂度：O(n)，需要额外的空间来存储临时数组。

    7. 堆排序（Heap Sort）

    原理：是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
    时间复杂度：O(n log n)，其中n是待排序数组的长度。
    空间复杂度：O(1)，只需要常数个额外空间。

    8. 计数排序（Counting Sort）

    原理：不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
    时间复杂度：O(n+k)，其中k是整数的范围。
    空间复杂度：O(n+k)，需要额外的数组来存储计数。

    9. 桶排序（Bucket Sort）

    原理：是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：首先，要使得数据分散得尽可能均匀；其次，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
    时间复杂度：O(n+n^2/k+k)，其中n是待排序数组的长度，k是桶的数量。当桶的数量接近或等于数组的长度时，退化为O(n^2)。
    空间复杂度：O(n+k)，需要额外的数组来存储桶。

    10. 基数排序（Radix Sort）

    原理：是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
    时间复杂度：O(nk)，其中n是待排序数组的长度，k是数字的位数。
    空间复杂度：O(n+k)，需要额外的数组来存储临时数据。

    1.冒泡排序（Bubble Sort）代码实现

    是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。以下是使用C语言实现的冒泡排序算法：

    1. #include 
    2.  
    3. // 冒泡排序函数
    4. void bubbleSort(int arr[], int n) {
    5.     int i, j, temp;
    6.     for (i = 0; i < n-1; i++) { // 外层循环控制遍历的次数
    7.         for (j = 0; j < n-i-1; j++) { // 内层循环控制每次遍历需要比较的次数
    8.             if (arr[j] > arr[j+1]) { // 如果前一个元素大于后一个元素，则交换
    9.                 temp = arr[j];
    10.                 arr[j] = arr[j+1];
    11.                 arr[j+1] = temp;
    12.             }
    13.         }
    14.     }
    15. }
    16.  
    17. // 打印数组
    18. void printArray(int arr[], int size) {
    19.     int i;
    20.     for (i=0; i < size; i++)
    21.         printf("%d ", arr[i]);
    22.     printf("\n");
    23. }
    24.  
    25. int main() {
    26.     int arr[] = {64, 34, 25, 12, 22, 11, 90};
    27.     int n = sizeof(arr)/sizeof(arr[0]);
    28.     bubbleSort(arr, n);
    29.     printf("Sorted array: \n");
    30.     printArray(arr, n);
    31.     return 0;
    32. }

    在这个示例中，bubbleSort 函数接受一个整数数组 arr 和数组的大小 n 作为参数。然后，它使用两个嵌套的循环来进行排序。外层循环控制遍历的次数，而内层循环则负责每次遍历时的元素比较和可能的交换。如果前一个元素大于后一个元素，则交换它们的位置。

    这个算法的效率并不高，特别是当待排序的数组已经有序或者接近有序时，因为仍然会进行不必要的比较和交换。然而，冒泡排序的实现简单易懂，因此经常被用作教学示例。

    冒泡排序的时间复杂度在最坏的情况下是 O(n^2)，其中 n 是数组的大小。在最好的情况下（即数组已经有序），时间复杂度是 O(n)。然而，由于冒泡排序在实际应用中并不高效，因此它通常不被用于大数据集的排序。

    2.选择排序（Selection Sort）代码实现

    是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

    以下是使用C语言实现的选择排序算法：

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

    在这个示例中，selectionSort 函数接收一个整数数组和数组的大小作为参数。它使用了两层循环。外层循环控制已排序部分的末尾位置，内层循环用于从未排序部分中找到最小元素的位置。一旦找到最小元素的位置，就将其与未排序部分的第一个元素（即当前外循环的索引位置）交换。

    选择排序是不稳定的排序算法，因为在交换过程中，相等元素的相对顺序可能会发生变化。

    选择排序的时间复杂度为 O(n^2)，其中 n 是待排序数组的大小。这是因为对于每一个元素，我们都需要遍历剩余的未排序部分来找到最小（或最大）的元素。因此，选择排序在大数据集上的效率不如一些更先进的排序算法，如快速排序、归并排序或堆排序。但是，由于选择排序的实现简单且易于理解，它在算法教学或小型数据集上仍然很受欢迎。

    3.插入排序（Insertion Sort）

    是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

    以下是使用C语言实现的插入排序算法：

    1. #include 
    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.         /* 将大于key的元素向后移动 */
    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.     return 0;
    26. }

    在这个示例中，insertionSort 函数接收一个整数数组和数组的大小作为参数。它使用两层循环来实现插入排序。外层循环遍历数组中的每个元素（从第二个元素开始），内层循环则将当前元素（称为key）与其前面的元素进行比较，如果前面的元素比key大，则将它们向后移动一位，直到找到key的正确位置或者已经到达数组的开始。然后，将key插入到正确的位置上。

    主函数 main 创建一个整数数组并调用 insertionSort 函数对其进行排序，然后打印排序后的数组。

    4.希尔排序（Shell Sort）代码实现

    是插入排序的一种更高效的改进版本，也称为缩小增量排序。它的基本思想是：先将整个待排序的记录序列分割成为若干子序列（由相隔某个“增量”的记录组成）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

    希尔排序通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

    以下是使用C语言实现的希尔排序算法：

    1. #include 
    2.  
    3. void shellSort(int arr[], int n) {
    4.     int gap, i, j, temp;
    5.     for (gap = n / 2; gap > 0; gap /= 2) { // 初始gap为数组长度的一半，然后逐渐缩小
    6.         for (i = gap; i < n; i++) { // 从gap位置开始，对每个子序列进行插入排序
    7.             temp = arr[i];
    8.             for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
    9.                 arr[j] = arr[j - gap]; // 将大于temp的元素后移
    10.             }
    11.             arr[j] = temp; // 找到temp的插入位置
    12.         }
    13.     }
    14. }
    15.  
    16. int main() {
    17.     int arr[] = {12, 34, 54, 2, 3};
    18.     int n = sizeof(arr) / sizeof(arr[0]);
    19.     shellSort(arr, n);
    20.     printf("Sorted array: \n");
    21.     for (int i = 0; i < n; i++)
    22.         printf("%d ", arr[i]);
    23.     return 0;
    24. }

    在这个示例中，shellSort 函数接收一个整数数组和数组的大小作为参数。它使用一个外部循环来逐渐减小增量（gap），内部循环则对每个由当前gap定义的子序列执行插入排序。初始时，gap通常设置为数组长度的一半，并在每次迭代中除以2（或者其他数）来逐渐减小，直到gap为1，此时算法就退化为普通的插入排序。

    希尔排序的时间复杂度依赖于增量序列的选择，不同的增量序列会导致不同的执行效率。上述示例中使用的增量序列是最简单的递减序列，即每次减半。在实际应用中，可能会使用更复杂的增量序列来提高效率。

    需要注意的是，希尔排序是不稳定的排序算法，即相等的元素在排序后可能会改变其相对顺序。

    5.快速排序（Quick Sort）代码实现

    是一种高效的排序算法，它采用了分治法的思想。快速排序的基本思想是：选择一个基准元素（pivot），通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

    以下是使用C语言实现的快速排序算法：

    1. #include 
    2.  
    3. // 快速排序的划分函数
    4. int partition(int arr[], int low, int high) {
    5.     int pivot = arr[high]; // 选择最右边的元素作为基准
    6.     int i = (low - 1); // 指向小于基准的元素的最后一个位置
    7.  
    8.     for (int j = low; j <= high - 1; j++) {
    9.         // 如果当前元素小于或等于基准
    10.         if (arr[j] <= pivot) {
    11.             i++; // 增加 i
    12.             // 交换 arr[i] 和 arr[j]
    13.             int temp = arr[i];
    14.             arr[i] = arr[j];
    15.             arr[j] = temp;
    16.         }
    17.     }
    18.     // 将基准元素交换到它最终的位置 arr[i+1]
    19.     int temp = arr[i + 1];
    20.     arr[i + 1] = arr[high];
    21.     arr[high] = temp;
    22.     return (i + 1);
    23. }
    24.  
    25. // 快速排序函数
    26. void quickSort(int arr[], int low, int high) {
    27.     if (low < high) {
    28.         /* pi 是分区点，arr[pi] 已经到位 */
    29.         int pi = partition(arr, low, high);
    30.  
    31.         // 分别对基准元素左边的子序列和右边的子序列进行快速排序
    32.         quickSort(arr, low, pi - 1);
    33.         quickSort(arr, pi + 1, high);
    34.     }
    35. }
    36.  
    37. // 打印数组
    38. void printArray(int arr[], int size) {
    39.     int i;
    40.     for (i = 0; i < size; i++)
    41.         printf("%d ", arr[i]);
    42.     printf("\n");
    43. }
    44.  
    45. // 主函数
    46. int main() {
    47.     int arr[] = {10, 7, 8, 9, 1, 5};
    48.     int n = sizeof(arr) / sizeof(arr[0]);
    49.     quickSort(arr, 0, n - 1);
    50.     printf("Sorted array: \n");
    51.     printArray(arr, n);
    52.     return 0;
    53. }

    在这个示例中，quickSort 函数是递归的，它接受一个整数数组 arr 和要排序的数组段的起始 low 和结束 high 索引作为参数。函数首先检查基本情况（即 low 是否小于 high），然后调用 partition 函数来选择一个基准元素并将数组分成两部分。然后，它递归地对基准元素左右两侧的子数组进行快速排序。

    partition 函数负责选择基准元素（在这个例子中是最右边的元素），然后将数组重新排列，使得所有小于基准的元素都在基准的左边，所有大于基准的元素都在基准的右边。函数最后返回基准元素的最终位置。

    快速排序的平均时间复杂度是 O(n log n)，但在最坏的情况下（即每次划分都极度不平衡），时间复杂度会退化为 O(n^2)。然而，通过随机化基准元素的选择或使用三数取中等技巧，可以大大降低最坏情况发生的概率。

    6.归并排序（Merge Sort）代码实现

    是一种典型的分治算法，它将一个大问题分解为两个或更多个小问题，然后递归地解决这些小问题，最后将解决的小问题合并起来，从而完成对整个数据的排序。

    以下是使用C语言实现的归并排序算法：

    1.  
    2. #include 
    3.  
    4. // 合并两个已排序的数组
    5. void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
    6.     int i = 0, j = 0, k = 0;
    7.     while (i < leftSize && j < rightSize) {
    8.         if (left[i] <= right[j]) {
    9.             arr[k++] = left[i++];
    10.         } else {
    11.             arr[k++] = right[j++];
    12.         }
    13.     }
    14.     // 拷贝剩余的元素
    15.     while (i < leftSize) {
    16.         arr[k++] = left[i++];
    17.     }
    18.     while (j < rightSize) {
    19.         arr[k++] = right[j++];
    20.     }
    21. }
    22.  
    23. // 归并排序函数
    24. void mergeSort(int arr[], int left, int right) {
    25.     if (left < right) {
    26.         int mid = left + (right - left) / 2;
    27.         int leftSize = mid - left + 1;
    28.         int rightSize = right - mid;
    29.  
    30.         // 创建临时数组
    31.         int leftArr[leftSize], rightArr[rightSize];
    32.  
    33.         // 拷贝数据到临时数组
    34.         for (int i = 0; i < leftSize; i++) {
    35.             leftArr[i] = arr[left + i];
    36.         }
    37.         for (int j = 0; j < rightSize; j++) {
    38.             rightArr[j] = arr[mid + 1 + j];
    39.         }
    40.  
    41.         // 递归地对左右子数组进行排序
    42.         mergeSort(leftArr, 0, leftSize - 1);
    43.         mergeSort(rightArr, 0, rightSize - 1);
    44.  
    45.         // 合并临时数组回原数组
    46.         merge(arr, leftArr, leftSize, rightArr, rightSize);
    47.     }
    48. }
    49.  
    50. // 打印数组
    51. void printArray(int arr[], int size) {
    52.     for (int i = 0; i < size; i++) {
    53.         printf("%d ", arr[i]);
    54.     }
    55.     printf("\n");
    56. }
    57.  
    58. // 主函数
    59. int main() {
    60.     int arr[] = {12, 11, 13, 5, 6, 7};
    61.     int arrSize = sizeof(arr) / sizeof(arr[0]);
    62.  
    63.     printf("Given array is \n");
    64.     printArray(arr, arrSize);
    65.  
    66.     mergeSort(arr, 0, arrSize - 1);
    67.  
    68.     printf("\nSorted array is \n");
    69.     printArray(arr, arrSize);
    70.  
    71.     return 0;
    72. }

    在这个示例中，mergeSort 函数是递归的，它首先将数组分成两半，然后递归地对这两半进行排序。当递归调用返回时，merge 函数被用来合并两个已排序的子数组，生成一个完整的已排序数组。

    归并排序的时间复杂度是 O(n log n)，其中 n 是数组的大小。这个算法是稳定的，即具有相同值的元素在排序后的相对顺序保持不变。归并排序的空间复杂度取决于实现方式，如果使用了额外的数组来存储临时数据，则空间复杂度为 O(n)。然而，如果原地（in-place）归并排序的变种被实现，则空间复杂度可以降低到 O(log n)（忽略递归栈的额外空间）。但是，原地归并排序通常更加复杂且难以实现。

    7.堆排序（Heap Sort）代码实现

    是一种基于二叉堆这种数据结构所设计的排序算法。它是选择排序的一种有效改进版本，其基本思想是将待排序的序列构造成一个大顶堆（或小顶堆），此时，整个序列的最大值（或最小值）就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值（或最小值）。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

    以下是使用C语言实现的堆排序算法：

    1. #include 
    2.  
    3. // 交换两个元素
    4. void swap(int* a, int* b) {
    5.     int t = *a;
    6.     *a = *b;
    7.     *b = t;
    8. }
    9.  
    10. // 堆调整，从当前节点开始向下调整
    11. void heapify(int arr[], int n, int i) {
    12.     int largest = i; // 初始化largest为根
    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.  
    28.         // 递归地调整受影响的子堆
    29.         heapify(arr, n, largest);
    30.     }
    31. }
    32.  
    33. // 堆排序
    34. void heapSort(int arr[], int n) {
    35.     // 构建一个大顶堆
    36.     for (int i = n / 2 - 1; i >= 0; i--)
    37.         heapify(arr, n, i);
    38.  
    39.     // 一个个从堆顶取出元素
    40.     for (int i = n - 1; i >= 0; i--) {
    41.         // 将当前最大的元素arr[0]和arr[i]交换
    42.         swap(&arr[0], &arr[i]);
    43.  
    44.         // 重新调整堆
    45.         heapify(arr, i, 0);
    46.     }
    47. }
    48.  
    49. int main() {
    50.     int arr[] = {12, 11, 13, 5, 6, 7};
    51.     int n = sizeof(arr) / sizeof(arr[0]);
    52.     heapSort(arr, n);
    53.     printf("Sorted array: \n");
    54.     for (int i = 0; i < n; i++)
    55.         printf("%d ", arr[i]);
    56.     return 0;
    57. }

    在这个示例中，heapSort 函数首先通过 heapify 函数将数组构造成一个大顶堆。然后，它将堆顶元素（即当前的最大值）与数组的最后一个元素交换，并将剩余的元素重新调整为大顶堆。这个过程重复进行，直到整个数组有序。

    堆排序的时间复杂度是 O(n log n)，其中 n 是待排序数组的大小。这是因为构建堆的时间复杂度是 O(n)，并且调整堆和交换元素的操作在 n-1 次循环中发生，每次循环的复杂度是 O(log n)。因此，堆排序是一种非常高效的排序算法。同时，堆排序是一种原地排序算法，因为它只需要常数个额外的空间来存储临时数据。

    8.计数排序（Counting Sort）代码实现

    是一种非基于比较的排序算法，适用于一定范围内的整数排序。其核心思想是利用一个额外的数组（计数数组）来记录每个元素出现的次数，然后根据计数数组来将元素放到正确的位置上。

    以下是计数排序在C语言中的实现总结：1. 计数排序的基本步骤
    找出待排序的数组中最大和最小的元素：为了确定计数数组的长度和元素的映射范围。
    统计数组中每个值为 i 的元素出现的次数：遍历输入数组，增加计数数组中对应索引的计数。
    对计数数组进行累加操作：从计数数组的第二个元素开始，每个元素都加上前一个元素的值，得到一个新数组。新数组的第 i 个元素表示原数组中值小于等于 i 的元素个数。
    根据计数数组得到排序后的数组：从后往前遍历输入数组，根据计数数组确定当前元素在排序后数组中的位置，并将元素放到该位置。
    计数数组在排序后不再需要，可以释放（如果是在动态分配的内存中）。
    2. C语言实现示例

    1.  
    2. #include 
    3. #include 
    4.  
    5. void countingSort(int arr[], int n) {
    6.     int max = arr[0];
    7.     int min = arr[0];
    8.     for (int i = 1; i < n; i++) {
    9.         if (arr[i] > max) max = arr[i];
    10.         if (arr[i] < min) min = arr[i];
    11.     }
    12.     
    13.     int range = max - min + 1;
    14.     int count[range];
    15.     for (int i = 0; i < range; i++) {
    16.         count[i] = 0;
    17.     }
    18.     
    19.     for (int i = 0; i < n; i++) {
    20.         count[arr[i] - min]++;
    21.     }
    22.     
    23.     for (int i = 1; i < range; i++) {
    24.         count[i] += count[i - 1];
    25.     }
    26.     
    27.     int output[n];
    28.     for (int i = n - 1; i >= 0; i--) {
    29.         output[count[arr[i] - min] - 1] = arr[i];
    30.         count[arr[i] - min]--;
    31.     }
    32.     
    33.     // 将排序后的数组复制回原数组（如果需要）
    34.     for (int i = 0; i < n; i++) {
    35.         arr[i] = output[i];
    36.     }
    37. }
    38.  
    39. int main() {
    40.     int arr[] = {4, 2, 2, 8, 3, 3, 1};
    41.     int n = sizeof(arr) / sizeof(arr[0]);
    42.     countingSort(arr, n);
    43.     for (int i = 0; i < n; i++) {
    44.         printf("%d ", arr[i]);
    45.     }
    46.     return 0;
    47. }

    3. 计数排序的适用场景
    数据范围小：计数排序的复杂度取决于数据范围的大小，而不是数据量的大小。如果数据范围很大，计数数组也会很大，会占用大量内存。
    非负整数：计数排序通常用于非负整数排序，因为需要确定一个明确的范围来构建计数数组。如果包含负数或浮点数，需要进行额外的处理。
    稳定排序：计数排序是稳定的排序算法，即相等的元素在排序后保持原有的顺序。

    9.桶排序（Bucket Sort）代码实现

    是一种分配式排序算法，它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：首先，要使得数据分散得尽可能均匀；其次，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

    以下是桶排序在C语言中的实现总结：

    1. 桶排序的基本步骤
    确定桶的数量和大小：根据待排序数组的范围确定桶的数量，以及每个桶所能容纳的范围。
    初始化桶：创建一个空的桶数组（或者使用其他数据结构如链表、动态数组等），每个桶都初始化为空。
    分配元素到桶中：遍历待排序数组，将每个元素分配到对应的桶中。
    对每个桶中的元素进行排序：可以使用任何有效的排序算法对每个桶中的元素进行排序，如插入排序、快速排序等。
    合并桶中的元素：按照桶的顺序，将桶中的元素依次取出，合并成一个有序数组。
    2. C语言实现示例

    这里假设我们处理的是非负整数，并且知道数据的最大值 maxValue。

    1.  
    2. #include 
    3. #include 
    4.  
    5. void bucketSort(int arr[], int n, int maxValue) {
    6.     // 桶的数量
    7.     int bucketSize = maxValue / n + 1;
    8.     int bucketCount = (maxValue / bucketSize) + 1;
    9.     
    10.     // 初始化桶
    11.     int* buckets = (int*)calloc(bucketCount, sizeof(int*));
    12.     for (int i = 0; i < bucketCount; i++) {
    13.         buckets[i] = (int*)malloc(sizeof(int) * bucketSize);
    14.         int j;
    15.         for (j = 0; j < bucketSize; j++) {
    16.             buckets[i][j] = -1; // 标记为未使用
    17.         }
    18.     }
    19.     
    20.     // 将元素分配到桶中
    21.     for (int i = 0; i < n; i++) {
    22.         int index = arr[i] / bucketSize;
    23.         int offset = arr[i] % bucketSize;
    24.         int j;
    25.         for (j = 0; j < bucketSize; j++) {
    26.             if (buckets[index][j] == -1) {
    27.                 buckets[index][j] = arr[i];
    28.                 break;
    29.             }
    30.         }
    31.     }
    32.     
    33.     // 对每个桶进行排序（这里使用插入排序作为示例）
    34.     for (int i = 0; i < bucketCount; i++) {
    35.         int k = 0;
    36.         while (buckets[i][k] != -1) {
    37.             int j = k + 1;
    38.             while (j < bucketSize && buckets[i][j] != -1) {
    39.                 if (buckets[i][j] < buckets[i][j - 1]) {
    40.                     int temp = buckets[i][j];
    41.                     buckets[i][j] = buckets[i][j - 1];
    42.                     buckets[i][j - 1] = temp;
    43.                 }
    44.                 j++;
    45.             }
    46.             k++;
    47.         }
    48.     }
    49.     
    50.     // 合并桶中的元素
    51.     int index = 0;
    52.     for (int i = 0; i < bucketCount; i++) {
    53.         for (int j = 0; j < bucketSize; j++) {
    54.             if (buckets[i][j] != -1) {
    55.                 arr[index++] = buckets[i][j];
    56.             }
    57.         }
    58.     }
    59.     
    60.     // 释放桶的内存
    61.     for (int i = 0; i < bucketCount; i++) {
    62.         free(buckets[i]);
    63.     }
    64.     free(buckets);
    65. }
    66.  
    67. int main() {
    68.     int arr[] = {4, 2, 2, 8, 3, 3, 1, 10};
    69.     int n = sizeof(arr) / sizeof(arr[0]);
    70.     int maxValue = 10; // 假设已知数据的最大值
    71.     bucketSort(arr, n, maxValue);
    72.     for (int i = 0; i < n; i++) {
    73.         printf("%d ", arr[i]);
    74.     }
    75.     return 0;
    76. }

    3. 桶排序的适用场景
    数据分布均匀：当待排序的数据分布比较均匀时，桶排序的效率会非常高。
    数据范围大但数据量不大：桶排序适合处理数据范围大但数据量不大的情况。如果数据量非常大，桶的数量也会非常大，这可能会导致内存消耗过多。
    非负整数：桶排序通常用于非负整数排序，如果包含负数或浮点数，需要进行额外的处理。

    10.基数排序（Radix Sort）代码实现

    是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序使用了计数排序（Counting Sort）作为子程序。

    基数排序有两种常见的实现方式：最低位优先（Least Significant Digit first, LSD）和最高位优先（Most Significant Digit first, MSD）。通常，LSD 更常用，因为它可以从低位到高位依次排序，而不需要像 MSD 那样进行递归或栈操作。

    以下是基数排序的 C 语言实现（使用 LSD 方法）：

    1.  
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. // 假设我们处理的是非负整数，并且知道最大的数的位数 maxDigit
    7. void countingSort(int arr[], int n, int exp) {
    8.     int output[n];
    9.     int count[10] = {0};
    10.  
    11.     // 存储每个元素的出现次数
    12.     for (int i = 0; i < n; i++) {
    13.         count[(arr[i] / exp) % 10]++;
    14.     }
    15.  
    16.     // 更改 count[i] 使得 count[i] 现在包含小于或等于 i 的数字的数量
    17.     for (int i = 1; i < 10; i++) {
    18.         count[i] += count[i - 1];
    19.     }
    20.  
    21.     // 生成输出数组
    22.     for (int i = n - 1; i >= 0; i--) {
    23.         output[count[(arr[i] / exp) % 10] - 1] = arr[i];
    24.         count[(arr[i] / exp) % 10]--;
    25.     }
    26.  
    27.     // 复制回原数组
    28.     for (int i = 0; i < n; i++) {
    29.         arr[i] = output[i];
    30.     }
    31. }
    32.  
    33. // 基数排序函数
    34. void radixsort(int arr[], int n) {
    35.     // 找到数组中最大的数
    36.     int max = arr[0];
    37.     for (int i = 1; i < n; i++) {
    38.         if (arr[i] > max) {
    39.             max = arr[i];
    40.         }
    41.     }
    42.  
    43.     // 计算最大数的位数
    44.     int maxDigit = 0;
    45.     while (max > 0) {
    46.         max /= 10;
    47.         maxDigit++;
    48.     }
    49.  
    50.     // 对每一位进行计数排序
    51.     for (int exp = 1; exp <= maxDigit; exp *= 10) {
    52.         countingSort(arr, n, exp);
    53.     }
    54. }
    55.  
    56. int main() {
    57.     int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    58.     int n = sizeof(arr) / sizeof(arr[0]);
    59.     radixsort(arr, n);
    60.     printf("Sorted array: \n");
    61.     for (int i = 0; i < n; i++) {
    62.         printf("%d ", arr[i]);
    63.     }
    64.     return 0;
    65. }

    在这个示例中，我们首先通过 countingSort 函数对数组的每个位进行排序。然后，在 radixsort 函数中，我们确定最大数的位数，并对每一位调用 countingSort 函数。最后，在 main 函数中，我们测试基数排序并打印排序后的数组。

  • 相关阅读:
    2022“杭电杯”中国大学生算法设计超级联赛（4）签到题5题
    A-Level Biology 真题及解析（2）
    主流架构(gcc、msvc、x86、x64、arm)中double与float浮点数保留精度(末尾清零)
    贪心算法 Problem M 1012 已知幂和结果求底数
    专利说明书怎么写？
    SSM项目 - Online Music Player（在线音乐播放器）- 前端页面设计 - 细节狂魔
    tomcat 的日志详解
    基于php食堂外卖系统
    golang查看CPU使用率与内存及源码中的//go:指令
    Vue 3 中的 ref 和 reactive 有什么区别？
  • 原文地址：https://blog.csdn.net/2401_83427936/article/details/139596143