快速排序
快速排序和归并排序看起来有点像，原理却大相径庭。归并排序是将数据一分为二，如此往复直到不能再分为止，然后再用一个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的空间来存放临时数据。
快速排序是原地排序，但不是稳定的排序，在排序过程中大小相同的数字排序过后位置关系可能会发生变化。
