快速排序

快速排序和归并排序看起来有点像，原理却大相径庭。归并排序是将数据一分为二，如此往复直到不能再分为止，然后再用一个merge函数将分出来的数据按个合并，合并的过程中进行比较。快速排序是为自己随机选择一个分区点，将大于和小于该分区点的数放在其两边，如此往复直到不能再分为止，快速排序是一边给自己分区一边进行比较，是由上至下的。

快速排序代码实现

"""
    快速排序
    Author: xingrui
"""


# 快速排序
def quickSort(nums: list, p: int, r: int):
    if p >= r:
        return

    q = partition(nums, p, r)
    quickSort(nums, p, q - 1)
    quickSort(nums, q + 1, r)


def partition(nums: list, p: int, r: int) -> int:
    # 分区点
    pivot = nums[r]
    i, j = p, p

    while j <= r - 1:
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

        j += 1

    nums[i], nums[r] = nums[r], nums[i]
    return i


if __name__ == "__main__":
    nums = [4, 5, 2, 6, 2, 3, 9, 3, 1, 20, 57, 39]
    p, r = 0, len(nums) - 1
    quickSort(nums, p, r)
    print('快速排序，正序排列', nums)

上面的排序方式，选择分区点每次都是选择最后一个元素，这种方法有其弊端，当数据本身是比较有序的情况，可能最后一个元素每次都是最大的，那么就会导致改分区点左右两边的数据数量极其不平衡，这样快速排序的时间复杂度就会退化为。

所以，针对快速排序的优化（让其尽可能分区点选择的合理），我们可以对分区点选择做一些操作，比如三数取中法，随机法。下面一个随机选择分区点的快速排序实现：

"""
    快速排序
    Author: xingrui
"""

import random


# 快速排序
def quickSort(nums: list, p: int, r: int):
    if p >= r:
        return

    q = partition(nums, p, r)
    quickSort(nums, p, q - 1)
    quickSort(nums, q + 1, r)


# 分区-随机选点
def partition(nums: list, p: int, r: int) -> int:
    # 分区点
    randomIndex = random.randint(p, r)
    pivot = nums[randomIndex]

    nums[r], nums[randomIndex] = pivot, nums[r]

    i, j = p, p

    while j <= r - 1:
        if nums[j] <= pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

        j += 1

    nums[i], nums[r] = nums[r], nums[i]

    return i


if __name__ == "__main__":
    nums = [4, 5, 2, 6, 2, 3, 9, 3, 1, 20, 57, 39]
    p, r = 0, len(nums) - 1
    quickSort(nums, p, r)
    print('快速排序，正序排列', nums)

分析

快速排序的平均时间复杂度是，在极端情况下会退化为，而归并排序的时间复杂度可以稳定在，然而实际在日常应用中我们见的更多的是快速排序，这是因为归并排序不是原地排序的算法，如果有1g的数据需要排序，那么可能还需要额外1g的空间来存放临时数据。

快速排序是原地排序，但不是稳定的排序，在排序过程中大小相同的数字排序过后位置关系可能会发生变化。