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

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

2023-07-10 18:32:00 深夜i 8 0

Java 快速排序算法常见实现方法

Java作为一门常用的编程语言，其提供了多种快速排序算法的实现方法。下面将会介绍几种最常见的Java快速排序算法实现方法。

1. 基本快速排序算法

基本快速排序算法最为简单，其主要思路是先选取一个元素作为基准值，然后将列表中的元素分成两个部分：小于基准值和大于基准值的。接着递归地对两个部分进行排序。

基本快速排序算法的Java代码如下：

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);//递归排序后半部分
  }
}
private static int partition(int[] arr, int low, int high) {
  int pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] >= pivot)
      high--;
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot)
      low++;
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

2. 三向切割快速排序算法

三向切割快速排序算法是对基本快速排序算法的改进，其在处理有大量重复元素的数组时，速度更加快。

三向切割快速排序算法的Java代码如下：

public static void quickSort(int[] arr, int low, int high) {
  if (low >= high)
    return;
  int lt = low, i = low + 1, gt = high;
  int pivot = arr[low];
  while (i <= gt) {
    if (arr[i] < pivot)
      swap(arr, lt++, i++);
    else if (arr[i] > pivot)
      swap(arr, i, gt--);
    else
      i++;
  }
  quickSort(arr, low, lt - 1);
  quickSort(arr, gt + 1, high);
}
private static void swap(int[] arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

3. 新式快速排序算法

新式快速排序算法是由蒂姆·彼得斯（Tim Peters）所发明的，是Python语言内置排序函数sorted()的默认排序算法，被证明具有相对较好的时间和空间复杂度。

新式快速排序算法的Java代码如下：

public static void quickSort(int[] arr, int low, int high) {
  if (low >= high)
    return;
  int pivot = medianOfThree(arr, low, high);//选取中位数作为基准值
  int i = low, j = high - 1;
  while (true) {
    while (arr[++i] < pivot) ;
    while (arr[--j] > pivot) ;
    if (i < j)
      swap(arr, i, j);
    else
      break;
  }
  swap(arr, i, high - 1);
  quickSort(arr, low, i - 1);
  quickSort(arr, i + 1, high);
}
private static int medianOfThree(int[] arr, int left, int right) {
  int center = (left + right) / 2;
  if (arr[left] > arr[center])
    swap(arr, left, center);
  if (arr[left] > arr[right])
    swap(arr, left, right);
  if (arr[center] > arr[right])
    swap(arr, center, right);
  swap(arr, center, right - 1);
  return arr[right - 1];
}
private static void swap(int[] arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

综上所述，Java实现快速排序算法的常见实现方法有基本快速排序算法、三向切割快速排序算法以及新式快速排序算法。不同的排序算法适用于不同的场景，根据实际需求选择合适的算法，可以提高程序的效率和稳定性。

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

下一篇: C++中有long long数据类型吗？

评论区

相似文章