【数据结构】排序算法：冒泡与快速

引言：排序算法的重要性

排序算法是计算机科学的基础核心，直接影响程序性能和资源消耗。在C语言开发中，理解不同排序算法的特性对编写高效代码至关重要。本文将深入分析两种经典排序算法：简单直观的冒泡排序和高效快速的快速排序，并提供完整的C语言实现。

冒泡排序：简单但低效

基本思想

冒泡排序通过相邻元素比较交换，使较大元素逐渐移动到数组末端，如同气泡上浮。

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 arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("排序结果：");
    for (int i=0; i<n; i++) printf("%d ", arr[i]);
    return 0;
}

性能分析

• 时间复杂度：

  • 最优：O(n)（已排序数组，可添加标志位优化）

  • 最差：O(n²)（完全逆序）

  • 平均：O(n²)

• 空间复杂度：O(1)（原地排序）

• 稳定性：稳定（相等元素不交换）

优化版本（带提前终止）

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]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1;
            }
        }
        if (swapped == 0) break; // 无交换说明已有序
    }
}

快速排序：高效分治策略

基本思想

快速排序采用分治法：

1. 选取基准元素（pivot）

2. 将数组分为小于和大于基准的两部分

3. 递归排序子数组

C语言实现

#include <stdio.h>

// 分区函数
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);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("排序结果：");
    for (int i=0; i<n; i++) printf("%d ", arr[i]);
    return 0;
}
性能分析

• 时间复杂度：

  • 最优：O(n log n)（平衡分区）

  • 最差：O(n²)（极端不平衡分区）

  • 平均：O(n log n)

• 空间复杂度：O(log n)（递归栈空间）

• 稳定性：不稳定（分区可能改变相同元素顺序）

优化技巧

1. 基准选择优化（避免最坏情况）：

   // 三数取中法选择基准
   int medianOfThree(int arr[], int low, int high) {
       int mid = low + (high - low)/2;
       if (arr[low] > arr[mid]) swap(&arr[low], &arr[mid]);
       if (arr[low] > arr[high]) swap(&arr[low], &arr[high]);
       if (arr[mid] > arr[high]) swap(&arr[mid], &arr[high]);
       return mid;
   }

2. 小数组切换插入排序：

   void quickSortOptimized(int arr[], int low, int high) {
       if (high - low < 10) { // 阈值可调整
           insertionSort(arr, low, high);
           return;
       }
       // 正常快速排序流程...
   }

对比与选型指南

实际开发建议

1. 优先考虑快速排序：适用于大多数通用排序需求

2. 特殊场景选择：

   • 数据量小（n<100）：冒泡或插入排序

   • 需要稳定性：归并排序

   • 内存受限：堆排序

3. 工程实践：直接使用标准库函数（如C的qsort()）

C标准库qsort示例

#include <stdlib.h>

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

int main() {
    int arr[] = {10, 5, 8, 1, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    qsort(arr, n, sizeof(int), compare);
    // 输出排序结果...
    return 0;
}

结论

冒泡排序以其简单直观的特性成为算法学习的入门选择，而快速排序凭借高效分治策略成为实际应用的主流。理解这两种算法的核心思想，能够帮助开发者：

• 根据数据特征选择合适算法

• 优化现有排序实现

• 更好地理解标准库排序函数的工作原理

建议读者动手实现这两个算法，并通过不同规模的数据测试它们的性能差异，这将加深对时间复杂度的理解。记住，在实际项目中，除非有特殊需求，否则应优先使用经过充分优化的标准库排序函数。