Java 实现快速排序 |21xrx.com

Java 实现快速排序

2023-08-01 11:40:57 深夜i -- --

排序算法数组递归分治时间复杂度

快速排序是一种高效的排序算法，适用于大规模数据的排序。它的核心思想是通过分治的方式将数组划分为较小的子数组，并且在每个子数组中选择一个基准元素，将其余元素与基准元素比较，并根据比较结果将元素分成两个部分。递归地对子数组进行相同的操作，直到每个子数组都只包含一个元素，然后将这些子数组按照顺序合并起来，即可得到有序的数组。

Java 提供了一种简洁而易于理解的实现快速排序的方法。下面是一个示例代码：


public class QuickSort {
  public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
      int pivotIndex = partition(array, low, high); // 在数组中选取基准元素，并返回其索引
      quickSort(array, low, pivotIndex - 1); // 对基准元素左侧的子数组进行排序
      quickSort(array, pivotIndex + 1, high); // 对基准元素右侧的子数组进行排序
    }
  }
  public static int partition(int[] array, int low, int high) {
    int pivotValue = array[high]; // 选取数组最后一个元素作为基准元素
    int i = low - 1;
    for (int j = low; j < high; j++) {
      if (array[j] < pivotValue) {
        i++;
        swap(array, i, j);
      }
    }
    swap(array, i + 1, high);
    return i + 1; // 返回基准元素的索引
  }
  public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  public static void main(String[] args) {
    int[] arr = 3;
    quickSort(arr, 0, arr.length - 1);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
  }
}

在上面的代码中，首先定义了一个 QuickSort 类，其中包含了 quickSort、partition 和 swap 三个静态方法。quickSort 方法是快速排序的主方法，它接收一个数组以及数组的下界和上界，通过递归调用 partition 方法和自身来实现排序。partition 方法利用选取的基准元素将数组划分成两个部分，并返回基准元素的索引。swap 方法用于交换数组中的两个元素。

在 main 方法中，创建了一个包含 6 个元素的数组，并将其作为参数传递给 quickSort 方法，然后打印排序后的数组。

快速排序的时间复杂度为 O(nlogn)，其中 n 为需要排序的元素的个数。由于快速排序是一个原址排序算法，它对内存的要求较低，是一种常用的排序算法。在实际应用中，我们可以通过一些优化的方法来提高快速排序的性能，例如随机选择基准元素、三路快速排序等。

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

下一篇: OpenCV实现像素坐标到实际距离的转换

评论区

()

相似文章