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

Java快速排序算法的实现

2023-10-31 19:07:13 深夜i -- --

Java 快速排序算法实现算法分析性能优化

Java快速排序算法是一种常用的排序算法，它能够快速而有效地将一个无序的数组进行排序。快速排序算法的核心思想是通过选取一个基准元素，将数组分割成两个子数组，其中一个子数组的元素都比基准元素小，另一个子数组的元素都比基准元素大，然后再对这两个子数组进行递归排序，最终将整个数组排序完成。

快速排序算法的实现步骤如下：

1. 选择一个基准元素，可以是数组中的任意一个元素。

2. 将数组分成两个子数组，确保一个子数组中的元素都比基准元素小，另一个子数组中的元素都比基准元素大。可以通过定义两个指针，一个从数组的左端开始向右移动，直到找到一个比基准元素大的元素；另一个从数组的右端开始向左移动，直到找到一个比基准元素小的元素；然后交换这两个元素的位置。不断重复这个过程，直到两个指针相遇，此时将基准元素与相遇点的元素进行交换。

3. 递归对两个子数组进行排序，直到子数组的长度为1。

4. 合并两个子数组，得到排序完成的数组。

下面是Java快速排序算法的实现代码：


public class QuickSort {
  public static void main(String[] args) {
    int[] array = 3;
    quickSort(array, 0, array.length - 1);
    for (int i : array) {
      System.out.print(i + " ");
    }
  }
  public static void quickSort(int[] array, int left, int right) {
    if (left >= right)
      return;
    
    int pivot = partition(array, left, right);
    quickSort(array, left, pivot - 1);
    quickSort(array, pivot + 1, right);
  }
  public static int partition(int[] array, int left, int right) {
    int pivot = array[left];
    while (left < right) {
      while (left < right && array[right] >= pivot)
        right--;
      
      array[left] = array[right];
      while (left < right && array[left] <= pivot) {
        left++;
      }
      array[right] = array[left];
    }
    array[left] = pivot;
    return left;
  }
}

运行以上代码，将会输出排序完成的数组。快速排序算法的时间复杂度为O(n log n)，是一种高效的排序算法，通常被广泛应用于各种排序场景中。无论是在算法竞赛中还是在日常的开发工作中，掌握快速排序算法都是非常重要的技能。

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

下一篇: Java中的operate方法指南

评论区

()

相似文章