快速排序（Python实现）

逃离我推掉我的手 2022-03-07 07:38 240阅读 0赞

一、 算法介绍  
快速排序是经常考查到的排序算法，这里对快排算法做一下总结。快速排序是“交换”类的排序，它通过多次划分操作实现排序！以升序为例，其执行流程可以概括为：每一趟排序选择当前所有子序列的一个关键字（通常是第一个）作为**枢轴量**，将子序列中比枢轴量小的移到枢轴前边，比枢轴大的移到枢轴后边，具体过程是一个交替扫描和交换的过程。当本趟所有子序列都被枢轴以上述规则划分完毕后会得到新的**一组**更短的子序列，它们会成为下一趟划分的初始序列集。  
二、演示流程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld21lbW9yeQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld21lbW9yeQ_size_16_color_FFFFFF_t_70 1]  
三、 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(nlog2n)，待排序列越接近无序，本算法效率越高，最坏情况下时间复杂度为O(n2)（序列已经有序的状态），待排序列越接近有序，本算法效率越低，平均时间复杂度为O(nlog2n)。快速排序的排序趟数和初始序列有关！

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld21lbW9yeQ_size_16_color_FFFFFF_t_70]: /images/20220307/44eaa925c07d4e62b136fcbe4dabca47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25ld21lbW9yeQ_size_16_color_FFFFFF_t_70 1]: /images/20220307/e6182fad99ac411180f822ab52b7be16.png