Java 七大排序算法（中篇）：冒泡与快速排序实现

1.4 优化策略

如果某一趟遍历中没有发生任何交换，说明数组已经有序，可以提前结束。 我们可以引入一个标记位 flag，若发生交换则置为 true。若一趟结束 flag 仍为 false，直接返回。

优化后的代码：

/**
 * 冒泡排序优化版
 * 时间复杂度：最坏 O(N^2)，最好 O(N)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 */
public static void bubbleSortOptimized(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                flag = true;
            }
        }
        // 没发生交换，说明已经有序
        if (!flag) {
            return;
        }
    }
}

public static void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

1.5 特性总结

1. 理解难度：低，非常适合入门。
2. 时间复杂度：平均和最坏情况均为 O(N^2)。
3. 空间复杂度：O(1)，原地排序。
4. 稳定性：稳定，相等元素不会改变相对顺序。

2. 快速排序

快速排序由 Hoare 于 1962 年提出，是一种基于二叉树结构的交换排序方法。其核心思想是分治：选取基准值，将序列分割为小于基准值的左子序列和大于基准值的右子序列，然后递归处理。

2.1 递归框架

快速排序的递归结构与二叉树的前序遍历非常相似。在处理时，可以先写出递归骨架，再专注于如何划分区间。

/**
 * @param start 待排序区间起始下标
 * @param end   待排序区间结束下标
 */
private static void quick(int[] array, int start, int end) {
    if (start >= end) return; // 区间无效或只剩一个元素
    
    // 分区操作，返回基准值最终位置
    int pivot = partition(array, start, end);
    
    // 递归排左序列
    quick(array, start, pivot - 1);
    // 递归排右序列
    quick(array, pivot + 1, end);
}

2.2 分区实现方式

2.2.1 Hoare 法

这是最经典的版本。以首元素为基准 key，先从右向左找比 key 小的数，再从左向右找比 key 大的数，交换它们。当左右指针相遇时，将 key 与相遇点交换。

注意：为什么先走右边？如果先走左边，相遇点的值可能比 key 大，导致基准值放错位置；先走右边能保证相遇点一定小于等于 key。等号必须取，防止指针不动越界。

private static int partitionHoare(int[] array, int left, int right) {
    int key = array[left];
    int i = left;
    while (left < right) {
        // 先走右边，找比 key 小的
        while (left < right && array[right] >= key) {
            right--;
        }
        // 再走左边，找比 key 大的
        while (left < right && array[left] <= key) {
            left++;
        }
        // 交换
        swap(array, left, right);
    }
    // 相遇后，将 key 放到正确位置
    swap(array, i, left);
    return left;
}

2.2.2 挖坑法

将首元素作为基准 key 取出，此时 left 位置成为一个'坑'。从右边找小填坑，再从左边找大填右边的坑，循环往复，最后将 key 填入最终的坑位。

private static int partitionPit(int[] array, int left, int right) {
    int key = array[left];
    while (left < right) {
        // 右边找小填左边坑
        while (left < right && array[right] >= key) {
            right--;
        }
        array[left] = array[right];
        
        // 左边找大填右边坑
        while (left < right && array[left] <= key) {
            left++;
        }
        array[right] = array[left];
    }
    // 填补最终空位
    array[left] = key;
    return left;
}

2.2.3 前后指针法

使用 prev 和 cur 两个指针。cur 负责寻找小于基准值的元素，找到后 prev 前进并交换。此方法逻辑较难直观理解，建议结合图示掌握。

private static int partitionPrePost(int[] array, int left, int right) {
    int prev = left;
    int cur = left + 1;
    while (cur <= right) {
        if (array[cur] < array[left] && array[++prev] != array[cur]) {
            swap(array, cur, prev);
        }
        cur++;
    }
    swap(array, prev, left);
    return prev;
}

2.3 快速排序优化

优化一：三数取中法

当数组本身有序时，快排退化为单分支递归，性能急剧下降。我们可以通过'三数取中'选择更合适的基准值，避免极端情况。

private static int midOfThree(int[] array, int left, int right) {
    int mid = (left + right) / 2;
    if (array[right] > array[left]) {
        if (array[mid] < array[left]) return left;
        else if (array[mid] > array[right]) return right;
        else return mid;
    } else {
        if (array[mid] > array[left]) return left;
        else if (array[mid] < array[right]) return right;
        else return mid;
    }
}

// 在 partition 前调用，确保基准值不是最大或最小
int index = midOfThree(array, start, end);
swap(array, index, start);

优化二：小区间插入排序

递归深度过深会增加栈开销。当子数组长度较小时（如小于 15），直接使用插入排序效率更高。

private static void insertSortRange(int[] array, int begin, int end) {
    for (int i = begin + 1; i <= end; i++) {
        int tmp = array[i];
        int j = i - 1;
        for (; j >= begin; j--) {
            if (array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = tmp;
    }
}

// 在主递归函数中加入判断
if (end - start + 1 <= 15) {
    insertSortRange(array, start, end);
    return;
}

2.4 完整递归实现示例

整合上述优化，以下是基于挖坑法的完整快速排序结构：

public static void quickSort(int[] array) {
    quick2(array, 0, array.length - 1);
}

private static void quick2(int[] array, int start, int end) {
    if (start >= end) return;
    
    // 小区间优化
    if (end - start + 1 <= 15) {
        insertSortRange(array, start, end);
        return;
    }
    
    // 三数取中优化
    int index = midOfThree(array, start, end);
    swap(array, index, start);
    
    int pivot = partitionPit(array, start, end);
    quick2(array, start, pivot - 1);
    quick2(array, pivot + 1, end);
}

// 辅助函数省略...（见上文）

快速排序的非递归实现在后续内容中展开。理解这些算法的关键在于动手画图模拟过程，一旦掌握了分治与划分的逻辑，编写代码自然水到渠成。