逐行代码解析：快速排序的条件设置

快速排序 Java 实现

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 获取分区点
            int pivotIndex = partition(arr, low, high);

            // 递归排序左子数组
            quickSort(arr, low, pivotIndex - 1);
            // 递归排序右子数组
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // 选择最右边的元素作为基准
        int pivot = arr[high];
        // i 是小于基准的区域的边界
        int i = low - 1;

        for (int j = low; j < high; j++) {
            // 如果当前元素小于等于基准
            if (arr[j] <= pivot) {
                i++;
                // 交换元素
                swap(arr, i, j);
            }
        }
        // 将基准元素放到正确的位置
        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("排序前:");
        printArray(arr);

        quickSort(arr, 0, arr.length - 1);

        System.out.println("排序后:");
        printArray(arr);
    }

    private static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

快速排序 Python 实现

def quick_sort(arr, low, high):
    if low < high:
        # 获取分区点
        pivot_index = partition(arr, low, high)

        # 递归排序左子数组
        quick_sort(arr, low, pivot_index - 1)
        # 递归排序右子数组
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    # 选择最右边的元素作为基准
    pivot = arr[high]
    # i 是小于基准的区域的边界
    i = low - 1

    for j in range(low, high):
        # 如果当前元素小于等于基准
        if arr[j] <= pivot:
            i += 1
            # 交换元素
            arr[i], arr[j] = arr[j], arr[i]

    # 将基准元素放到正确的位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# 测试代码
if __name__ == "__main__":
    arr = [10, 7, 8, 9, 1, 5]
    print("排序前:", arr)

    quick_sort(arr, 0, len(arr) - 1)

    print("排序后:", arr)

---

逐行代码解析

1. 主方法 quickSort (Java) / quick_sort (Python)

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

def quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

• 作用：递归实现快速排序
• 参数：
  • arr：待排序数组
  • low：当前排序的起始索引
  • high：当前排序的结束索引
• 条件 low < high：确保至少有两个元素需要排序，否则递归终止
• 步骤：
  1. 调用 partition 方法进行分区，得到基准元素的最终位置 pivotIndex
  2. 递归排序左半部分（从 low 到 pivotIndex-1）
  3. 递归排序右半部分（从 pivotIndex+1 到 high）

2. 分区方法 partition (Java) / partition (Python)

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

• 作用：将数组分为两部分，使得左边部分都小于等于基准，右边部分都大于基准，并返回基准元素的最终位置
• 步骤解析：
  1. 选择基准：int pivot = arr[high]; 选择最右边的元素作为基准
  2. 初始化指针：int i = low - 1; 指针 i 初始化为 low-1，表示小于基准的区域的边界（初始时该区域为空）
  3. 遍历数组：for (int j = low; j < high; j++) 遍历从 low 到 high-1 的元素（因为 high 位置是基准，最后处理）
  4. 比较元素：if (arr[j] <= pivot) 如果当前元素小于等于基准，则：
     • i++：将边界指针 i 向右移动一位
     • swap(arr, i, j)：将当前元素 arr[j] 交换到 i 的位置（即小于基准的区域）
  5. 放置基准：遍历结束后，将基准元素 arr[high] 与 i+1 位置的元素交换：
     • 此时 i+1 左边的元素都小于等于基准
     • i+1 右边的元素都大于基准
  6. 返回基准位置：return i + 1; 返回基准元素的最终位置

3. 交换方法 swap (Java) / Python 的元组交换

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

# Python 中直接使用元组交换，无需单独方法
arr[i], arr[j] = arr[j], arr[i]

• 作用：交换数组中两个位置的元素
• Java：使用临时变量 temp 完成交换
• Python：利用元组解包特性，直接交换

---

关键条件解析

1. 递归终止条件：if (low < high)

• 为什么需要这个条件？
  • 当 low >= high 时，表示子数组长度为0或1，已经有序，无需排序
  • 避免无限递归和栈溢出
• 示例：
  • 初始调用：quickSort(arr, 0, 5)（数组长度6）
  • 递归调用：quickSort(arr, 0, 2)（子数组长度3）
  • 终止条件：quickSort(arr, 0, 0)（子数组长度1，直接返回）

2. 分区循环：for (int j = low; j < high; j++)

• 为什么是 j < high 而不是 j <= high？
  • high 位置的元素是基准，最后单独处理
  • 避免在循环中处理基准元素，确保基准元素在最后被放置到正确位置
• 示例：
  • 数组 [10, 7, 8, 9, 1, 5]，high=5（基准是5）
  • 循环遍历 j 从0到4（索引5的基准不参与循环比较）

3. 指针 i 的初始化：int i = low - 1

