排序之交换排序：冒泡排序与快速排序

交换排序，说白了就是通过比较和交换元素位置来达到有序。这类算法里最经典的两个代表，一个是冒泡排序，另一个是快速排序。一个简单到让人想笑，一个高效到让人想哭——嗯，我当年学的时候就是这个感觉。

冒泡排序：基础与优化

冒泡排序的思路很简单：从头到尾，两两比较，把大的往后挪。一轮下来，最大的数就沉到了最后。重复这个过程，直到所有数都排好。

但这里有个问题——如果某轮遍历下来，一次交换都没发生，说明数组已经有序了。这时候再继续遍历就是浪费。我在项目中遇到过这种情况：一个几乎有序的数组，用原始冒泡排序跑了整整n²次比较，白白浪费CPU周期。

// 优化后的冒泡排序
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    int swapped;
    
    for (i = 0; i < n - 1; i++) {
        swapped = 0;  // 每轮开始重置标志
        
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        
        // 如果没发生交换，提前结束
        if (swapped == 0) {
            break;
        }
    }
}

快速排序：枢轴选择与Partition过程

快速排序的核心思想是分治。选一个枢轴（pivot），把比它小的放左边，比它大的放右边。然后递归处理左右两部分。

这里最关键的就是两个问题：枢轴怎么选？Partition怎么做？

枢轴选择策略

枢轴选得好，快排效率高。选得不好，退化成冒泡排序。我见过有人直接取第一个元素做枢轴，结果遇到一个逆序数组，直接崩成O(n²)。

策略	做法	优缺点
固定位置	取第一个或最后一个	简单，但容易退化
随机选择	随机选一个元素	避免最坏情况，但有随机开销
三数取中	取首、中、尾三个数的中位数	工程中最常用，平衡性好

Partition过程

Partition是快排的核心操作。我习惯用挖坑填数法来实现，思路清晰，不容易出错。

// 挖坑填数法 Partition
int partition(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]);
    
    // 把枢轴放到最右边
    swap(&arr[mid], &arr[high]);
    int pivot = arr[high];
    
    int i = low - 1;  // i指向小于枢轴的最后一个元素
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

你想想看，这个Partition的过程其实就是在做一件事：把数组分成两堆，一堆小于枢轴，一堆大于枢轴。i指针始终指向小于枢轴的那一堆的末尾，j指针负责扫描整个数组。

快速排序的递归实现

递归实现最直观，也最容易理解。但要注意递归深度的问题——极端情况下可能栈溢出。

void quickSortRecursive(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSortRecursive(arr, low, pivotIndex - 1);
        quickSortRecursive(arr, pivotIndex + 1, high);
    }
}

快速排序的非递归实现

非递归实现需要手动维护一个栈。为什么要学这个？因为有些嵌入式环境不支持递归，或者递归深度受限。我在一个RTOS项目里就遇到过这种情况——任务栈只有4KB，递归快排直接崩了。

void quickSortIterative(int arr[], int low, int high) {
    // 用数组模拟栈
    int stack[high - low + 1];
    int top = -1;
    
    stack[++top] = low;
    stack[++top] = high;
    
    while (top >= 0) {
        high = stack[top--];
        low = stack[top--];
        
        int pivotIndex = partition(arr, low, high);
        
        // 先压入右半部分，再压入左半部分
        // 这样左半部分会先被处理
        if (pivotIndex + 1 < high) {
            stack[++top] = pivotIndex + 1;
            stack[++top] = high;
        }
        
        if (low < pivotIndex - 1) {
            stack[++top] = low;
            stack[++top] = pivotIndex - 1;
        }
    }
}

非递归版本的核心思想就是：用栈保存待处理的区间边界。每次从栈里取出一对边界，做Partition，然后把新的边界压入栈中。说白了，就是把递归调用栈显式地模拟出来。

知识体系总览

下面这张图展示了交换排序的整体脉络，以及我们今天讲的核心内容。

这张图把今天的内容串起来了。冒泡排序和快速排序虽然都属于交换排序，但思路完全不同。冒泡是稳扎稳打，快速是分而治之。在实际项目中，我90%的场景都用快速排序，只有在数据量极小（比如少于10个元素）或者几乎有序的情况下，才会考虑冒泡排序。