以下是C语言中常用的十种排序算法：
1. 冒泡排序（Bubble Sort）
冒泡排序的核心思想是反复交换相邻的未按顺序排列的元素，通过多次遍历数组，每次将一个未排好序的元素放到合适的位置，最终得到有序数组。时间复杂度为O(n^2)，不适用于大规模数据。
- 优点：简单易懂，实现容易。
- 缺点：效率较低，对大规模数据排序耗时长，不适合生产环境使用。
- 应用场景：适用于小规模数据排序以及教学示例等场景。
## 2. 选择排序（Selection Sort）
选择排序的主要思想是在未排序的序列中选择最小（或最大）的元素放到已排序序列的末尾。与冒泡排序不同的是，选择排序每次只会进行一次交换操作，因此其时间复杂度仍然为O(n^2)。
- 优点：实现容易，内存开销较小。
- 缺点：效率较低，在大规模数据下表现不佳。
- 应用场景：适用于小规模数据排序以及结构性较差的数据排序。
## 3. 插入排序（Insertion Sort）
插入排序的核心思想是将待排序的序列分成已排序和未排序两部分，每次从未排序的序列中选择一个元素插入到已排序的序列中，直至所有元素都被插入。与前两种排序算法不同的是，插入排序在处理近乎有序的数组时表现较优，其时间复杂度为O(n^2)。
- 优点：实现简单，在排序小规模数据或近乎有序的数据时表现良好。
- 缺点：效率较低，在大规模数据下表现不佳。
- 应用场景：适用于小规模数据排序以及对近乎有序的数据进行排序。
## 4. 希尔排序（Shell Sort）
希尔排序是插入排序的改进版，其主要思想是将待排序的序列按照一个增量序列（通常是n/2，n/4，...，1）分成若干个子序列，对每个子序列进行插入排序。然后缩小增量，再进行插入排序。最终当增量为1时，整个序列就被排好序了。由于希尔排序多次分组排序，因此其时间复杂度介于O(n)和O(n^2)之间。
- 优点：相较于插入排序，希尔排序的效率更高。
- 缺点：时间复杂度上界难以精确，而且受增量序列的影响较大。
- 应用场景：适用于中等规模数据排序，比插入排序更加高效。
## 5. 归并排序（Merge Sort）
归并排序是一种比较高效的排序算法，其主要思想是将待排序的序列分成左右两部分，对每部分进行递归排序，最后将两个有序的子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn)，但其需要开辟额外的空间用于存放临时序列，因此其空间复杂度较高。
- 优点：时间复杂度稳定，具有很好的可扩展性。
- 缺点：需要额外的内存空间。
- 应用场景：适用于大规模数据排序，对稳定性和可扩展性要求较高的场景。
## 6. 快速排序（Quick Sort）
快速排序也是一种高效的排序算法，其主要思想是选择一个基准元素，将待排序的序列分成两部分，一部分所有元素都小于等于基准元素，另一部分所有元素都大于等于基准元素。然后对这两部分分别递归调用快速排序函数。快速排序的时间复杂度为O(nlogn)，但其在最坏情况下性能会退化为O(n^2)。
- 优点：效率较高，在大规模数据下表现良好。
- 缺点：不稳定，存在最坏时间复杂度O(n^2)的情况。
- 应用场景：适用于大规模数据排序，对稳定性没有严格要求的场景。
## 7. 堆排序（Heap Sort）
堆排序利用了二叉堆的数据结构，其主要思想是将待排序的序列看成一棵完全二叉树，对每个非叶子节点进行堆化操作，得到一个大根堆或小根堆。然后依次将堆顶元素与末尾元素交换，并进行堆化操作，直到所有元素被排好序。
- 优点：效率较高，不需要额外的内存空间。
- 缺点：不稳定。
- 应用场景：适用于大规模数据排序，对稳定性没有要求。
## 8. 计数排序（Counting Sort）
计数排序适用于元素取值范围比较小的场景，其主要思想是通过统计每个元素出现的次数来确定元素在最终有序序列中的位置。计数排序的时间复杂度为O(n+k)，其中k为元素取值范围。
- 优点：效率高，稳定。
- 缺点：需要额外的内存空间，只能处理非负整数。
- 应用场景：适用于元素取值范围比较小的场景，如对年龄进行排序等。
## 9. 桶排序（Bucket Sort）
桶排序是一种基于计数排序的改进算法，适用于元素分布比较均匀的场景。其主要思想是将待排序的元素按照一定规则放入多个桶中，对每个桶中的元素进行排序，最后依次将所有桶中的元素拼接成一个有序序列。桶排序的时间复杂度为O(n+k)，空间复杂度较高。
- 优点：效率高，稳定。
- 缺点：需要额外的内存空间。
- 应用场景：适用于元素分布比较均匀的场景。
## 10. 基数排序（Radix Sort）
基数排序是一种非比较排序算法，其主要思想是利用数字的位数进行排序。对于待排序的元素，首先按照个位排序，然后按照十位排序，依次类推，直到排完最高位。基数排序的时间复杂度为O(d(n+k))，其中d为元素的最大位数，k为元素的取值范围。
- 优点：稳定，适用于各种数据类型。
- 缺点：需要额外的内存空间。
- 应用场景：适用于元素位数相同的场景，如整数排序等。
总体来说，不同的排序算法有各自不同的特点和适用场景
## 代码举例
好的，以下是使用C语言编写各种排序算法的完整示例代码，每一行都有注释说明。请注意，这些示例可能不包含错误处理和边界检查等必要的细节。
### 冒泡排序
```c
void bubble_sort(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]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
```
### 选择排序
```c
void selection_sort(int arr[], int n) {
// 从第一个元素开始遍历到倒数第二个元素
for (int i = 0; i < n - 1; i++) {
// 假设当前元素是未排序部分中最小的
int min_index = i;
// 遍历未排序部分的所有元素，找到最小值的下标
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// 如果最小值不在已排序的位置，则将其放到已排序部分的末尾
if (min_index != i) {
int temp = arr[ i];
arr[ i] = arr[min_index];
arr[min_index] = temp;
}
}
}
```
### 插入排序
```c
void insertion_sort(int arr[], int n) {
// 从第二个元素开始遍历
for (int i = 1; i < n; i++) {
int temp = arr[ i]; // 将当前元素存储在临时变量中
int j = i - 1; // 已排序部分的最后一个元素的下标
// 如果已排序部分中的一个元素大于当前元素，则向右移动该元素
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
// 将当前元素插入到正确的位置
arr[j + 1] = temp;
}
}
```
### 希尔排序
```c
void shell_sort(int arr[], int n) {
// 初始化间隔大小
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个间隔进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[ i];
int j = i;
// 将未排序部分中的元素插入到已排序部分的正确位置
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
```
### 归并排序
```c
// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
int len1 = mid - left + 1; // 左子数组的长度
int len2 = right - mid; // 右子数组的长度
int L[len1], R[len2]; // 创建两个临时数组
// 将左子数组复制到 L 数组中
for (int i = 0; i < len1; i++) {
L[ i] = arr[left + i];
}
// 将右子数组复制到 R 数组中
for (int j = 0; j < len2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = left; // i、j 和 k 分别是 L、R和 arr 数组中元素的下标
// 比较 L 和 R 数组中的元素，将较小的一个放到 arr 数组中
while (i < len1 && j < len2) {
if (L[ i] <= R[j]) {
arr[k] = L[ i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 将剩余的元素放到 arr 数组中
while (i < len1) {
arr[k] = L[ i];
i++;
k++;
}
while (j < len2) {
arr[k] = R[j];
j++;
k++;
}
}
// 归并排序
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 找到数组的中间位置
merge_sort(arr, left, mid); // 对左子数组进行归并排序
merge_sort(arr, mid + 1, right); // 对右子数组进行归并排序
merge(arr, left, mid, right); // 合并两个有序子数组
}
}
```
### 快速排序
```c
// 将数组划分为两部分，并返回枢轴的下标
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // 选择第一个元素作为枢轴
while (low < high) {
// 从后向前遍历，找到第一个小于等于枢轴的元素
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
// 从前向后遍历，找到第一个大于枢轴的元素
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot; // 将枢轴放到正确位置上
return low;
}
// 快速排序
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pivot_index = partition(arr, low, high); // 划分数组为两部分
quick_sort(arr, low, pivot_index - 1); // 对左子数组进行快速排序
quick_sort(arr, pivot_index + 1, high); // 对右子数组进行快速排序
}
}
```
这些排序算法都是经典的基于比较的排序算法，它们的时间复杂度最好情况下都是 O(n log n)，最坏情况下为 O(n2)。在实际应用中，可以根据具体情况选择不同的排序算法来优化程序性能。
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
