C 语言数组排序

C语言数组排序

数组排序是C语言中处理数据集合的基础操作，指按照特定规则（升序/降序）重新排列数组元素的过程。排序算法直接影响程序效率，初学者需掌握原理及实现，进阶者应了解性能差异和应用场景。

排序基础概念

排序算法的核心是通过比较和交换元素位置使数组有序。常见指标包括：

• 时间复杂度：完成排序所需的操作次数（如$O(n^2)$、$O(n\log n)$）
• 空间复杂度：排序过程中额外占用的内存空间
• 稳定性：相等元素的原始顺序是否保留

pie title 常用排序算法分类 "比较排序" : 75 "非比较排序" : 25

基础排序算法

冒泡排序（Bubble Sort）

通过重复交换相邻无序元素实现排序，适合小规模数据。

#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]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    int data[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(data)/sizeof(data[0]);
    
    bubbleSort(data, size);
    
    printf("排序结果: ");
    for (int i = 0; i < size; i++)
        printf("%d ", data[i]);
    return 0;
}

输出:

排序结果: 11 12 22 25 34 64 90

选择排序（Selection Sort）

每次选择最小/最大元素放到已排序序列末尾。

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;
        
        // 交换找到的最小值
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

高效排序算法

快速排序（Quick Sort）

分治算法典范，平均时间复杂度$O(n\log n)$。

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++;
            // 交换元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 交换基准值
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    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);
    }
}

归并排序（Merge Sort）

稳定排序算法，需要额外空间，时间复杂度恒为$O(n\log n)$。

标准库排序

C语言标准库提供qsort()函数：

#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

// 使用示例
qsort(arr, n, sizeof(int), compare);

实际应用案例

成绩管理系统需要按分数排序：

struct Student {
    char name[50];
    int score;
};

int compareStudents(const void *a, const void *b) {
    return ((struct Student*)b)->score - ((struct Student*)a)->score;
}
// 排序学生数组
qsort(students, count, sizeof(struct Student), compareStudents);

算法比较表

排序算法特性对比

算法	平均时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(1)$	稳定
快速排序	$O(n\log n)$	$O(\log n)$	不稳定
归并排序	$O(n\log n)$	$O(n)$	稳定

进阶话题

• 多关键字排序（先按年龄再按姓名）
• 外部排序（处理超大数据集）
• 并行排序算法优化

掌握数组排序是算法学习的重要基石，建议从理解基础算法开始，逐步过渡到标准库应用和性能优化实践。