本教程显示了如何用Java编写快速排序程序。快速排序也是类似于合并排序的"分而治之算法"。

快速排序算法

快速排序的工作方式如下

• 选择一个元素作为枢轴，然后围绕该枢轴划分所有元素。
• 价值小于枢轴的所有元素都位于枢轴之前。
• 价值高于枢轴的所有元素都位于枢轴之后。

将元素围绕支点进行分区后，我们将获得两个子数组。枢轴左侧的一个值小于枢轴，另一个在枢轴右侧的一个值大于枢轴。对于这2个子数组，递归执行-3.

在实施"快速排序"时，我们必须做出的决定之一就是应选择哪个值作为枢轴，选项是

• 第一个元素作为枢轴。
• 最后一个元素作为枢轴(本文中的快速排序实现使用此方法)
• 中间元素作为枢轴。
• 排序项目的中位数。

例如，假设输入数组为[40、62、49、10、39、65、75、32、53、46]

下图说明了分区过程的起点。

从左向右移动以寻找大于枢轴值的元素。从右侧向左侧移动，寻找小于枢轴的元素。找到此类元素后，请交换这些元素。在我们的示例中，这样的元素在交换它们时分别为62(左)和32(右)
[40、32、49、10、39、65、75、62、53、46]

再次移动，发现这些元素在交换它们时变为49(从左)和39(从右)，数组变为[40、32、39、10、49、65、75、62、53、46]。此时，左侧指向39，右侧指向49.

一旦左侧变得大于右侧(在我们的示例中会发生这种情况，当左侧开始指向49，右侧开始指向39时)，请用枢轴交换左侧，这将为我们提供两个分区，并在其最终位置枢纽[40，32，39，10 ，46，65，75，62，53，49]

再次对分区数组重复该过程。

快速排序Java程序

public class QuickSort {
  public static void main(String[] args) {
    int[] arr = {108, 52, 23, 32, 3, 56, 87, 62, 37, 91, 34, 78};
    System.out.println("Original array- " + Arrays.toString(arr));
    quickSort(arr, 0, arr.length-1);
    System.out.println("Sorted array after quick sort- " + Arrays.toString(arr));
  }
    
  private static void quickSort(int[] arr, int lower, int upper){
    // base case
    if(upper - lower <= 0){
        return;
    }else{
      int partition = partition(arr, lower, upper);
      // recursive call with smaller values partition
      quickSort(arr, lower, partition-1);
      // recursive call with higher values partition
      quickSort(arr, partition+1, upper);
    }
  }
    
  private static int partition(int[] arr, int lower, int upper){
    int pivot = arr[upper];
    int left = lower - 1;
    int right = upper;
    while(left <= right) {
      // find an element greater than pivot 
      // starting from the left side
      while(arr[++left] < pivot);
      // find an element smaller than pivot
      // starting from the right side
      while(right > 0 && arr[--right] > pivot);
      // break out of loop whenever left is greater than right
      if(left >= right)
        break;
      else{
        swap(arr, left, right);
      }
    }
    // to get pivot at its proper place
    swap(arr, left, upper);
    return left;
  }
    
  private static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

输出：

Original array- [108, 52, 23, 32, 3, 56, 87, 62, 37, 91, 34, 78]
Sorted array after quick sort- [3, 23, 32, 34, 37, 52, 56, 62, 78, 87, 91, 108]

快速排序时间和空间复杂性

快速排序的平均时间和最佳情况时间复杂度为O(n * logn)。最坏的情况是，当枢轴值不能正确划分元素时，时间复杂度可能为O(n2)。

当以递归方式实现递归调用方法堆栈时，需要额外的空间，因此快速排序的最坏情况下的空间复杂度是O(n)。