当前位置：首页 > news >正文

数组排序算法

news 来源：原创 2025/5/15 11:23:22

数组排序算法

用C语言实现的数组排序算法。

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	是否稳定	适用场景
Quick	O(n log n)	O(n²)	O(n log n)	O(log n)	不稳定	大规模数据，通用排序
Bubble	O(n²)	O(n²)	O(n)	O(1)	稳定	小规模数据，教学用途
Insert	O(n²)	O(n²)	O(n)	O(1)	稳定	小规模或部分有序数据
Select	O(n²)	O(n²)	O(n²)	O(1)	不稳定	小规模数据，简单实现
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定	大规模数据，稳定排序需求
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定	大规模数据，原地排序需求
Count	O(n + k)	O(n + k)	O(n + k)	O(n + k)	稳定	小范围整数排序
Radix	O(d(n + k))	O(d(n + k))	O(d(n + k))	O(n + k)	稳定	整数或字符串排序，位数较小
Bucket	O(n + k)	O(n²)	O(n)	O(n + k)	稳定	均匀分布的数据
Shell	O(n log n)	O(n²)	O(n log n)	O(1)	不稳定	中等规模数据，改进的插入排序

快速排序

快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略。以下是使用C语言实现数组的快速排序的代码：

#include <stdio.h>// 交换两个元素的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 分区函数，返回分区点的索引
int partition(int arr[], int low, int high) {int pivot = arr[high];  // 选择最后一个元素作为基准int i = (low - 1);  // i是较小元素的索引for (int j = low; j <= high - 1; j++) {// 如果当前元素小于或等于基准if (arr[j] <= pivot) {i++;  // 增加较小元素的索引swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);  // 将基准元素放到正确的位置return (i + 1);
}// 快速排序的递归函数
void quickSort(int arr[], int low, int high) {if (low < high) {// pi是分区点，arr[pi]已经排好序int pi = partition(arr, low, high);// 递归地对分区点左边和右边的子数组进行排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);quickSort(arr, 0, n - 1);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

swap函数：用于交换两个元素的值。
partition函数：选择数组的最后一个元素作为基准（pivot），然后将数组分为两部分，左边部分的元素都小于或等于基准，右边部分的元素都大于基准。最后返回基准元素的正确位置。
quickSort函数：递归地对数组进行排序。首先通过partition函数找到分区点，然后对分区点左边和右边的子数组分别进行快速排序。
printArray函数：用于打印数组的内容。
main函数：测试快速排序的实现。

运行结果：

原始数组: 
10 7 8 9 1 5 
排序后的数组: 
1 5 7 8 9 10

时间复杂度：

平均时间复杂度：O(n log n)
最坏时间复杂度：O(n^2)（当数组已经有序或所有元素相等时）
空间复杂度：O(log n)（递归栈的深度）

快速排序是一种非常高效的排序算法，尤其适用于大规模数据的排序。

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历数组，比较相邻的元素并交换它们的位置，直到整个数组有序。以下是使用C语言实现数组的冒泡排序的代码：

#include <stdio.h>// 交换两个元素的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 冒泡排序函数
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {  // 外层循环控制遍历次数for (int j = 0; j < n - i - 1; j++) {  // 内层循环比较相邻元素if (arr[j] > arr[j + 1]) {swap(&arr[j], &arr[j + 1]);  // 如果顺序错误，交换元素}}}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);bubbleSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

swap函数：用于交换两个元素的值。
bubbleSort函数：
- 外层循环控制遍历次数，每次遍历会将当前未排序部分的最大值“冒泡”到正确的位置。
- 内层循环比较相邻元素，如果顺序错误（前一个元素大于后一个元素），则交换它们。
printArray函数：用于打印数组的内容。
main函数：测试冒泡排序的实现。

运行结果：

原始数组: 
64 34 25 12 22 11 90 
排序后的数组: 
11 12 22 25 34 64 90

优化版本：

如果某次遍历中没有发生任何交换，说明数组已经有序，可以提前结束排序。以下是优化后的冒泡排序代码：

void bubbleSortOptimized(int arr[], int n) {int swapped;  // 标记是否发生交换for (int i = 0; i < n - 1; i++) {swapped = 0;  // 每次遍历前重置标记for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(&arr[j], &arr[j + 1]);swapped = 1;  // 发生交换，标记为1}}if (swapped == 0) {  // 如果没有发生交换，说明数组已经有序break;}}
}

时间复杂度：

最坏情况：O(n²)（当数组完全逆序时）
最好情况：O(n)（当数组已经有序时，优化版本可以达到）
平均情况：O(n²)

空间复杂度：

O(1)（原地排序，不需要额外空间）

冒泡排序虽然简单，但在实际应用中效率较低，通常用于教学或小规模数据的排序。对于大规模数据，更高效的排序算法（如快速排序、归并排序等）更为适用。

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是使用C语言实现数组的插入排序的代码：

插入排序代码实现

#include <stdio.h>// 插入排序函数
void insertionSort(int arr[], int n) {int i, j, key;for (i = 1; i < n; i++) {key = arr[i];  // 当前需要插入的元素j = i - 1;// 将比key大的元素向后移动while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;  // 插入key到正确位置}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);insertionSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

insertionSort函数：
- 从第二个元素开始（i = 1），将当前元素key插入到已排序部分的正确位置。
- 使用while循环将比key大的元素向后移动，直到找到key的正确位置。
- 将key插入到正确位置。
printArray函数：用于打印数组的内容。
main函数：测试插入排序的实现。

运行结果：

原始数组: 
12 11 13 5 6 
排序后的数组: 
5 6 11 12 13

时间复杂度：

最坏情况：O(n²)（当数组完全逆序时）
最好情况：O(n)（当数组已经有序时）
平均情况：O(n²)

空间复杂度：

O(1)（原地排序，不需要额外空间）

插入排序的特点：

适合小规模数据：对于小规模数据或部分有序的数据，插入排序的效率较高。
稳定排序：插入排序是稳定的排序算法，相同元素的相对顺序不会改变。
简单直观：实现简单，易于理解和实现。

优化版本：

插入排序可以通过二分查找来优化查找插入位置的过程，将查找时间从O(n)优化到O(log n)，但整体时间复杂度仍然是O(n²)。

// 使用二分查找优化插入排序
void insertionSortOptimized(int arr[], int n) {int i, j, key, low, high, mid;for (i = 1; i < n; i++) {key = arr[i];low = 0;high = i - 1;// 使用二分查找找到插入位置while (low <= high) {mid = (low + high) / 2;if (arr[mid] > key) {high = mid - 1;} else {low = mid + 1;}}// 将元素向后移动for (j = i - 1; j >= low; j--) {arr[j + 1] = arr[j];}arr[low] = key;  // 插入key到正确位置}
}

插入排序在实际应用中常用于小规模数据排序或作为其他排序算法（如快速排序、归并排序）的辅助排序方法。

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每次从未排序部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。以下是使用C语言实现数组的选择排序的代码：

选择排序代码实现

#include <stdio.h>// 交换两个元素的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 选择排序函数
void selectionSort(int arr[], int n) {int i, j, min_idx;for (i = 0; i < n - 1; i++) {min_idx = i;  // 假设当前索引i是最小元素的索引// 在未排序部分中找到最小元素的索引for (j = i + 1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 将找到的最小元素与当前元素交换if (min_idx != i) {swap(&arr[min_idx], &arr[i]);}}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {64, 25, 12, 22, 11};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);selectionSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

swap函数：用于交换两个元素的值。
selectionSort函数：
- 外层循环从第一个元素开始，依次选择未排序部分的最小元素。
- 内层循环在未排序部分中找到最小元素的索引。
- 将找到的最小元素与当前元素交换。
printArray函数：用于打印数组的内容。
main函数：测试选择排序的实现。

运行结果：

原始数组: 
64 25 12 22 11 
排序后的数组: 
11 12 22 25 64

时间复杂度：

最坏情况：O(n²)（无论数组是否有序，都需要进行完整的比较和交换）
最好情况：O(n²)（即使数组已经有序，仍然需要进行完整的比较）
平均情况：O(n²)

空间复杂度：

O(1)（原地排序，不需要额外空间）

选择排序的特点：

简单直观：实现简单，易于理解和实现。
不稳定排序：选择排序是不稳定的排序算法，可能会改变相同元素的相对顺序。
适合小规模数据：对于小规模数据，选择排序的效率尚可，但对于大规模数据效率较低。

优化版本：

选择排序的优化空间较小，但可以通过同时选择最小和最大元素来减少外层循环的次数。

// 优化版本：同时选择最小和最大元素
void selectionSortOptimized(int arr[], int n) {int i, j, min_idx, max_idx;for (i = 0; i < n / 2; i++) {min_idx = i;max_idx = i;// 在未排序部分中找到最小和最大元素的索引for (j = i + 1; j < n - i; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}if (arr[j] > arr[max_idx]) {max_idx = j;}}// 将最小元素放到前面if (min_idx != i) {swap(&arr[min_idx], &arr[i]);}// 如果最大元素的位置被影响，需要更新max_idxif (max_idx == i) {max_idx = min_idx;}// 将最大元素放到后面if (max_idx != n - i - 1) {swap(&arr[max_idx], &arr[n - i - 1]);}}
}

选择排序虽然简单，但在实际应用中效率较低，通常用于教学或小规模数据的排序。对于大规模数据，更高效的排序算法（如快速排序、归并排序等）更为适用。

归并排序

归并排序（Merge Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略。它的核心思想是将数组分成两个子数组，分别对子数组进行排序，然后将排序后的子数组合并成一个有序数组。以下是使用C语言实现数组的归并排序的代码：

归并排序代码实现

#include <stdio.h>
#include <stdlib.h>// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {int i, j, k;int n1 = mid - left + 1;  // 左子数组的大小int n2 = right - mid;     // 右子数组的大小// 创建临时数组int* L = (int*)malloc(n1 * sizeof(int));  // 左子数组int* R = (int*)malloc(n2 * sizeof(int));  // 右子数组// 将数据复制到临时数组for (i = 0; i < n1; i++) {L[i] = arr[left + i];}for (j = 0; j < n2; j++) {R[j] = arr[mid + 1 + j];}// 合并临时数组到原数组i = 0;  // 左子数组的索引j = 0;  // 右子数组的索引k = left;  // 合并后数组的索引while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 复制左子数组剩余的元素while (i < n1) {arr[k] = L[i];i++;k++;}// 复制右子数组剩余的元素while (j < n2) {arr[k] = R[j];j++;k++;}// 释放临时数组的内存free(L);free(R);
}// 归并排序的递归函数
void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;  // 计算中间位置// 递归地对左子数组和右子数组进行排序mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 合并两个有序子数组merge(arr, left, mid, right);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);mergeSort(arr, 0, n - 1);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

merge函数：
- 合并两个有序子数组L和R到原数组arr中。
- 使用临时数组存储子数组的数据，然后按顺序合并到原数组。
mergeSort函数：
- 递归地将数组分成两个子数组，分别对子数组进行排序。
- 调用merge函数合并两个有序子数组。
printArray函数：用于打印数组的内容。
main函数：测试归并排序的实现。

运行结果：

原始数组: 
12 11 13 5 6 7 
排序后的数组: 
5 6 7 11 12 13

时间复杂度：

最坏情况：O(n log n)
最好情况：O(n log n)
平均情况：O(n log n)

空间复杂度：

O(n)（需要额外的临时数组存储数据）

归并排序的特点：

稳定排序：归并排序是稳定的排序算法，相同元素的相对顺序不会改变。
适合大规模数据：归并排序的时间复杂度为O(n log n)，适合处理大规模数据。
分治法思想：通过递归将问题分解为更小的子问题，然后合并结果。

优化版本：

归并排序可以通过以下方式优化：

小规模数据使用插入排序：当子数组规模较小时，插入排序的效率更高。
避免频繁的内存分配：可以预先分配一个临时数组，避免在每次合并时分配内存。

// 优化版本：预先分配临时数组
void mergeSortOptimized(int arr[], int left, int right, int* temp) {if (left < right) {int mid = left + (right - left) / 2;// 递归地对左子数组和右子数组进行排序mergeSortOptimized(arr, left, mid, temp);mergeSortOptimized(arr, mid + 1, right, temp);// 合并两个有序子数组merge(arr, left, mid, right);}
}

归并排序是一种非常高效的排序算法，尤其适用于需要稳定排序的场景或处理大规模数据。

堆排序

堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的排序算法。它的核心思想是将数组构建成一个最大堆（或最小堆），然后逐步将堆顶元素（最大值或最小值）与堆的最后一个元素交换，并调整堆，直到整个数组有序。以下是使用C语言实现数组的堆排序的代码：

堆排序代码实现

#include <stdio.h>// 交换两个元素的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 调整堆，使其满足最大堆的性质
void heapify(int arr[], int n, int i) {int largest = i;  // 初始化最大值的索引为根节点int left = 2 * i + 1;  // 左子节点的索引int right = 2 * i + 2;  // 右子节点的索引// 如果左子节点比根节点大，更新最大值的索引if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子节点比当前最大值大，更新最大值的索引if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是根节点，交换根节点和最大值，并递归调整堆if (largest != i) {swap(&arr[i], &arr[largest]);heapify(arr, n, largest);}
}// 堆排序函数
void heapSort(int arr[], int n) {// 构建最大堆（从最后一个非叶子节点开始）for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐步将堆顶元素（最大值）与堆的最后一个元素交换，并调整堆for (int i = n - 1; i > 0; i--) {swap(&arr[0], &arr[i]);  // 将堆顶元素与堆的最后一个元素交换heapify(arr, i, 0);      // 调整堆，使其满足最大堆的性质}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);heapSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

swap函数：用于交换两个元素的值。
heapify函数：
- 调整堆，使其满足最大堆的性质。
- 从根节点开始，比较根节点与其左右子节点，找到最大值。
- 如果最大值不是根节点，交换根节点和最大值，并递归调整堆。
heapSort函数：
- 构建最大堆：从最后一个非叶子节点开始，逐步调整堆。
- 逐步将堆顶元素（最大值）与堆的最后一个元素交换，并调整堆。
printArray函数：用于打印数组的内容。
main函数：测试堆排序的实现。

运行结果：

原始数组: 
12 11 13 5 6 7 
排序后的数组: 
5 6 7 11 12 13

时间复杂度：

建堆过程：O(n)
每次调整堆：O(log n)
总时间复杂度：O(n log n)

空间复杂度：

O(1)（原地排序，不需要额外空间）

堆排序的特点：

不稳定排序：堆排序是不稳定的排序算法，可能会改变相同元素的相对顺序。
适合大规模数据：堆排序的时间复杂度为O(n log n)，适合处理大规模数据。
基于二叉堆：利用二叉堆的性质实现排序。

优化版本：

堆排序的优化空间较小，但可以通过以下方式改进：

使用最小堆：如果需要升序排序，可以使用最小堆。
减少交换次数：在调整堆时，可以减少不必要的交换操作。

堆排序是一种高效的排序算法，尤其适用于需要原地排序的场景或处理大规模数据。

计数排序

计数排序（Counting Sort）是一种非比较型整数排序算法。它的核心思想是通过统计数组中每个元素的出现次数，然后根据统计结果将元素放回正确的位置。计数排序适用于元素范围较小且已知的情况。以下是使用C语言实现数组的计数排序的代码：

计数排序代码实现

#include <stdio.h>
#include <stdlib.h>// 计数排序函数
void countingSort(int arr[], int n) {// 找到数组中的最大值int max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) {max = arr[i];}}// 创建计数数组，并初始化为0int* count = (int*)calloc(max + 1, sizeof(int));// 统计每个元素的出现次数for (int i = 0; i < n; i++) {count[arr[i]]++;}// 将计数数组转换为前缀和数组for (int i = 1; i <= max; i++) {count[i] += count[i - 1];}// 创建输出数组int* output = (int*)malloc(n * sizeof(int));// 从后向前遍历原数组，将元素放入输出数组的正确位置for (int i = n - 1; i >= 0; i--) {output[count[arr[i]] - 1] = arr[i];count[arr[i]]--;}// 将输出数组的内容复制回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}// 释放动态分配的内存free(count);free(output);
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {4, 2, 2, 8, 3, 3, 1};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);countingSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

countingSort函数：
- 找到数组中的最大值，确定计数数组的大小。
- 创建计数数组，统计每个元素的出现次数。
- 将计数数组转换为前缀和数组，表示每个元素在输出数组中的位置。
- 从后向前遍历原数组，将元素放入输出数组的正确位置。
- 将输出数组的内容复制回原数组。
printArray函数：用于打印数组的内容。
main函数：测试计数排序的实现。

运行结果：

原始数组: 
4 2 2 8 3 3 1 
排序后的数组: 
1 2 2 3 3 4 8

时间复杂度：

时间复杂度：O(n + k)，其中n是数组长度，k是数组中元素的最大值。
空间复杂度：O(n + k)（需要额外的计数数组和输出数组）。

计数排序的特点：

非比较排序：计数排序不直接比较元素的大小，而是通过统计元素的出现次数进行排序。
稳定排序：计数排序是稳定的排序算法，相同元素的相对顺序不会改变。
适合小范围整数排序：计数排序适用于元素范围较小且已知的情况。

优化版本：

计数排序的优化可以通过以下方式实现：

减少空间占用：如果元素范围较大，可以使用哈希表或其他方法减少计数数组的大小。
处理负数：如果需要处理负数，可以将数组中的元素统一加上一个偏移量，使其变为非负数。

以下是处理负数的优化版本：

void countingSortWithNegative(int arr[], int n) {// 找到数组中的最小值和最大值int min = arr[0], max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] < min) {min = arr[i];}if (arr[i] > max) {max = arr[i];}}// 计算偏移量int range = max - min + 1;// 创建计数数组，并初始化为0int* count = (int*)calloc(range, sizeof(int));// 统计每个元素的出现次数for (int i = 0; i < n; i++) {count[arr[i] - min]++;}// 将计数数组转换为前缀和数组for (int i = 1; i < range; i++) {count[i] += count[i - 1];}// 创建输出数组int* output = (int*)malloc(n * sizeof(int));// 从后向前遍历原数组，将元素放入输出数组的正确位置for (int i = n - 1; i >= 0; i--) {output[count[arr[i] - min] - 1] = arr[i];count[arr[i] - min]--;}// 将输出数组的内容复制回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}// 释放动态分配的内存free(count);free(output);
}

计数排序是一种高效的排序算法，尤其适用于元素范围较小的情况。对于元素范围较大的情况，可以考虑使用其他排序算法（如快速排序或归并排序）。

基数排序

基数排序（Radix Sort）是一种非比较型整数排序算法。它的核心思想是将整数按位数切割成不同的数字，然后按每个位数分别进行排序（通常使用计数排序或桶排序作为子排序算法）。基数排序适用于整数或字符串的排序。以下是使用C语言实现数组的基数排序的代码：

基数排序代码实现

#include <stdio.h>
#include <stdlib.h>// 获取数组中的最大值
int getMax(int arr[], int n) {int max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) {max = arr[i];}}return max;
}// 使用计数排序对数组按指定位数进行排序
void countingSort(int arr[], int n, int exp) {int* output = (int*)malloc(n * sizeof(int));  // 输出数组int count[10] = {0};  // 计数数组，初始化为0// 统计每个数字出现的次数for (int i = 0; i < n; i++) {count[(arr[i] / exp) % 10]++;}// 将计数数组转换为前缀和数组for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 从后向前遍历原数组，将元素放入输出数组的正确位置for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}// 将输出数组的内容复制回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}// 释放动态分配的内存free(output);
}// 基数排序函数
void radixSort(int arr[], int n) {int max = getMax(arr, n);  // 获取数组中的最大值// 对每个位数进行计数排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSort(arr, n, exp);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);radixSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

getMax函数：获取数组中的最大值，用于确定需要排序的位数。
countingSort函数：
- 对数组按指定位数（exp）进行计数排序。
- 使用计数数组统计每个数字出现的次数，并将其转换为前缀和数组。
- 从后向前遍历原数组，将元素放入输出数组的正确位置。
radixSort函数：
- 获取数组中的最大值，确定需要排序的位数。
- 对每个位数调用countingSort函数进行排序。
printArray函数：用于打印数组的内容。
main函数：测试基数排序的实现。

运行结果：

原始数组: 
170 45 75 90 802 24 2 66 
排序后的数组: 
2 24 45 66 75 90 170 802

时间复杂度：

时间复杂度：O(d * (n + k))，其中d是最大数字的位数，n是数组长度，k是基数（通常为10）。
空间复杂度：O(n + k)（需要额外的计数数组和输出数组）。

基数排序的特点：

非比较排序：基数排序不直接比较元素的大小，而是通过按位数排序。
稳定排序：基数排序是稳定的排序算法，相同元素的相对顺序不会改变。
适合整数或字符串排序：基数排序适用于整数或固定长度的字符串排序。

优化版本：

基数排序的优化空间较小，但可以通过以下方式改进：

使用桶排序：在某些情况下，可以使用桶排序代替计数排序作为子排序算法。
处理负数：如果需要处理负数，可以将数组分为正数和负数两部分，分别进行基数排序。

基数排序是一种高效的排序算法，尤其适用于整数或字符串的排序场景。

桶排序

桶排序（Bucket Sort）是一种分布式排序算法，它将数组分到有限数量的桶中，每个桶再分别排序（通常使用插入排序或其他排序算法），最后将各个桶中的元素合并成有序数组。以下是使用C语言实现数组的桶排序的代码：

桶排序代码实现

#include <stdio.h>
#include <stdlib.h>// 定义桶的数量
#define BUCKET_SIZE 10// 定义链表节点
typedef struct Node {float data;struct Node* next;
} Node;// 插入节点到链表中（按升序插入）
Node* insert(Node* head, float value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;if (head == NULL || head->data >= value) {newNode->next = head;head = newNode;} else {Node* current = head;while (current->next != NULL && current->next->data < value) {current = current->next;}newNode->next = current->next;current->next = newNode;}return head;
}// 桶排序函数
void bucketSort(float arr[], int n) {// 创建桶数组Node* buckets[BUCKET_SIZE] = {NULL};// 将元素分配到桶中for (int i = 0; i < n; i++) {int bucketIndex = (int)(arr[i] * BUCKET_SIZE);  // 计算桶的索引buckets[bucketIndex] = insert(buckets[bucketIndex], arr[i]);}// 将桶中的元素合并到原数组int index = 0;for (int i = 0; i < BUCKET_SIZE; i++) {Node* current = buckets[i];while (current != NULL) {arr[index++] = current->data;current = current->next;}}
}// 打印数组
void printArray(float arr[], int size) {for (int i = 0; i < size; i++) {printf("%.2f ", arr[i]);}printf("\n");
}// 主函数
int main() {float arr[] = {0.42, 0.32, 0.75, 0.12, 0.89, 0.63, 0.25, 0.55};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);bucketSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

Node结构体：定义链表节点，用于存储桶中的元素。
insert函数：
- 将元素按升序插入到链表中。
- 如果链表为空或当前元素小于链表头节点，则插入到链表头部。
- 否则，遍历链表找到合适的插入位置。
bucketSort函数：
- 创建桶数组，每个桶是一个链表。
- 将数组中的元素分配到对应的桶中。
- 对每个桶中的元素进行排序（通过插入排序实现）。
- 将各个桶中的元素合并到原数组。
printArray函数：用于打印数组的内容。
main函数：测试桶排序的实现。

运行结果：

原始数组: 
0.42 0.32 0.75 0.12 0.89 0.63 0.25 0.55 
排序后的数组: 
0.12 0.25 0.32 0.42 0.55 0.63 0.75 0.89

时间复杂度：

平均情况：O(n + k)，其中n是数组长度，k是桶的数量。
最坏情况：O(n²)（当所有元素都分配到同一个桶时）。
最好情况：O(n)（当元素均匀分布在各个桶中时）。

空间复杂度：

O(n + k)（需要额外的桶数组和链表节点）。

桶排序的特点：

分布式排序：将元素分配到多个桶中，分别排序后再合并。
适合均匀分布的数据：当元素均匀分布在各个桶中时，桶排序的效率较高。
稳定排序：如果使用的子排序算法是稳定的，桶排序也是稳定的。

优化版本：

桶排序的优化可以通过以下方式实现：

动态调整桶的数量：根据数据的分布动态调整桶的数量，避免所有元素都分配到同一个桶中。
使用更高效的子排序算法：例如使用快速排序或归并排序代替插入排序。

桶排序是一种高效的排序算法，尤其适用于数据分布均匀的场景。对于非均匀分布的数据，桶排序的性能可能会下降。

希尔排序

希尔排序（Shell Sort）是插入排序的一种改进版本，也称为缩小增量排序。它的核心思想是通过将数组分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的间隔，最终对整个数组进行一次插入排序。希尔排序的时间复杂度优于普通的插入排序。以下是使用C语言实现数组的希尔排序的代码：

希尔排序代码实现

#include <stdio.h>// 希尔排序函数
void shellSort(int arr[], int n) {// 初始间隔（gap）为数组长度的一半，逐步缩小间隔for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个子序列进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];  // 当前需要插入的元素int j;// 将比temp大的元素向后移动for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;  // 插入temp到正确位置}}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {12, 34, 54, 2, 3};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);shellSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

shellSort函数：
- 初始间隔（gap）为数组长度的一半，逐步缩小间隔。
- 对每个子序列进行插入排序。
- 将比当前元素大的元素向后移动，直到找到当前元素的正确位置。
printArray函数：用于打印数组的内容。
main函数：测试希尔排序的实现。

运行结果：

原始数组: 
12 34 54 2 3 
排序后的数组: 
2 3 12 34 54

时间复杂度：

最坏情况：O(n²)（取决于间隔序列的选择）。
平均情况：O(n log n) 到 O(n^(3/2))。
最好情况：O(n log n)。

空间复杂度：

O(1)（原地排序，不需要额外空间）。

希尔排序的特点：

改进的插入排序：通过分组插入排序，减少了元素的移动次数。
不稳定排序：希尔排序是不稳定的排序算法，可能会改变相同元素的相对顺序。
适合中等规模数据：希尔排序的效率高于普通的插入排序，适合中等规模的数据排序。

优化版本：

希尔排序的性能取决于间隔序列的选择。常见的间隔序列有：

希尔原始序列：gap = n / 2, gap /= 2。
Hibbard序列：gap = 2^k - 1。
Sedgewick序列：gap = 9 * 4^i - 9 * 2^i + 1 或 gap = 4^i + 3 * 2^i + 1。

以下是使用Hibbard序列的优化版本：

// 使用Hibbard序列的希尔排序
void shellSortHibbard(int arr[], int n) {// 计算Hibbard序列的最大值int k = 1;while ((1 << k) - 1 < n) {k++;}// 使用Hibbard序列作为间隔for (int gap = (1 << k) - 1; gap > 0; gap = (1 << (--k)) - 1) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}

希尔排序是一种高效的排序算法，尤其适用于中等规模数据的排序。通过选择合适的间隔序列，可以进一步提高其性能。

总结

以下是常见排序算法的比较表格，包括时间复杂度、空间复杂度、稳定性以及适用场景等信息：

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	是否稳定	适用场景
Quick	O(n log n)	O(n²)	O(n log n)	O(log n)	不稳定	大规模数据，通用排序
Bubble	O(n²)	O(n²)	O(n)	O(1)	稳定	小规模数据，教学用途
Insert	O(n²)	O(n²)	O(n)	O(1)	稳定	小规模或部分有序数据
Select	O(n²)	O(n²)	O(n²)	O(1)	不稳定	小规模数据，简单实现
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定	大规模数据，稳定排序需求
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定	大规模数据，原地排序需求
Count	O(n + k)	O(n + k)	O(n + k)	O(n + k)	稳定	小范围整数排序
Radix	O(d(n + k))	O(d(n + k))	O(d(n + k))	O(n + k)	稳定	整数或字符串排序，位数较小
Bucket	O(n + k)	O(n²)	O(n)	O(n + k)	稳定	均匀分布的数据
Shell	O(n log n)	O(n²)	O(n log n)	O(1)	不稳定	中等规模数据，改进的插入排序

表格说明：

时间复杂度：
- 平均：算法在大多数情况下的性能。
- 最坏：算法在最差情况下的性能。
- 最好：算法在最优情况下的性能。
空间复杂度：算法所需的额外空间。
稳定性：排序后相同元素的相对顺序是否保持不变。
适用场景：算法最适合的应用场景。

总结：

Quick Sort：通用高效，适合大规模数据，但不稳定。
Bubble Sort：简单但效率低，适合小规模数据或教学用途。
Insertion Sort：适合小规模或部分有序数据，稳定。
Selection Sort：简单但效率低，适合小规模数据。
Merge Sort：稳定且高效，适合大规模数据，但需要额外空间。
Heap Sort：原地排序，适合大规模数据，但不稳定。
Counting Sort：适合小范围整数排序，稳定。
Radix Sort：适合整数或字符串排序，稳定。
Bucket Sort：适合均匀分布的数据，稳定。
Shell Sort：改进的插入排序，适合中等规模数据。

根据具体需求选择合适的排序算法可以提高程序的效率。