快速排序python实现总结
背景：数据结构与算法是IT相关的工程师一直以来的基础考察重点，很多经典书籍都是用c++或者java来实现，出于对python编码效率的喜爱，于是取search了一下python的快排实现，发现大家写的都比较个性，也所以我也总结下自己理解的python快排实现。
注：本随笔注重代码实现，如果是对快速排序无任何接触的还是先看一下相关的书籍
快速排序简介：快速排序是突破O(n^2)时间复杂度上界的排序算法，其平均情况下和最好情况是的时间复杂度都是O(nlogn)，最差情况下的时间复杂度为O(n^2)(最差情况下退化为选择排序)，空间复杂度为O(logn)
核心思想：
核心为 partition() 函数，该函数每调用一次，会产生两个作用：
例子：待排序数组为[3,5,1,8,2,4]，调用一次该函数后数组变为[2,1,3,8,5,4]
直接作用：确定待排序数组上某个位置的值（我们称这个值为枢轴）；在上例中表现为确定了待排序数组中索引为2（第3个元素）的值，元素\'3\'即为枢轴的值
副作用：将待排序数据分为了3个部分，即 [小于等于枢轴的待排序数组]+枢轴+[大于等于枢轴的待排序数组]，副作用的贡献体现在减少了分治的次数
快速排序=对待排序数组采用分治+递归的方法调用partition()函数
partition()函数的时间复杂度为O(n),分治+递归调用的平均时间复杂度为O(logn),所以总体相乘为O(nlogn)
python代码实现
第一种实现，partition借助额外的list，所以partition函数的空间复杂度为O(n),因为涉及分治+递归调用，递归使用的隐含栈需要O(logn)的时间复杂度，所以整体空间复杂度为O(nlogn),借助额外的数据结构一般会起到两个效果：1、降低时间复杂度 或者 2、提高代码可读性（易于理解），这里并没有降低时间复杂度
def quick_sort1(lst): """快速排序""" def partition(lst, left, right): #借助两个临时列表存放小于枢轴的元素和大于枢轴的元素 l_list, r_list = [], [] #选取待排序列表的最左元素作为枢轴 pivot_value = lst[left] for i in lst[left+1:right+1]: if i<=pivot_value: l_list.append(i) else: r_list.append(i) #因为是原地排序，所以对原待排序数组的相应元素进行替换 lst[left:right+1] = l_list+[pivot_value]+r_list return left+len(l_list) def q_sort(lst, left, right): """辅助函数，便于递归调用""" if left>=right: return pivot_key = partition(lst, left, right) q_sort(lst, left, pivot_key-1) q_sort(lst, pivot_key+1, right) if not lst or len(lst)==0: return lst q_sort(lst, 0, len(lst)-1) return lst
上述实现采用了额外的list，虽然增加了可读性，但是提高了空间复杂度，所以，可以对其优化，将partition函数的空间复杂度降为O(1)
第二种实现，不借助额外列表
def quick_sort2(lst): """快速排序""" def partition(lst, left, right): #默认选择列表最左元素作为枢轴 pivot_value = lst[left] while left<right: while left<right and lst[right]>=pivot_value: right-=1 #当右指针对应元素小于枢轴的值，将左右指针对应元素交换，使小于枢轴的值位于枢轴的左侧 lst[left], lst[right] = lst[right], lst[left] while left<right and lst[left]<=pivot_value: left+=1 #当左指针对应元素大于枢轴的值，将左右指针对应元素交换，使大于枢轴的值位于枢轴的右侧 lst[left], lst[right] = lst[right], lst[left] return left def q_sort(lst, left, right): if left>=right: return pivot_key = partition(lst, left, right) q_sort(lst, left, pivot_key-1) q_sort(lst, pivot_key+1, right) if not lst or len(lst)==0: return lst q_sort(lst, 0, len(lst)-1) return lst
这里通过元素交换的方式达到了与方法1同样的效果，所以在很多资料上，快速排序和冒泡排序都被分类为\'交换排序\'，但有一点要注意，快速排序最差的情况下，会退化为选择排序而非冒泡排序
针对第二种情况，我们还可以继续优化，省去不必要的交换，将"交换"优化为“替换”
第三种实现
def quick_sort3(lst): """快速排序""" def partition(lst, left, right): #默认选择列表最左元素作为枢轴，同时也记录了left最初对应的元素值 pivot_value = lst[left] while left<right: while left<right and lst[right]>=pivot_value: right-=1 #将left对应的元素替换为right（小于枢轴）对应的元素 lst[left] = lst[right] while left<right and lst[left]<=pivot_value: left+=1 #将right对应的元素替换为left（大于枢轴）对应的元素 lst[right] = lst[left] #当left和right相等时，使用最初记录的left对应的元素值替换当前指针的元素 lst[left] = pivot_value #返回枢轴对应的索引 return left def q_sort(lst, left, right): if left>=right: return pivot_key = partition(lst, left, right) q_sort(lst, left, pivot_key-1) q_sort(lst, pivot_key+1, right) if not lst or len(lst)==0: return lst q_sort(lst, 0, len(lst)-1) return lst
第三种方案和前两种一样，都是将列表的最左元素作为枢轴，这也是导致快速排序最差情况时间复杂度为O(n^2)的原因，比如每次列表的最左元素都为最大值或者最小值，那每次对partition函数的调用只起到了直接作用（确定了列表的最左端的最小值或者最右端的最大值），而没有起到副作用（副作用的目的是减小分治次数）
所以我们可以对枢轴的选取进行优化，优化的目的是使枢轴的选取避开最大值或最小值，尽量靠近中位数，优化的思路有两种
1、随机选取
2、选取列表中left, right, (left+right)//2，三个索引位置对应元素居中的元素
由于随机数的生成在编程语言API中的实现也要耗费一定的时间复杂度，所以我们选择2
第四种实现如下
def quick_sort4(lst): """快速排序""" def partition(lst, left, right): #计算中间索引 mid = (left+right)//2 #将三个元素中大小居中的元素交换至列表的最左侧 if lst[left]>lst[mid]: lst[left], lst[mid] = lst[mid], lst[left] if lst[mid]>lst[right]: lst[mid], lst[right] = lst[right], lst[mid] if lst[left]<lst[mid]: lst[left], lst[mid] = lst[mid],lst[left] pivot_value = lst[left] while left<right: while left<right and lst[right]>=pivot_value: right-=1 lst[left] = lst[right] while left<right and lst[left]<=pivot_value: left+=1 lst[right] = lst[left] lst[left] = pivot_value return left def q_sort(lst, left, right): if left>=right: return pivot_key = partition(lst, left, right) q_sort(lst, left, pivot_key-1) q_sort(lst, pivot_key+1, right) if not lst or len(lst)==0: return lst q_sort(lst, 0, len(lst)-1) return lst
经过2~4的优化，我们已经
1）把空间复杂度由O(nlogn)降至O(n),yi
2）并尽量优化了最差情况下的时间复杂度，使其比O(n^2)要好一些
但需要提醒一下，其最佳情况下的时间复杂度依旧使O(nlogn)，而一些简单排序算法，如插入排序和优化后的冒泡排序的最优时间复杂度都可以达到O(n)
快排在面对大量数据排序时表现良好，
所以可以进行优化，当待排序数据的元素数量小于某个常数值时采用插入排序，否则使用快速排序
第五种实现
def quick_sort5(lst): """快速排序""" def partition(lst, left, right): #计算中间索引 mid = (left+right)//2 #将三个元素中大小居中的元素交换至列表的最左侧 if lst[left]>lst[mid]: lst[left], lst[mid] = lst[mid], lst[left] if lst[mid]>lst[right]: lst[mid], lst[right] = lst[right], lst[mid] if lst[left]<lst[mid]: lst[left], lst[mid] = lst[mid],lst[left] pivot_value = lst[left] while left<right: while left<right and lst[right]>=pivot_value: right-=1 lst[left] = lst[right] while left<right and lst[left]<=pivot_value: left+=1 lst[right] = lst[left] lst[left] = pivot_value return left def q_sort(lst, left, right): if left>=right: return pivot_key = partition(lst, left, right) q_sort(lst, left, pivot_key-1) q_sort(lst, pivot_key+1, right) if not lst or len(lst)==0: return lst #取某个常数，待排序元素数量大于该常数时使用快排，否则使用插入排序 if len(lst)>50: q_sort(lst, 0, len(lst)-1) else: #插入排序在此不实现了，大家自行解决 insert_sort(lst) return lst
经过上述优化，我们做到了
1）空间复杂度由O(nlogn)优化至O(logn)
2) 将最差情况下的时间复杂度O(n^2)尽可能提升
3）将时间复杂度的下界提升至O(n)，当然，这已经不是单纯的快排了- -！
刚开始写博客，有不对的地方还望指教~~~