编辑“︁C 语言数组排序”︁（章节）

= C语言数组排序 =

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

== 排序基础概念 ==
排序算法的核心是通过比较和交换元素位置使数组有序。常见指标包括：
* '''时间复杂度'''：完成排序所需的操作次数（如<math>O(n^2)</math>、<math>O(n \log n)</math>）
* '''空间复杂度'''：排序过程中额外占用的内存空间
* '''稳定性'''：相等元素的原始顺序是否保留

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

== 基础排序算法 ==
=== 冒泡排序（Bubble Sort） ===
通过重复交换相邻无序元素实现排序，适合小规模数据。

<syntaxhighlight lang="c">
#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;
}
</syntaxhighlight>

'''输出:'''
<pre>
排序结果: 11 12 22 25 34 64 90
</pre>

=== 选择排序（Selection Sort） ===
每次选择最小/最大元素放到已排序序列末尾。

<syntaxhighlight lang="c">
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;
    }
}
</syntaxhighlight>

== 高效排序算法 ==
=== 快速排序（Quick Sort） ===
分治算法典范，平均时间复杂度<math>O(n \log n)</math>。

<syntaxhighlight lang="c">
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);
    }
}
</syntaxhighlight>

=== 归并排序（Merge Sort） ===
稳定排序算法，需要额外空间，时间复杂度恒为<math>O(n \log n)</math>。

== 标准库排序 ==
C语言标准库提供<code>qsort()</code>函数：

<syntaxhighlight lang="c">
#include <stdlib.h>

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

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

== 实际应用案例 ==
'''成绩管理系统'''需要按分数排序：
<syntaxhighlight lang="c">
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);
</syntaxhighlight>

== 算法比较表 ==
{| class="wikitable"
|+ 排序算法特性对比
! 算法 !! 平均时间复杂度 !! 空间复杂度 !! 稳定性
|-
| 冒泡排序 || <math>O(n^2)</math> || <math>O(1)</math> || 稳定
|-
| 快速排序 || <math>O(n \log n)</math> || <math>O(\log n)</math> || 不稳定
|-
| 归并排序 || <math>O(n \log n)</math> || <math>O(n)</math> || 稳定
|}

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

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

[[Category:编程语言]]
[[Category:C]]
[[Category:C 语言数组]]