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

快速排序算法的Java实现

2023-11-22 21:54:31 深夜i 39 0

快速排序算法 Java实现排序分治算法

快速排序是一种常用的排序算法，利用分治的思想，通过递归的方式将待排序的序列分为两部分，然后对这两部分分别进行排序，最后将两部分合并起来，完成整个排序过程。下面是快速排序算法的Java实现。

首先，我们需要定义一个方法来实现快速排序。该方法需要接收一个待排序的整型数组，以及数组的开始和结束位置作为参数。

public static void quickSort(int[] array, int start, int end) {
  if (start < end) {
    int pivot = partition(array, start, end); // 将数组划分为两部分
    quickSort(array, start, pivot - 1); // 对左子序列进行排序
    quickSort(array, pivot + 1, end); // 对右子序列进行排序
  }
}

在快速排序的过程中，我们需要选择一个基准元素，将数组划分为两部分。基准元素可以是任意一个已存在于数组中的元素，通常选择数组的开始位置或结束位置的元素作为基准。这里我们选择将数组的开始位置的元素作为基准。

接下来，我们需要实现一个方法来划分数组，并返回基准元素的位置。

public static int partition(int[] array, int start, int end) {
  int pivot = array[start]; // 选择开始位置的元素作为基准
  int left = start + 1; // 左指针
  int right = end; // 右指针
  while (left <= right) {
    if (array[left] <= pivot) {
      left++;
    } else if (array[right] >= pivot)
      right--;
    else {
      // 交换左右指针所指向的元素
      int temp = array[left];
      array[left] = array[right];
      array[right] = temp;
      left++;
      right--;
    }
  }
  // 将基准元素与右指针所指向的元素进行交换
  int temp = array[start];
  array[start] = array[right];
  array[right] = temp;
  return right;
}

最后，我们可以使用上述的快速排序方法对一个整型数组进行排序。

public static void main(String[] args) {
  int[] array = 1;
  quickSort(array, 0, array.length - 1);
  System.out.println("排序结果：");
  for (int num : array) {
    System.out.print(num + " ");
  }
}

运行程序后，我们可以看到排序结果为：1 2 3 4 5 6 7 8，证明快速排序算法的实现是正确的。

总结来说，快速排序是一种高效的排序算法，借助分治的思想和递归的方式，可以在平均情况下达到O(nlogn)的时间复杂度。通过上述的Java实现，我们可以轻松地对一个整型数组进行排序。

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

下一篇: 使用OpenCV进行数字矫正

评论区

相似文章