C语言排序算法详解及代码实现344

C语言作为一门底层编程语言，其效率和性能在许多领域都备受推崇。在实际应用中，数据的排序是一个非常常见的需求，高效的排序算法能够显著提升程序的运行速度和用户体验。本文将深入探讨C语言中几种常用的排序算法，包括它们的原理、优缺点以及相应的代码实现，并提供一些代码优化技巧。

排序算法大致可以分为两类：内排序和外排序。内排序是指数据量较小，可以一次性加载到内存中进行排序的算法；外排序则针对数据量过大，无法全部加载到内存的情况，需要借助外部存储设备进行排序。本文主要关注内排序算法。

1. 冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法，它重复地走访待排序的元素列，依次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。走访元素列的工作是重复地进行直到没有再需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

优点：简单易懂，代码实现简洁。

缺点：效率低，时间复杂度为O(n^2)，不适合处理大量数据。```c
#include
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]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("排序后的数组:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("");
return 0;
}
```

2. 选择排序 (Selection Sort)

选择排序也是一种简单的排序算法。它重复地查找出未排序部分中的最小元素，然后将其放置到已排序部分的末尾。类似冒泡排序，选择排序的时间复杂度也是O(n^2)。

优点：简单易懂，代码实现简洁，数据交换次数少。

缺点：效率低，时间复杂度为O(n^2)，不适合处理大量数据。```c
#include
void selectionSort(int arr[], int n) {
int i, j, min_idx;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("排序后的数组:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("");
return 0;
}
```

3. 插入排序 (Insertion Sort)

插入排序的工作原理类似于我们整理扑克牌。从第二个元素开始，将当前元素与已排序部分的元素进行比较，找到合适的位置插入。

优点：简单易懂，代码实现简洁，对于少量数据或已基本有序的数据效率较高。

缺点：效率低，时间复杂度为O(n^2)，不适合处理大量数据。```c
#include
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("排序后的数组:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("");
return 0;
}
```