快速排序是一种基于分治法的排序算法，其中

1. 通过选择一个枢轴元素（从数组中选择的元素）将数组划分为子数组。

在划分数组时，枢轴元素应该以这样的方式定位，即小于枢轴的元素保留在左侧，大于枢轴的元素位于枢轴的右侧。

1. 左右子数组也使用相同的方式进行划分。这个过程一直持续到每个子数组都包含一个元素。
2. 此时，元素已经排序。最后，将元素组合起来形成一个有序数组。

算法的图解

1. 选择枢轴元素

快速排序有不同的变体，其中枢轴元素是从不同位置选择的。在这里，我们将选择数组最右边的元素作为枢轴元素。

选择一个枢轴元素

1. 重新排列数组
   现在数组的元素被重新排列，使得小于枢轴的元素放在左边，大于枢轴的元素放在右边。

将所有较小的元素放在左侧，将较大的元素放在枢轴元素的右侧

下面是我们如何重新排列数组：

2.1 指针固定在枢轴元素上。枢轴元素与从第一个索引开始的元素进行比较。

枢轴元素与从第一个索引开始的元素的比较

2.2 如果元素大于枢轴元素，则为该元素设置第二个指针。

如果元素大于枢轴元素，则为该元素设置第二个指针。

2.3 现在，将枢轴与其他元素进行比较。如果到达小于枢轴元素的元素，则将较小的元素与较早找到的较大的元素交换。

枢轴与其他元素进行比较。

2.4 再次重复该过程以将下一个更大的元素设置为第二个指针。并且，将其与另一个较小的元素交换。

重复该过程以将下一个更大的元素设置为第二个指针。

2.5 该过程一直持续到到达倒数第二个元素。

该过程一直持续到到达倒数第二个元素。

2.6 最后，枢轴元素与第二个指针交换。

最后，枢轴元素与第二个指针交换。

1. 分治子数组

再次分别为左侧和右侧子部件选择枢轴元素。并且，重复步骤2。
子阵列被划分，直到每个子阵列由单个元素形成。此时，数组已经排序。

选择每一半的枢轴元素并使用递归放置在正确的位置

算法的伪码

quickSort(array, leftmostIndex, rightmostIndex)
  if (leftmostIndex < rightmostIndex)
    pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
    quickSort(array, leftmostIndex, pivotIndex - 1)
    quickSort(array, pivotIndex, rightmostIndex)
partition(array, leftmostIndex, rightmostIndex)
  set rightmostIndex as pivotIndex
  storeIndex <- leftmostIndex - 1
  for i <- leftmostIndex + 1 to rightmostIndex
  if element[i] < pivotElement
    swap element[i] and element[storeIndex]
    storeIndex++
  swap pivotElement and element[storeIndex+1]
return storeIndex + 1

算法可视化

借助下图，您可以了解快速排序算法的工作原理。

使用递归对枢轴左侧的元素进行排序

使用递归对枢轴右侧的元素进行排序

算法的实现

// Quick sort in Java

import java.util.Arrays;

class Quicksort {

  // method to find the partition position
  static int partition(int array[], int low, int high) {

    // choose the rightmost element as pivot
    int pivot = array[high];

    // pointer for greater element
    int i = (low - 1);

    // traverse through all elements
    // compare each element with pivot
    for (int j = low; j < high; j++) {
      if (array[j] <= pivot) {

        // if element smaller than pivot is found
        // swap it with the greatr element pointed by i
        i++;

        // swapping element at i with element at j
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }

    }

    // swapt the pivot element with the greater element specified by i
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;

    // return the position from where partition is done
    return (i + 1);
  }

  static void quickSort(int array[], int low, int high) {
    if (low < high) {

      // find pivot element such that
      // elements smaller than pivot are on the left
      // elements greater than pivot are on the right
      int pi = partition(array, low, high);

      // recursive call on the left of pivot
      quickSort(array, low, pi - 1);

      // recursive call on the right of pivot
      quickSort(array, pi + 1, high);
    }
  }
}

// Main class
class Main {
  public static void main(String args[]) {

    int[] data = { 8, 7, 2, 1, 0, 9, 6 };
    System.out.println("Unsorted Array");
    System.out.println(Arrays.toString(data));

    int size = data.length;

    // call quicksort() on array data
    Quicksort.quickSort(data, 0, size - 1);

    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

算法复杂性

时间复杂度

• 最坏情况复杂性[Big-O]：O(n**2**)

当提取的枢轴元件是最大或最小的元素时，会发生。
这种情况导致枢轴元素位于已排序数组的最末端的情况。一个子数组始终为空，另一个子数组包含 n - 1 个元素。因此，仅在此子数组上调用快速排序。
但是，快速排序算法对于分散的枢轴具有更好的性能。

• 最佳情况复杂度 [Big-omega]：O(n*log n)
  当枢轴元素始终是中间元素或靠近中间元素时，就会发生这种情况。

• 平均情况复杂度 [Big-theta]：O(n*log n)
  当上述条件不发生时，就会发生。

空间复杂度

• 快速排序的空间复杂度为 O(log n)

算法的应用

快速排序算法用于

• 编程语言有利于递归
• 时间复杂度很重要
• 空间复杂度很重要

相似的算法

• 插入排序
• 归并排序
• 选择排序
• 桶排序