C 语言数组排序
在C语言中，数组是一种存储相同类型数据的集合。排序是数组操作中非常常见的任务，它可以帮助我们更高效地查找、插入或删除数据。本文将介绍几种常见的排序算法，并通过代码示例展示如何在C语言中实现它们。
1. 什么是数组排序？
数组排序是指将数组中的元素按照一定的顺序（升序或降序）重新排列。排序算法是实现这一目标的具体方法。常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序等。
2. 冒泡排序
冒泡排序是一种简单的排序算法。它重复地遍历数组，比较相邻的元素，并交换它们的位置，直到整个数组有序。
代码示例
#include <stdio.h>
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]) {
// 交换 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("排序后的数组: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
输入和输出
输入数组: {64, 34, 25, 12, 22, 11, 90}
输出数组: {11, 12, 22, 25, 34, 64, 90}
冒泡排序的时间复杂度为O(n²)，适用于小规模数据排序。
3. 选择排序
选择排序是一种简单直观的排序算法。它的工作原理是每次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。
代码示例
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 交换 arr[i] 和 arr[min_idx]
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("排序后的数组: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
输入和输出
输入数组: {64, 25, 12, 22, 11}
输出数组: {11, 12, 22, 25, 64}
选择排序的时间复杂度也是O(n²)，但它比冒泡排序稍微高效一些，因为它的交换次数较少。
4. 插入排序
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
代码示例
#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int 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("排序后的数组: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
输入和输出
输入数组: {12, 11, 13, 5, 6}
输出数组: {5, 6, 11, 12, 13}
插入排序的时间复杂度为O(n²)，但在数据几乎有序的情况下，它的性能会非常好。
5. 快速排序
快速排序是一种高效的排序算法，采用分治法策略。它通过选择一个“基准”元素，将数组分为两部分，一部分比基准小，另一部分比基准大，然后递归地对这两部分进行排序。
代码示例
#include <stdio.h>
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 <= 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) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
输入和输出
输入数组: {10, 7, 8, 9, 1, 5}
输出数组: {1, 5, 7, 8, 9, 10}
快速排序的平均时间复杂度为O(n log n)，但在最坏情况下会退化为O(n²)。
6. 实际应用场景
排序算法在现实生活中有广泛的应用，例如：
- 数据库查询优化: 数据库系统需要对大量数据进行排序以提高查询效率。
- 搜索引擎: 搜索引擎需要对搜索结果进行排序以提供最相关的信息。
- 金融分析: 金融分析师需要对股票价格、交易量等数据进行排序以进行趋势分析。
7. 总结
本文介绍了C语言中几种常见的数组排序算法，包括冒泡排序、选择排序、插入排序和快速排序。每种算法都有其优缺点，适用于不同的场景。初学者可以从简单的冒泡排序和选择排序开始，逐步掌握更高效的排序算法。
8. 附加资源与练习
- 练习: 尝试实现一个降序排序的版本。
- 资源: 阅读更多关于归并排序和堆排序的内容，了解它们的实现原理。
- 挑战: 尝试对字符串数组进行排序，并比较不同排序算法的性能。
通过不断练习和尝试不同的排序算法，你将能够更好地理解它们的原理和应用场景。