Java快速排序算法的实现方法 |21xrx.com

Java快速排序算法的实现方法

2023-07-29 21:40:27 深夜i -- --

Java 快速排序算法实现方法

Java快速排序算法是一种高效的排序算法，它通过不断地划分数组，并将较小的元素放在左边，较大的元素放在右边，最终使得整个数组有序。下面将介绍Java快速排序算法的实现方法。

首先，我们需要定义一个快速排序的方法，接受一个整型数组和数组的起始位置和结束位置作为参数。在方法内部，我们首先判断起始位置是否小于结束位置，如果不小于，则直接返回。否则，我们选择一个基准元素，并以它为基准进行划分。

选择基准元素可以有多种方法，常见的有取数组的第一个元素、中间元素或者随机挑选一个元素作为基准。在这里，我们选择数组的中间元素为基准。定义两个指针，一个指向起始位置，另一个指向结束位置。然后，我们将两个指针不断向中间移动，直到它们相遇。在移动指针的过程中，我们分别找到一个比基准元素大和一个比基准元素小的元素，并交换它们的位置。

当两个指针相遇时，我们将基准元素与指针所指向的元素交换位置，此时基准元素的位置就确定下来了。然后，我们递归地对基准元素的左边部分和右边部分进行快速排序。

具体实现如下：


public static void quickSort(int[] arr, int low, int high) {
  if (low >= high)
    return;
  
  int left = low;
  int right = high;
  int pivot = arr[(low + high) / 2];
  while (left <= right) {
    while (arr[left] < pivot) {
      left++;
    }
    while (arr[right] > pivot)
      right--;
    
    if (left <= right) {
      int temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      left++;
      right--;
    }
  }
  quickSort(arr, low, right);
  quickSort(arr, left, high);
}
public static void main(String[] args) {
  int[] arr = 8;
  quickSort(arr, 0, arr.length - 1);
  for (int i : arr) {
    System.out.print(i + " ");
  }
}

上述代码中，首先定义了一个quickSort()方法来进行快速排序。在main()方法中，我们创建了一个待排序的数组arr，并调用quickSort()方法对其进行排序。最后，打印出排序后的数组。

通过以上步骤，我们实现了Java快速排序算法。该算法的时间复杂度为O(nlogn)，是一种高效的排序算法，常被使用在实际的软件开发中。

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

下一篇: KNN算法的Java实现

评论区

()

相似文章