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

Java实现快速排序算法的代码实例

2023-10-15 07:06:57 深夜i 13 0

Java 快速排序算法代码实例

快速排序是一种常用的排序算法，它通过分区操作将数组分成较小和较大的两个子数组，然后递归地排序子数组。该算法的时间复杂度为O(nlogn)，是一种高效的排序算法。在Java中，我们可以很容易地实现快速排序算法。

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

public class QuickSort {
  public void sort(int[] arr, int low, int high) {
    if (low < high) {
      int pivot = partition(arr, low, high);
      sort(arr, low, pivot - 1);
      sort(arr, pivot + 1, high);
    }
  }
  private 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;
  }
  public static void main(String[] args) {
    int[] arr = 64;
    int n = arr.length;
    QuickSort quickSort = new QuickSort();
    quickSort.sort(arr, 0, n - 1);
    System.out.println("排序后的数组：");
    for (int i = 0; i < n; i++) {
      System.out.print(arr[i] + " ");
    }
  }
}

在这个例子中，我们创建了一个名为`QuickSort`的类。这个类有一个`sort`方法，用于实现快速排序算法。`sort`方法接收一个整数数组`arr`以及数组的开始索引`low`和结束索引`high`作为参数。

在`sort`方法中，我们首先判断`low`是否小于`high`，如果是，则进行分区操作。我们选择数组的最后一个元素作为基准元素`pivot`，并设定一个索引`i`，初始值为`low - 1`。

接下来，我们使用一个循环遍历从`low`到`high - 1`的所有元素。如果当前元素小于或等于基准元素`pivot`，则将`i`增加1，并交换`arr[i]`和`arr[j]`的值，将较小的元素放在`i`的位置。

最后，我们将基准元素`pivot`与`arr[i + 1]`交换位置，将基准元素放在正确的位置上，并返回基准元素的索引。

在`main`方法中，我们创建一个整数数组`arr`，并对其进行快速排序。然后，我们打印排序后的数组。

总结起来，Java实现快速排序算法的代码很简单，但它可以高效地对数组进行排序。通过递归地分区和排序子数组，快速排序算法在实际应用中广泛使用。

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

下一篇: ROS使用OpenCV显示图像

评论区

相似文章