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

内容纲要

快速排序 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)`

第一次分区（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
递归左半部分：quickSort(arr, 0, 0)（只有一个元素，直接返回）
递归右半部分：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
递归左半部分：quickSort(arr, 2, 1)（不满足 low<high，返回）
递归右半部分：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
递归左半部分：quickSort(arr, 3, 2)（返回）
递归右半部分：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
递归左半部分：quickSort(arr, 4, 3)（返回）
递归右半部分：quickSort(arr, 5, 4)（返回）

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

关键点总结

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

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

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

快速排序 Java 实现

快速排序 Python 实现

逐行代码解析

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

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

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

关键条件解析

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

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

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

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

完整执行流程示例

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

关键点总结

林清杨

Leave a Comment 取消回复

快速排序 Java 实现

快速排序 Python 实现

逐行代码解析

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

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

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

关键条件解析

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

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

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

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

完整执行流程示例

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

关键点总结

林清杨

Leave a Comment 取消回复

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

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

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

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

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

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

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

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