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

合肥瑶海区医院/云南seo网络优化师

news 文章来源：https://blog.csdn.net/weixin_57242378/article/details/145404415 2025/3/13 17:03:28

合肥瑶海区医院,云南seo网络优化师,爱搜索中级网站建设,没有备案做盈利性的网站违法吗数组排序算法用C语言实现的数组排序算法。排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度是否稳定适用场景QuickO(n log n)O(n)O(n log n)O(log n)不稳定大规模数据，通用排序BubbleO(n)O(n)O(n)O(1)稳定小规模数据，教学用途InsertO(n)…

数组排序算法

用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：改进的插入排序，适合中等规模数据。

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

数组排序算法

快速排序

代码说明：

运行结果：

时间复杂度：

冒泡排序

代码说明：

运行结果：

优化版本：

时间复杂度：

空间复杂度：

插入排序

插入排序代码实现

代码说明：

运行结果：

时间复杂度：

空间复杂度：

插入排序的特点：

优化版本：

选择排序

选择排序代码实现

代码说明：

运行结果：

时间复杂度：

空间复杂度：

选择排序的特点：

优化版本：

归并排序

归并排序代码实现

代码说明：

运行结果：

时间复杂度：

空间复杂度：

归并排序的特点：

优化版本：

堆排序

堆排序代码实现

代码说明：

运行结果：

时间复杂度：

空间复杂度：

堆排序的特点：

优化版本：

计数排序

计数排序代码实现

代码说明：

运行结果：

时间复杂度：

计数排序的特点：

优化版本：

基数排序

基数排序代码实现

代码说明：

运行结果：

时间复杂度：

基数排序的特点：

优化版本：

桶排序

桶排序代码实现

代码说明：

运行结果：

时间复杂度：

空间复杂度：

桶排序的特点：

优化版本：

希尔排序

希尔排序代码实现

代码说明：

运行结果：

时间复杂度：

空间复杂度：

希尔排序的特点：

优化版本：

总结

表格说明：

总结：

相关文章：