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

Java实现快速排序算法

2023-11-09 04:40:49 深夜i -- --

Java 快速排序算法

快速排序是一种常用的排序算法，它采用分治的思想来进行排序。与其他排序算法相比，快速排序的性能较好，通常被认为是最快的排序算法之一。快速排序的原理是通过递归将待排序数组分成两个子数组，然后对这两个子数组进行排序，最后合并成一个有序数组。

快速排序的实现思路是选择一个基准元素，通过一次遍历将数组分成两个部分，左边部分的所有元素小于等于基准元素，右边部分的所有元素大于等于基准元素。然后分别对左右两个部分进行递归排序，最后合并成一个有序数组。具体实现如下：


public class QuickSort {
  public 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 int partition(int[] arr, int low, int high) {
    int pivot = arr[low]; // 选择第一个元素作为基准元素
    int i = low;
    int j = high;
    while (i < j) {
      while (i < j && arr[j] >= pivot)
        j--;
      
      if (i < j) {
        arr[i++] = arr[j];
      }
      while (i < j && arr[i] <= pivot) {
        i++;
      }
      if (i < j) {
        arr[j--] = arr[i];
      }
    }
    arr[i] = pivot;
    return i;
  }
  public static void main(String[] args) {
    int[] arr = {8, 4, 2, 1, 9, 5, 7, 6, 3};
    QuickSort quickSort = new QuickSort();
    quickSort.quickSort(arr, 0, arr.length - 1);
    for (int num : arr) {
      System.out.print(num + " ");
    }
  }
}

上述代码演示了如何使用Java实现快速排序算法。通过调用`quickSort`方法传入待排序数组以及数组的起始和结束位置，即可完成对数组的排序。最后，通过遍历数组输出排序后的结果。

快速排序的时间复杂度为O(nlogn)，其中n为待排序数组的大小。平均情况下，快速排序的性能非常好，在实际应用中被广泛使用。但是在最坏情况下，快速排序的时间复杂度会退化到O(n^2)，这时可以使用一些优化策略来提高性能，如随机选择基准元素或者使用三数取中法来选择基准元素。

总之，快速排序是一种高效的排序算法，通过选择基准元素和分治的思想，可以很快地将一个无序的数组排序成一个有序的数组。使用Java实现快速排序算法相对简单，只需实现递归调用和基准元素的选择即可。

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

下一篇: 快速学习FFmpeg MP3实时流传输技术

评论区

()

相似文章