C语言排序算法详解及应用：从冒泡排序到快速排序191

C语言作为一门底层语言，其效率和灵活性使其在系统编程和算法实现方面具有显著优势。排序作为一项基础的算法操作，在C语言中有着广泛的应用。本文将深入探讨C语言中的几种常用排序算法，从简单的冒泡排序到高效的快速排序，并结合代码示例进行详细讲解，帮助读者掌握C语言排序的精髓。

排序算法的目标是将一组无序的数据元素按照特定的顺序排列，例如升序或降序。不同的排序算法在时间复杂度和空间复杂度上有所差异，选择合适的算法取决于数据的规模、数据的特点以及对性能的要求。接下来，我们将详细介绍几种常见的C语言排序算法。

1. 冒泡排序 (Bubble Sort)

冒泡排序是最简单易懂的排序算法之一。它通过反复遍历待排序的元素序列，比较相邻的两个元素，如果顺序错误则交换它们。每次遍历都会将最大的（或最小的）元素“冒泡”到序列的末尾。 虽然简单，但其时间复杂度为O(n²)，对于大型数据集效率较低，不适用于实际生产环境中的大规模数据排序。
#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("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("");
return 0;
}

2. 选择排序 (Selection Sort)

选择排序也具有O(n²)的时间复杂度，但它比冒泡排序略微高效一些。选择排序每次遍历都会找到未排序部分中的最小（或最大）元素，将其与未排序部分的第一个元素交换位置。选择排序的优势在于它只需要进行O(n)次的交换操作，而冒泡排序可能进行更多的交换。
#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, 90};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("");
return 0;
}

3. 插入排序 (Insertion Sort)

插入排序的时间复杂度也是O(n²)，但在数据量较小或数据基本有序的情况下，其效率较高。插入排序的思想是将每个元素插入到已排序部分的正确位置。它是一种稳定的排序算法，这意味着相同元素的相对顺序在排序后保持不变。
#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("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("");
return 0;
}

4. 快速排序 (Quick Sort)

快速排序是一种高效的排序算法，其平均时间复杂度为O(n log n)，最坏情况下的时间复杂度为O(n²)。快速排序通过递归的方式将数组划分为两个子数组，然后分别对子数组进行排序。快速排序的选择在于其平均时间复杂度的高效性，在实际应用中被广泛使用。
#include
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j

2025-04-30

上一篇：C语言无限循环输出“ok”详解及安全编程实践

下一篇：C语言图形绘制：深入理解和应用fillrectangle函数