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

Java实现快速排序算法

2023-07-29 07:01:28 深夜i 12 0

Java 快速排序算法实现

快速排序是一种常用的排序算法，在Java中可以很容易地实现。快速排序算法的核心思想是通过将一个数组划分为较小的子数组，然后对这些子数组进行排序。具体实现步骤如下：

1. 选择一个基准元素（pivot），将数组分为左右两个子数组。

2. 将小于基准元素的元素放在左子数组中，将大于基准元素的元素放在右子数组中。

3. 对左右子数组递归地应用快速排序算法，直到子数组的长度为1或者为空。

4. 合并排序好的左右子数组，得到最终排序结果。

下面是使用Java实现快速排序算法的例子：


public class QuickSort {
  public static void main(String[] args) {
    int[] arr = 2;
    quickSort(arr, 0, arr.length - 1);
    System.out.println("排序结果: " + Arrays.toString(arr));
  }
  public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
      int pivotIndex = partition(arr, low, high);
      quickSort(arr, low, pivotIndex - 1);
      quickSort(arr, pivotIndex + 1, high);
    }
  }
  public static int partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int i = low + 1;
    int j = high;
    while (true) {
      while (i <= j && arr[i] < pivot) {
        i++;
      }
      while (i <= j && arr[j] > pivot)
        j--;
      
      if (i > j)
        break;
      
      swap(arr, i, j);
    }
    swap(arr, low, j);
    return j;
  }
  public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

通过这段代码，我们可以将数组 3进行快速排序。在实现过程中，我们选择了数组的第一个元素作为基准元素，并将小于基准元素的元素放在左子数组中，将大于基准元素的元素放在右子数组中。然后，对左右子数组递归地应用快速排序算法，直到子数组的长度为1或者为空。最后，通过合并排序好的左右子数组，我们得到了排序结果。运行代码，可以得到如下输出：


排序结果: [2, 3, 4, 5, 8]

快速排序算法是一种高效的排序算法，它的平均时间复杂度为O(nlogn)，在处理大型数据集时表现出色。由于Java的面向对象特性以及简洁的语法，我们可以很容易地使用Java来实现快速排序算法。希望上述的代码以及解释能对你理解Java实现快速排序算法有所帮助。

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

下一篇: 使用opencv实现Fisherface人脸识别算法

评论区

相似文章