快速排序（Python实现）

大家好，又见面了，我是你们的朋友全栈君。

一、 算法介绍
快速排序是经常考查到的排序算法，这里对快排算法做一下总结。快速排序是“交换”类的排序，它通过多次划分操作实现排序！以升序为例，其执行流程可以概括为：每一趟排序选择当前所有子序列的一个关键字（通常是第一个）作为枢轴量，将子序列中比枢轴量小的移到枢轴前边，比枢轴大的移到枢轴后边，具体过程是一个交替扫描和交换的过程。当本趟所有子序列都被枢轴以上述规则划分完毕后会得到新的一组更短的子序列，它们会成为下一趟划分的初始序列集。
二、演示流程


三、 Python代码实现

def quick_sort(nums: list, left: int, right: int) -> None:
	if left < right:
		i = left
		j = right
		# 取第一个元素为枢轴量
		pivot = nums[left]
		while i != j:
			# 交替扫描和交换
			# 从右往左找到第一个比枢轴量小的元素，交换位置
			while j > i and nums[j] > pivot:
				j -= 1
			if j > i:
				# 如果找到了，进行元素交换
				nums[i] = nums[j]
				i += 1
			# 从左往右找到第一个比枢轴量大的元素，交换位置
			while i < j and nums[i] < pivot:
				i += 1
			if i < j:
				nums[j] = nums[i]
				j -= 1
		# 至此完成一趟快速排序，枢轴量的位置已经确定好了，就在i位置上（i和j)值相等
		nums[i] = pivot
		# 以i为枢轴进行子序列元素交换
		quick_sort(nums, left, i-1)
		quick_sort(nums, i+1, right)		


# 测试代码
import random

data = [random.randint(-100, 100) for _ in range(10)]
quick_sort(data, 0, len(data) - 1)
print(data)

四、性能分析

1. 时间复杂度分析
   快速排序最好情况下的时间复杂度为O(nlog₂n)，待排序列越接近无序，本算法效率越高，最坏情况下时间复杂度为O(n²)（序列已经有序的状态），待排序列越接近有序，本算法效率越低，平均时间复杂度为O(nlog₂n)。快速排序的排序趟数和初始序列有关！

有多个时间复杂度为O(nlog₂n)的排序算法，但这里称之为快速排序算法而不是其他排序，是因为其他排序算法的基本操作执行次数的多项式最高项为X*nlog₂，X为系数，快速排序的X最小，可见它在最高级别的算法中是最好的，故叫快速排序。

2. 空间复杂度分析
   空间复杂度为O(log₂n)，快速排序是递归进行的，需要栈的辅助！