21xrx.com
2025-03-26 07:22:32 Wednesday
文章检索 我的文章 写文章
Java 实现快速排序算法
2023-06-19 06:18:12 深夜i     24     0
Java 快速排序 算法

在计算机科学中，快速排序（QuickSort）是一种排序算法，它是对冒泡排序的一种改进。快速排序由于其在通常情况下的高效性被广泛使用，通常被认为是最快的通用排序算法之一。在Java程序中，快速排序算法的代码如下：

public class QuickSort{
  
  public void quickSort(int[] arr, int begin, int end) {
    if (begin < end) {
      int partitionIndex = partition(arr, begin, end);
      quickSort(arr, begin, partitionIndex-1);
      quickSort(arr, partitionIndex+1, end);
    }
  }
  private int partition(int[] arr, int begin, int end) {
    int pivot = arr[end];
    int i = (begin-1);
  
    for (int j = begin; j < end; j++) {
      if (arr[j] <= pivot) {
        i++;
        int swapTemp = arr[i];
        arr[i] = arr[j];
        arr[j] = swapTemp;
      }
    }
  
    int swapTemp = arr[i+1];
    arr[i+1] = arr[end];
    arr[end] = swapTemp;
  
    return i+1;
  }
}

该代码使用递归方法来实现快速排序。在 `quickSort` 函数中，我们使用 `partition` 函数来将数组划分为两个子数组，并将枢轴元素放在正确的位置。然后，我们递归地排序左右两个子数组。

快速排序算法的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(\log n)$。

  
  

评论区

请求出错了