前言

快速排序是一种高效的就地排序算法，如果实施得当，它的执行速度通常比归并排序和堆排序快两到三倍。快速排序是一种比较排序，这意味着它可以对定义了小于关系的任何类型的项目进行排序。在有效的实现中，它通常不是一个稳定的排序。

平均而言，快速排序会进行O(n.log(n))比较来对n项目进行排序。在最坏的情况下，会进行O(n²)次比较，这种情况比较少。

与合并排序一样，快速排序是一种分治算法。它选择一个元素作为中心点，并围绕选择的中心点对给定数组进行划分。有许多不同版本的快速排序以不同的方式选择中心点。 

1. 始终选择第一个元素作为中心点。
2. 始终选择最后一个元素作为中心点。
3. 选择一个随机元素作为中心点。
4. 选择中位数作为中心点。

快速排序的关键过程是 partition()。划分的目标是，给定一个数组和数组的一个元素 x 作为中心点，将 x 放在已排序数组中的正确位置，并将所有较小的元素（小于 x）放在 x 之前，并将所有较大的元素（大于 x）放在后面X。

递归的基本情况是 size 的数组1，它们永远不需要排序。上图显示了快速排序算法的每个步骤中选择最左边的元素作为划分点，通过划分点对数组进行分区，并在分区过程后得到的两个子数组上递归：

Java示例

// Java implementation of QuickSort
import java.io.*;
 
class GFG{
     
// 交换两个元素
static void swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
/* 此函数以最后一个元素为中心点，将中心点元素放置在其正确的位置数组，将所有较小的（小于pivot）在中心点的左边，将更大的元素放在右边 */
static int partition(int[] arr, int low, int high)
{
     
    // 中心点
    int pivot = arr[high];
     
    int i = (low - 1);
 
    for(int j = low; j <= high - 1; j  )
    {
         
        // 如果当前元素小
        if (arr[j] < pivot)
        {
            i  ;
            swap(arr, i, j);
        }
    }
    swap(arr, i   1, high);
    return (i   1);
}
 
/*
          arr[]  要排序的数组
          low  起始索引
          high  结束索引
 */
static void quickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
         
        // pi 分区索引
        int pi = partition(arr, low, high);
 
        // 分别对元素进行排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi   1, high);
    }
}
 
// 打印数组
static void printArray(int[] arr, int size)
{
    for(int i = 0; i < size; i  )
        System.out.print(arr[i]   " ");
         
    System.out.println();
}
 
public static void main(String[] args)
{
    int[] arr = { 10, 7, 8, 9, 1, 5 };
    int n = arr.length;
    System.out.println("排序前: ");
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    System.out.println("排序后: ");
    printArray(arr, n);
}
}
 

输出 排序前： 10 7 8 9 1 5 排序后： 1 5 7 8 9 10

性能

快速排序的最坏情况时间复杂度是O(n²)，其中n是输入的大小。当中心点恰好是列表中的最小或最大元素或所有数组元素相等时，会发生最坏的情况。这将导致最不平衡的分区，因为中心点将数组分成大小为 0 和 的两个子数组n-1。如果这在每个分区中重复发生（例如，我们已排序数组），那么每个递归调用都会处理一个大小比前一个列表小一的列表，从而导致O(n 2 )时间。

T(n) = T(n-1) cn = O(n²)

快速排序的最佳时间复杂度是O(n.log(n))。最好的情况发生在中心点将数组分成两个几乎相等的部分时。现在每个递归调用都会处理一个大小减半的列表。

T(n) = 2 T(n/2) cn = O(n.log(n))

快速排序算法所需的辅助空间为调用堆栈的O(n) 。

这篇好文章是转载于：学新通技术网