Python之快速排序

r囧r小猫 2022-02-20 08:53 112阅读 0赞

**快速排序：**  
通过基准值将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准值要小，另外一部分的所有数据都比基准值要大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此类推，使整个数据变成有序序列。

快速排序的速度取决于选择的基准值，有序序列中选择第一个值作为基准值是最糟情况O(n)，基准值选取优先级：三数取中 > 随机基准 > 固定基准。

使用分而治之divide and conquer(D&C)策略，必须有基准值。

**示例：三数取中，取中间数为基准值**

from random import choice
    
    def quickSort(arr):
    	length = len(arr)
    	if length < 2: 												#基线条件，空列表或1个值的列表
    		return arr
    	else: 														#递归条件（归纳条件，归纳证明）
    		index = length//2 										#中间数索引
    		start = arr[0] 											#第一个元素
    		mid = arr[index]										#最中间一个元素
    		end = arr[length-1]										#最后一个元素
    		#判断三数的中值，作为基准值
    		if end <= start and end <= mid: 						#如果最后一个元素最小
    			pivot = min(start, mid) 							#获取前两个元素中小的那个
    		else:													#如果最后一个元素不是最小
    			pivot = min(max(start, mid), end) 					#获取前两个元素中大的那个，再与最后一个元素对比，获取小的那个元素
    		arr.remove(pivot) 										#去除基准值，下面再排序
    		less = [i for i in arr if i < pivot] 					#小于基准值的子列表
    		greater = [i for i in arr if i >= pivot] 				#大于等于基准值的子列表
    		return quickSort(less) + [pivot] + quickSort(greater)	#合并列表
    
    arr = [5, 2, 10, 4, 3, 7, 1]
    print(quickSort(arr))

**结果为：**

[1, 2, 3, 4, 5, 7, 10]

**示例：随机基准**

def quickSort2(arr):
    	if len(arr) < 2: 											#基线条件，空列表或1个值的列表
    		return arr
    	else: 														#递归条件（归纳条件，归纳证明）	
    		pivot = choice(arr) 									#随机选取一个基准值
    		arr.remove(pivot) 										#去除基准值，下面再排序
    		less = [i for i in arr if i < pivot] 					#小于基准值的子列表
    		greater = [i for i in arr if i >= pivot] 				#大于等于基准值的子列表
    		return quickSort2(less) + [pivot] + quickSort2(greater)	#合并列表
    
    arr2 = [5, 2, 10, 4, 3, 7, 1]
    print(quickSort2(arr2))

**结果为：**

[1, 2, 3, 4, 5, 7, 10]

**示例：固定基准，一般固定为第一个或最后一个元素**

def quickSort3(arr):
    	if len(arr) < 2: 											#基线条件，空列表或1个值的列表
    		return arr
    	else: 														#递归条件（归纳条件，归纳证明）
    		pivot = arr[0]											#基准值，固定为第一个元素
    		less = [i for i in arr[1:] if i < pivot] 				#小于基准值的子列表
    		greater = [i for i in arr[1:] if i >= pivot] 			#大于等于基准值的子列表
    		return quickSort3(less) + [pivot] + quickSort3(greater)	#合并列表
    
    arr3 = [5, 2, 10, 4, 3, 7, 1]
    print(quickSort3(arr3))

**结果为：**

[1, 2, 3, 4, 5, 7, 10]