Java快速排序算法代码解析 |21xrx.com

Java快速排序算法代码解析

2023-10-18 10:53:35 深夜i -- --

Java 快速排序算法代码解析

快速排序是一种经典的排序算法，被广泛用于各种编程语言中。在Java中，快速排序的实现需要对代码进行解析，以便理解其工作原理和实现细节。

以下是一个使用Java实现快速排序算法的示例代码：

public class QuickSort {
  
  public static void main(String[] args) {
    int[] arr = 2;
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
  }
  
  public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
      int pivot = partition(arr, low, high);
      
      quickSort(arr, low, pivot - 1);
      quickSort(arr, pivot + 1, high);
    }
  }
  
  public 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;
  }
  
  public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

这段代码首先定义了一个名为 `QuickSort` 的类，其中包含了 `main` 方法作为程序的入口。在 `main` 方法中，我们创建了一个数组 `arr` 并初始化了一些整数值。然后，我们调用 `quickSort` 方法对该数组进行排序，并通过 `Arrays.toString(arr)` 方法将结果打印出来。

`quickSort` 方法是实现快速排序的核心部分。它接受一个数组 `arr` 以及待排序部分的第一个元素索引 `low` 和最后一个元素索引 `high`。在方法内部，首先判断 `low` 是否小于 `high`，如果是，则继续进行排序；否则，表示已经完成排序，直接返回。接下来，我们调用 `partition` 方法来确定一个基准元素 `pivot`，然后通过递归调用 `quickSort` 方法对基准元素左右两边的子数组进行排序。

`partition` 方法用于确定基准元素的位置，并在分区过程中将小于或等于基准元素的元素移到其左侧，将大于基准元素的元素移到其右侧。首先，我们选择基准元素 `pivot` 为数组的最后一个元素 `arr[high]`，并定义一个变量 `i` 来跟踪小于或等于基准元素的元素的位置。然后，我们使用一个循环遍历数组中 `low` 到 `high-1` 之间的元素。如果当前元素小于或等于基准元素，则将 `i` 增加1，并交换 `arr[i]` 和 `arr[j]` 的位置。最后，我们将基准元素 `pivot` 与 `arr[i+1]` 交换位置，确保基准元素在最终排序中的正确位置。最后，返回基准元素的索引加1。

在排序过程中，我们使用了一个名为 `swap` 的辅助方法，用于交换数组中两个元素的位置。

综上所述，这段代码实现了快速排序算法。通过对数组进行拆分和递归排序的方式，可以在效率上迅速地将数组排序。有了这个理解，我们可以在需要时根据自己的需求进行修改和优化。

上一篇: idea打包java可执行jar包

下一篇: 使用OpenCV实现图像抠图

评论区

相似文章