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

Java快速排序实现

2023-06-16 15:41:57 深夜i -- --

Java 快速排序递归

快速排序是一种高效的排序算法，能够在最糟糕的情况下也能以O(n log n)时间复杂度完成排序。在Java中，我们可以使用递归实现快速排序算法。

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

public static void quickSort(int[] arr, int left, int right) {
  if (left >= right)
    return;
  
  int pivotIndex = partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);
}
private static int partition(int[] arr, int left, int right) {
  int pivot = arr[left];
  int i = left + 1;
  int j = right;
  while (i <= j) {
    while (i <= j && arr[i] <= pivot) {
      i++;
    }
    while (i <= j && arr[j] > pivot)
      j--;
    
    if (i <= j) {
      swap(arr, i, j);
    }
  }
  swap(arr, left, j);
  return j;
}
private static void swap(int[] arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

上述代码中，我们首先定义了一个`quickSort`方法，用来实现快速排序。在该方法中，我们首先判断左右指针是否相遇，若相遇则直接返回，否则我们取最左边的元素`pivot`为基准值，对数组进行一次分区操作，将小于`pivot`的元素移动到左边，大于等于`pivot`的元素移动到右边。然后，递归调用`quickSort`方法，对左侧和右侧的子数组进行排序。

接下来，我们定义了一个`partition`方法，用来实现分区操作。在该方法中，我们采用快慢指针的思路，将大于`pivot`的元素和小于等于`pivot`的元素交换位置，直到左右指针相遇。最后，我们再将`pivot`与左右指针相遇的元素交换位置，返回左右指针相遇的位置即可。

以上就是Java快速排序的实现方式。使用该算法能够快速高效地将一个乱序数组进行排序。

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

下一篇: Java和C哪个更好

评论区

相似文章