Java中实现快速排序算法的方法有哪些？ |21xrx.com

Java中实现快速排序算法的方法有哪些？

2023-07-12 14:02:26 深夜i -- --

Java 快速排序算法实现方法

快速排序算法是一种基于分治思想的高效排序算法。在Java语言中，也有多种实现快速排序的方法。

一、递归实现

最常用的实现快速排序的方法是递归。这种方法将排序数组分为两个子数组，并递归地进行排序。递归的结束条件是子数组的大小为1或0。具体实现可以参考以下代码：

public static void quickSort(int[] arr, int low, int high) {

if (low < high) {

int partitionIndex = partition(arr, low, high);

quickSort(arr, low, partitionIndex - 1);

quickSort(arr, partitionIndex + 1, high);

}

private 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;

}

二、迭代实现

除了递归实现以外，还可以使用迭代实现快速排序。这种方法利用栈来实现递归。具体实现可以参考以下代码：

public static void quickSort(int[] arr, int low, int high) {

Stack stack = new Stack<>();

stack.push(low);

stack.push(high);

while (!stack.isEmpty()) {

int h = stack.pop();

int l = stack.pop();

int partitionIndex = partition(arr, l, h);

if (partitionIndex - 1 > l) {

stack.push(l);

stack.push(partitionIndex - 1);

}

if (partitionIndex + 1 < h) {

stack.push(partitionIndex + 1);

stack.push(h);

}

三、Java自带的快速排序实现

在Java中，除了手动实现快速排序算法以外，也可以使用Java自带的快速排序实现。具体实现可以参考以下代码：

public static void quickSort(int[] arr, int low, int high) {

Arrays.sort(arr, low, high + 1);

}

以上就是在Java中实现快速排序算法的三种方法。无论是递归实现还是迭代实现，还是Java自带的实现，都可以在一定程度上提高排序效率和性能。如果需要综合考虑速度和空间的平衡，选择适合自己的方法即可。

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

下一篇: C++ GUI框架介绍

评论区

()

相似文章