快速排序

基本概念

快速排序（Quick Sort）基本思想：
采用分治策略，选择一个基准元素，将数组分为两部分：小于基准的元素放在左侧，大于基准的元素放在右侧。然后递归地对左右两部分进行排序，最终得到有序数组。

算法步骤

快速排序的核心是 分区操作，具体步骤如下：

选择基准：从数组中选择一个元素作为基准值（通常选择第一个元素）
分区操作：
- 使用双指针法，左指针从数组开始，右指针从数组末尾
- 右指针向左移动，找到第一个小于基准值的元素
- 左指针向右移动，找到第一个大于基准值的元素
- 交换这两个元素
- 重复上述过程，直到左右指针相遇
- 将基准值放到正确位置（左右指针相遇处）
递归排序：对基准值左右的两个子数组分别进行快速排序

内部实现：

import random
class Solution:
	def randomPartition(self,nums:[int],low:int,high:int)->int:
		i=random.randint(low,high)
		nums[low],nums[i]=nums[i],nums[low]
		return self.partition(nums,low,high)
	def partition(self,nums:[int],low:int,high,int)->int:
		pivot=nums[low]
		i,j=low,high
		while i<j:
			while i<j and nums[j]>=pivot:
				j-=1
			while i<j and nums[i]<=pivot:
				i+=1
			nums[i],nums[j]=nums[j],nums[i]
		nums[i],nums[low]=nums[low],nums[i]
		return i
	def quicksort(self,nums:[int],low:int,high:int)->[int]:
		if low<high:
			pivot_i=self.randomPartition(nums,low,high)
			self.quicksort(nums,low,pivot_i-1)
			self.quicksort(nums,pivot_i+1,high)
		return nums
	def sortArray(self,nums:[int])->[int]:
		return self.quicksort(nums,0,len(nums)-1)

复杂度分析：

指标	复杂度	说明
最佳时间复杂度	$O(nlog⁡n)$	每次都能将数组平均分成两半
最坏时间复杂度	$O(n^2)$	每次选择的基准值都是极值（如已排序数组）
平均时间复杂度	$O(nlog⁡n)$	随机选择基准值时的期望复杂度
空间复杂度	$O(log⁡n)$	递归栈空间，最坏情况下为 $O(n)$
稳定性	不稳定	交换操作可能改变相等元素的相对位置

适用场景：

大规模数据排序（n≥1000）
对平均性能要求高的场景
数据分布相对均匀的情况

优化策略：

随机选择基准值，避免最坏情况
三数取中法选择基准值
小数组使用插入排序
处理重复元素时使用三路快排
快速排序是一种高效的排序算法，采用分治策略，通过分区操作将数组分成两部分，然后递归排序。
优点：
- 平均情况下效率高，时间复杂度为 $O(nlog⁡n)$
- 原地排序，空间复杂度低
- 缓存友好，局部性良好
- 实际应用中常数因子较小
缺点：
- 不稳定排序
- 最坏情况下性能较差，时间复杂度为 $O(n^2)$
- 对于小数组，其他算法可能更快
- 递归调用可能导致栈溢出

快速排序是许多编程语言内置排序函数的实现基础，在实际应用中非常广泛。通过合理的优化策略，可以显著提高其性能和稳定性。

应用场景：

912排序数组
- 问题描述：给你一个整数数组 nums，请你将该数组升序排列。
- 解决方案：快速排序即可
169多数元素
- 问题描述：寻找多数元素
- 解决方案：多数元素总是出现在已排序数组中间