• 为什么是 low - 1？
  • i 表示小于基准的区域的边界
  • 初始时该区域为空，所以边界在 low-1 位置
  • 第一次遇到小于基准的元素时，i++ 变为 low，然后交换到 low 位置
• 示例：
  • low=0，初始 i=-1
  • 遇到第一个小于基准的元素（如1），i 变为0，交换到位置0

4. 基准放置：swap(arr, i + 1, high)

• 为什么是 i + 1？
  • 循环结束后：
  • i 指向最后一个小于等于基准的元素
  • i+1 指向第一个大于基准的元素
  • 将基准与 i+1 位置的元素交换，确保：
  • 基准左边所有元素 ≤ 基准
  • 基准右边所有元素 > 基准
• 示例：
  • 分区后：[1, 5, 8, 9, 10, 7]（基准是5）
  • i=0（指向1），i+1=1（指向5）
  • 交换 arr[1] 和 arr[5]（基准5与7交换）→ [1, 5, 8, 9, 10, 7]（基准在正确位置）

---

完整执行流程示例

以数组 [10, 7, 8, 9, 1, 5] 为例：

初始调用：quickSort(arr, 0, 5)

1. 第一次分区（partition）：

   • 基准 pivot = arr[5] = 5
   • 初始化 i = -1
   • 遍历 j 从0到4：
     • j=0: 10 > 5 → 不操作
     • j=1: 7 > 5 → 不操作
     • j=2: 8 > 5 → 不操作
     • j=3: 9 > 5 → 不操作
     • j=4: 1 ≤ 5 → i=0, 交换 arr[0] 和 arr[4] → [1, 7, 8, 9, 10, 5]
   • 遍历结束，交换 arr[i+1]（arr[1]）和 arr[5] → [1, 5, 8, 9, 10, 7]
   • 返回基准位置 1

2. 递归左半部分：quickSort(arr, 0, 0)（只有一个元素，直接返回）

3. 递归右半部分：quickSort(arr, 2, 5)

   • 分区：基准 pivot = arr[5] = 7
   • 初始化 i = 1
   • 遍历 j 从2到4：
     • j=2: 8 > 7 → 不操作
     • j=3: 9 > 7 → 不操作
     • j=4: 10 > 7 → 不操作
   • 遍历结束，交换 arr[i+1]（arr[2]）和 arr[5] → [1, 5, 7, 9, 10, 8]
   • 返回基准位置 2

4. 递归左半部分：quickSort(arr, 2, 1)（不满足 low<high，返回）

5. 递归右半部分：quickSort(arr, 3, 5)

   • 分区：基准 pivot = arr[5] = 8
   • 初始化 i = 2
   • 遍历 j 从3到4：
     • j=3: 9 > 8 → 不操作
     • j=4: 10 > 8 → 不操作
   • 遍历结束，交换 arr[i+1]（arr[3]）和 arr[5] → [1, 5, 7, 8, 10, 9]
   • 返回基准位置 3

6. 递归左半部分：quickSort(arr, 3, 2)（返回）

7. 递归右半部分：quickSort(arr, 4, 5)

   • 分区：基准 pivot = arr[5] = 9
   • 初始化 i = 3
   • 遍历 j 从4到4：
     • j=4: 10 > 9 → 不操作
   • 遍历结束，交换 arr[i+1]（arr[4]）和 arr[5] → [1, 5, 7, 8, 9, 10]
   • 返回基准位置 4

8. 递归左半部分：quickSort(arr, 4, 3)（返回）

9. 递归右半部分：quickSort(arr, 5, 4)（返回）

最终结果：[1, 5, 7, 8, 9, 10]

---

关键点总结

1. 分区操作：快速排序的核心。通过分区将数组分为两部分，并确定基准元素的最终位置。
2. 基准选择：本实现选择最右边的元素作为基准。这种选择在数组有序或逆序时会导致最坏情况（时间复杂度O(n²)）。实际应用中可采用随机选择或三数取中等方法优化。
3. 递归终止条件：low < high 确保至少有两个元素才进行排序。
4. 指针 i 的作用：维护小于基准的区域的边界，确保所有小于等于基准的元素都被交换到该区域。
5. 时间复杂度：
   • 平均情况：O(n log n)
   • 最坏情况（如数组已有序）：O(n²)
6. 空间复杂度：O(log n)（递归调用栈的深度）
7. 稳定性：不稳定排序（分区过程中可能改变相等元素的相对位置）

快速排序是实际应用中最常用的排序算法之一，因为其平均时间复杂度优秀，且常数因子较小。通过优化基准选择（如随机化）可以避免最坏情况的发生。