《Java 实现快速排序：原理剖析与代码详解》

时间：2024-11-04 13:41:02

目录

一、引言

二、快速排序原理

1. 选择基准值

2. 划分操作

3. 递归排序

三、代码分析

1. 代码整体结构

2. main方法

3. sort方法（快速排序核心逻辑）

四、测试结果

一、引言

排序算法在数据处理和计算机编程领域中占据着举足轻重的地位，它们能够将无序的数据按照特定的规则整理成有序的序列，方便后续的分析与操作。快速排序作为一种高效且应用广泛的排序算法，以其独特的分治思想和相对优秀的时间复杂度表现备受关注。在这篇博客中，我们将深入解析一段用 Java 实现快速排序的代码，帮助大家透彻理解快速排序的原理以及代码的具体实现细节。

二、快速排序原理

快速排序基于分治策略，其核心思想可以概括为以下几个步骤：

1. 选择基准值

首先从待排序的数组中选取一个元素作为基准值（pivot）。这个基准值的选取方式有多种，常见的是选取数组的第一个元素、最后一个元素或者中间元素等。在我们给出的代码中，选取的是数组的第一个元素作为基准值。

2. 划分操作

将数组划分为两部分，使得左边部分的所有元素都小于等于基准值，右边部分的所有元素都大于等于基准值。这一步是通过两个游标（指针）从数组的两端开始向中间移动来实现的。具体操作如下：

  • 一个游标从数组的末尾开始，向前移动，直到找到一个小于基准值的元素。
  • 另一个游标从数组的开头开始，向后移动，直到找到一个大于基准值的元素。
  • 当这两个游标找到符合条件的元素后，将它们所指向的元素进行交换。
  • 不断重复上述过程，直到两个游标相遇。

3. 递归排序

在完成一次划分操作后，基准值就处于它在排序后应该所处的大致位置（即左边的元素都比它小，右边的元素都比它大）。然后，对划分后的左右两部分子数组分别递归地应用快速排序算法，直到整个数组都被排序完成。

三、代码分析

1. 代码整体结构

以下是我们要详细分析的 Java 快速排序代码：

package 排序;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {

        int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        //定义变量保存基准数
        int base = arr[left];
        //定义一个i游标和j游标
        int i = left;
        int j = right;

        while (i!= j) {
            //j游标从后往前移动，找比基准数小的
            while (arr[j] >= base && i < j) {
                j--;
            }
            //i游从前往后，找比基准数大的
            while (arr[i] <= base && i < j) {
                i++;
            }
            //交换
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //i和j相遇,基准数和相遇位置进行交换
        arr[left] = arr[i];
        arr[i] = base;

        //排序左边
        sort(arr, left, i - 1);
        //排序右边
        sort(arr, i + 1, right);
    }
}

2. main方法

在 main 方法中，首先定义了一个整数数组 arr，并初始化其值为 {5, 7, 4, 2, 0, 3, 1, 6}。这就是我们要进行排序的原始数组。

int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};

然后调用了 sort 方法，并将数组 arr 以及数组的起始索引 0 和结束索引 arr.length - 1 作为参数传递给它，目的是对整个数组进行排序操作。

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

最后，在排序完成后，使用 Arrays.toString 方法将排序后的数组以字符串的形式输出到控制台，以便直观地查看排序的结果。

System.out.println(Arrays.toString(arr));

3. sort方法（快速排序核心逻辑）

sort 方法实现了快速排序的核心逻辑，下面我们来详细剖析其内部的操作。

  • 递归终止条件：
    当 left 大于等于 right 时，意味着当前子数组的长度为 0 或 1，已经是排序好的状态，所以直接返回，不再进行排序操作。
if (left >= 23;
    return;
}
  • 选择基准值：
    选取数组的第一个元素作为基准值，并将其保存在变量 base 中。
int base = arr[left];

  • 划分操作（双游标移动与交换）：
    定义了两个游标 i 和 j，分别初始化为数组的起始索引 left 和结束索引 right。然后通过两个嵌套的 while 循环来实现划分操作。

    • 外层 while 循环：
      条件是 i!= j，确保两个游标没有相遇，只要它们没有相遇，就继续在数组中寻找可以交换的元素。

    • 内层第一个 while 循环：
      从数组的末尾（由 j 指向）开始，向前移动游标 j，只要 arr[j] >= base（即当前元素大于等于基准值）且 i < j（确保游标还没有相遇），就继续让 j 往前移动，直到找到一个小于基准值的元素为止。

    • 内层第二个 while 样：
      从数组的开头（由 i 指向）开始，向后移动游标 i，只要 arr[i] <= base（即当前元素小于等于基准值）且 i < j（确保游标还没有相遇），就继续让 i 往后移动，直到找到一个大于基准值的元素为止。

    • 元素交换：
      当两个游标 i 和 j 分别找到符合条件的元素后（即 arr[j] < base 且 arr[i] > base），通过临时变量 temp 来交换它们所指向的元素，使得数组的左边部分逐渐出现小于等于基准值的元素，右边部分逐渐出现大于等于基准值的元素。

while (arr[j] >= base && i < j) {
    j--;
}
while (arr[i] <= base && i < j) {
    i++;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

  • 基准值归位：
    当两个游标 i 和 j 相遇时，将基准值 base（最初保存在 arr[left]）与相遇位置的元素（此时 arr[i]）进行交换，这样基准值就处于它在排序后应该所处的大致位置，即左边的元素都比它小，右边的元素都比它大。
arr[left] = arr[i];
arr[i] = base;
  • 递归排序左右子数组：
    在完成一次划分操作后，对划分后的左右两部分子数组分别递归地应用快速排序算法。对左边子数组，调用 sort 方法，传入起始索引 left 和结束索引 i - 1；对右边子数组，调用 sort 方法，传入起始索引 i + 1 和结束索引 right。通过不断递归，直到整个数组都被排序完成。

//排序左边
sort(arr, left, i - 1);
//排序右边
sort(arr, i + 1, right);

四、测试结果

当我们运行上述代码时，对于给定的初始数组 {5, 7, 4, 2, 0, 3, 1, 6}，经过快速排序后，控制台会输出排序后的数组，其结果应该是 {0, 1, 2, 3, 4, 5, 6, 7}。

相关文章