用Java编写快速排序算法 |21xrx.com

用Java编写快速排序算法

2023-10-11 12:17:25 深夜i -- --

Java 快速排序算法编写

快速排序是一种常用的排序算法，它通过将一个数组分成两个子数组来递归地进行排序。这个算法的效率非常高，尤其是对于大型数据集。在Java中，我们可以使用递归来实现快速排序算法。

快速排序的基本思想是选择一个元素作为基准，然后将数组中小于基准的元素放在基准的左边，将大于基准的元素放在右边。然后，对左右子数组分别进行递归调用。这样，当子数组只有一个元素时，它就已经是有序的了。最后，通过递归的合并过程，整个数组就变成有序的了。

为了实现快速排序算法，我们首先需要一个方法来交换数组中两个元素的位置。然后，我们定义一个递归方法来对子数组进行排序。在这个方法中，我们选择数组中的一个元素作为基准，并将数组分成两个子数组。然后，我们将小于基准的元素放在基准的左边，大于基准的元素放在右边，并进行递归调用。最后，我们将左右子数组和基准进行合并，得到有序的数组。

下面是用Java编写快速排序算法的代码示例：


public class QuickSort {
  public static void main(String[] args) {
    int[] arr = 5;
    quickSort(arr, 0, arr.length - 1);
    for (int i : arr) {
      System.out.print(i + " ");
    }
  }
  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++;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
  }
}

在上面的代码中，我们首先定义了一个`QuickSort`类，并在`main`方法中创建了一个数组来测试快速排序算法。然后，我们调用`quickSort`方法对数组进行排序，并输出排序后的结果。

快速排序算法的时间复杂度为O(nlogn)，其中n是数组的长度。这使得它成为一种非常高效的排序算法。尽管快速排序在最坏情况下可能需要O(n^2)的时间，但这种情况非常罕见，并且可以通过选择合适的基准来避免。因此，快速排序是一种非常实用的排序算法，尤其适用于大型数据集的排序。

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

下一篇: 使用OpenCV进行人脸重建

评论区

()

相似文章