快速排序（Quick Sort）

快速排序是现今为止不管是理论上还是实际上都是最高效的一种通用排序方法。它使用分治法（Divide and conquer）策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。

希尔排序算法的运作如下：

1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）。
2. 分割（partition）：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。
3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
4. 递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。简单直接的方式可以为随机选取一个元素作为基准。相对改进的方法是选取一个小样本中的中位数作为基准，以最大限度地使基准将序列分成大小相似的两部分。由于选取样本以及计算中位数会有额外的计算开销，因此，这实际应用的样本的大小一般只取到3.

Quick Sort (Source: https://visualgo.net)

C#代码

//使用 3-way partitioning
void QuickSort(int[] numbers, int left, int right)
{
    if (left >= right) return;

    int lt = left, i = left+1, gt = right, v = numbers[left];
    while (i <= gt)
    {
        if(number[i] < v) { 
            Swap(numbers, lt++, i++);
        } else if (number[i] > v) {
            Swap(numbers, i, gt--);
        } else {
            i++;
        }
    }
    sort(numbers, left, lt - 1);
    sort(numbers, gt + 1, right);
}

private static void Swap(int[] numbers, int i, int j)
{
    int number = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = number;
}

时间与空间复杂度

快速排序的平均时间复杂度为O(NlogN)。在极端糟糕的情况下（每次选基准的时候都选到最大或最小元素），时间复杂度会变成O(N²)。随机选取基准或其他选取基准的方法都致力于是最差情况极度不可能发生。因此在实际应用中，快速排序拥有良好的运算效率。

其它特性

• 快速排序是一种不稳定的排序。
• 如果相同元素会重复出现，使用3-way partitioning可在让每次的分割完成对所有与基准一致的元素的排序，大大提高效率。

相关问题

回到算法页