排序算法详解、应用对比与C语言实现

四种经典排序算法详解（原理+动图+代码）

一、排序算法的重要性

排序算法是计算机科学领域最基础的算法之一，在数据库索引、搜索引擎优化、大数据分析等领域有广泛应用。根据Stack Overflow 2022开发者调查，超过83%的面试会考察算法实现能力，其中排序算法是必考题型。

（图示：电商平台价格排序、学生成绩排名等实际应用场景）

二、基础排序算法详解

2.1 冒泡排序（Bubble Sort）

算法原理

通过相邻元素两两比较，将最大值"冒泡"到数组末尾。每轮遍历减少一个比较元素。

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;
            }
        }
    }
}

过程演示（以数组[5,3,8,6,4]为例）

初始状态：5 3 8 6 4
第1轮：
3 5 8 6 4 → 3 5 6 8 4 → 3 5 6 4 8
第2轮：
3 5 6 4 → 3 5 4 6 
第3轮： 
3 5 4 → 3 4 5
第4轮：
3 4 → 完成排序

2.2 插入排序（Insertion Sort）

算法特点

• 时间复杂度：O(n²)（最坏）
• 空间复杂度：O(1)
• 稳定排序
• 适合小规模数据或基本有序数据

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--;
        }
        arr[j+1] = key;
    }
}

过程演示（以数组[5, 2, 9, 1, 5]为例）

未排序部分: [5, 2, 9, 1, 5]
已排序部分: []
第一步：
将第一个元素（5）视为已排序部分。
未排序部分: [2, 9, 1, 5]
已排序部分: [5]
第二步：
取未排序部分的第一个元素（2），与已排序部分的元素比较。
2 小于 5，将 5 向后移动，插入 2。
未排序部分: [9, 1, 5]
已排序部分: [2, 5]
第三步：
取未排序部分的下一个元素（9），与已排序部分的元素比较。
9 大于 5，直接插入到已排序部分的末尾。
未排序部分: [1, 5]
已排序部分: [2, 5, 9]
第四步：
取未排序部分的下一个元素（1），与已排序部分的元素比较。
1 小于 9，将 9 向后移动。
1 小于 5，将 5 向后移动。
1 小于 2，将 2 向后移动，插入 1。
未排序部分: [5]
已排序部分: [1, 2, 5, 9]
第五步：
取未排序部分的最后一个元素（5），与已排序部分的元素比较。
5 小于 9，将 9 向后移动。
5 等于已排序部分的最后一个元素（也是5），直接插入到该位置（或者保持不变，因为相等）。
未排序部分: []
已排序部分: [1, 2, 5, 5, 9]

最终排序结果：
[1, 2, 5, 5, 9]

三、高效排序算法解析

3.1 快速排序（Quick Sort）

核心思想

分治策略：选取基准值（pivot），将数组划分为两个子数组，递归排序。

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);
    }
}

快速排序分区过程图示

3.2 归并排序（Merge Sort）

算法优势

• 稳定排序
• 时间复杂度稳定O(n log n)
• 适合链表结构排序
• 可用于外部排序

void merge(int arr[], int l, int m, int r) {
    // 合并两个有序子数组
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
        
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 处理剩余元素
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

归并排序过程图示

四、排序算法综合对比

扩展：主流排序算法综合对比

五、工程实践建议

1. 小数据量（n < 100）：优先使用插入排序
2. 通用场景：采用快速排序（如C语言qsort函数）
3. 稳定性要求：选择归并排序（如Java的Arrays.sort）
4. 内存敏感：使用堆排序
5. 数据基本有序：考虑冒泡排序优化版

// 优化版冒泡排序（增加交换标志）
void optimizedBubbleSort(int arr[], int n) {
    int swapped;
    for (int i = 0; i < n-1; i++) {
        swapped = 0;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

六、总结与思考

不同的排序算法各有利弊，理解其核心原理和适用场景比死记代码更重要。实际工程中常采用混合排序策略（如TimSort结合了归并排序和插入排序），建议读者在掌握基础算法后，可进一步研究：

1. 不同编程语言的内置排序实现
2. 并行排序算法设计
3. 海量数据的分治策略优化
4. 特殊数据结构的排序优化