DSA 快速排序

快速排序

顾名思义，快速排序是最快的排序算法之一。

快速排序算法接受一个值数组，选择其中一个值作为“枢纽”元素，并将其他值移动，以便较低的值位于枢纽元素的左侧，而较高的值位于其右侧。

在本教程中，数组的最后一个元素被选为枢纽元素，但我们也可以选择数组的第一个元素，或者数组中的任何元素。

然后，快速排序算法对枢纽元素左侧和右侧的子数组递归地执行相同的操作。这将一直持续到数组排序完毕。

该算法可以这样描述：

继续阅读以完全理解快速排序算法以及如何自己实现它。

手动运行

在用编程语言实现快速排序算法之前，让我们手动运行一个简短的数组，以了解其原理。

步骤 1： 我们从一个未排序的数组开始。

步骤 2： 我们选择最后一个值 3 作为枢纽元素。

步骤 3： 数组中的其余值都大于 3，并且必须位于 3 的右侧。将 3 与 11 交换。

步骤 4： 值 3 现在处于正确的位置。我们需要对 3 右侧的值进行排序。我们选择最后一个值 11 作为新的枢纽元素。

步骤 5： 值 7 必须位于枢纽值 11 的左侧，而 12 必须位于其右侧。移动 7 和 12。

步骤 6： 将 11 与 12 交换，以便较低的值 9 和 7 位于 11 的左侧，而 12 位于右侧。

步骤 7： 11 和 12 处于正确的位置。我们选择 7 作为 [ 9, 7] 子数组中的枢纽元素，位于 11 的左侧。

步骤 8： 我们必须将 9 与 7 交换。

现在，数组已排序。

运行下面的模拟以查看上述步骤的动画演示。

手动运行：发生了什么？

在用编程语言实现该算法之前，我们需要详细了解上面发生了什么。

我们已经看到，数组的最后一个值被选为枢纽元素，其余的值被排列，以便低于枢纽值的值位于左侧，而高于枢纽值的值位于右侧。

之后，枢纽元素与较高值的第一个值交换。这将原始数组分成两个，枢纽元素位于较低值和较高值之间。

现在，我们需要对旧枢纽元素左侧和右侧的子数组执行与上面相同的操作。如果子数组的长度为 0 或 1，则认为它已完成排序。

总之，快速排序算法使子数组变得越来越短，直到数组排序完毕。

快速排序实现

要编写将数组分割成越来越短的子数组的“quickSort”方法，我们使用递归。这意味着“quickSort”方法必须使用枢纽元素左侧和右侧的新子数组调用自身。阅读有关递归的更多信息 此处。

要在编程语言中实现快速排序算法，我们需要：

1. 一个包含要排序的值的数组。
2. 一个 quickSort 方法，如果子数组的大小大于 1，则调用自身（递归）。
3. 一个 partition 方法，该方法接收一个子数组，移动值，将枢纽元素交换到子数组中并返回子数组中进行下一次分割的索引。

生成的代码如下所示：

def partition(array, low, high):
    pivot = array[high]
    i = low - 1

    for j in range(low, high):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

    array[i+1], array[high] = array[high], array[i+1]
    return i+1

def quicksort(array, low=0, high=None):
    if high is None:
        high = len(array) - 1

    if low < high:
        pivot_index = partition(array, low, high)
        quicksort(array, low, pivot_index-1)
        quicksort(array, pivot_index+1, high)

my_array = [64, 34, 25, 12, 22, 11, 90, 5]
quicksort(my_array)
print("Sorted array:", my_array)

快速排序时间复杂度

有关时间复杂度的总体说明，请访问 此页面。

有关快速排序时间复杂度的更深入和详细的说明，请访问 此页面。

快速排序的最坏情况是 \(O(n^2) \)。当枢纽元素在每个子数组中都是最高值或最低值时，就会发生这种情况，这会导致许多递归调用。在我们上面的实现中，当数组已排序时，就会发生这种情况。

但平均而言，快速排序的时间复杂度实际上仅为 \(O(n \log n) \)，这比我们之前研究过的排序算法要好得多。这就是快速排序如此流行的原因。

在下面，您可以看到快速排序在平均情况下 \(O(n \log n) \) 的时间复杂度的显著改进，与之前的排序算法冒泡排序、选择排序和插入排序相比，它们的时间复杂度为 \(O(n^2) \)

快速排序算法的递归部分实际上是平均排序场景如此快的另一个原因，因为对于枢纽元素的良好选择，每次算法调用自身时，数组都会被大致均匀地分成两半。因此，即使值的数量 \(n \) 翻倍，递归调用的数量也不会翻倍。

在下面的模拟中，在不同类型的数组上运行快速排序，这些数组具有不同数量的值

def partition(array, low, high):
    pivot = array[high]
    i = low - 1

    for j in range(low, high):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

    array[i+1], array[high] = array[high], array[i+1]
    return i+1

def quicksort(array, low=0, high=None):
    if high is None:
        high = len(array) - 1

    if low < high:
        pivot_index = partition(array, low, high)
        (array, low, pivot_index-1)
        (array, pivot_index+1, high)

my_array = [64, 34, 25, 12, 22, 11, 90, 5]
quicksort(my_array)
print("Sorted array:", my_array)