快速排序( Quick sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行递归排序，以达到整个序列有序。
1.算法描述：
另一个分而治之
将数组划分为两个部分,然后独立地对部分进行排序：
- 首先选择一个数据透视,并从列表中删除(隐藏在最后)
- 然后这些元素被分成两部分.一个小于枢轴,另一个大于枢轴. 这种分区是通过交换价值来实现的
- 然后在中间恢复枢轴,并且这两个部分递归地快速排序
示例：
Pivot:中间枢纽 ( 5) ， Portitiom:分区 ， Two points:两个指针 ( i:左->右 j:左<-右)
2.算法属性:
- 时间复杂度：O(nlogn)
- 空间复杂度：O(nlogn)
- 稳定性：不稳定
3.代码实现
''' O(nlogn) pivot枢纽，low和high为起点终点 ''' #划分分区（非就地划分） def partition(nums=list): pivot = nums[0] #挑选枢纽 lo = [x for x in nums[1:] if x < pivot] #所有小于pivot的元素 hi = [x for x in nums[1:] if x >= pivot] #所有大于pivot的元素 return lo,pivot,hi #快速排序 def quick_sort(nums=list): #被分解的Nums小于1则解决了 if len(nums) <= 1: return nums #分解 lo,pivot,hi = partition(nums) # 递归（树），分治，合并 return quick_sort(lo) + [pivot] + quick_sort(hi) lis = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2] print(quick_sort(lis)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
''' 两部分，第一部分封装快排函数，第二部分调用快排 取枢纽key为pivot 学习版本 ''' import time def _quick_sort(nums:list): if len(nums) <= 1: return nums pivot = nums[0] #取第一个值为枢纽 #pivot左右边分别调用_quick_sort自身 #找左半边比pivot小的 left_nums = _quick_sort([x for x in nums[1:] if x < pivot]) #找右半边比pivot大的（此处选择x>=pivot意为pivot放在后半边比它大的元素前面） right_nums = _quick_sort([x for x in nums[1:] if x >= pivot]) return left_nums + [pivot] + right_nums def quick_sort(nums:list,reverse=False): start = time.time() nums = _quick_sort(nums) if reverse: nums = nums[::-1] t = time.time() - start return nums,t lis = [1,3,5,7,9,2,5,3,6,8,0] lis = quick_sort(lis,reverse=False) print(lis) #输出结果 ([0, 1, 2, 3, 3, 5, 5, 6, 7, 8, 9], 0.0)
网上最多较多的版本
def quick_sort(array): #封装一层调用 def recursive(begin, end): #fecursive递归 if begin > end: return l, r = begin, end pivot = array[l] while l < r: while l < r and array[r] > pivot: r -= 1 while l < r and array[l] <= pivot: l += 1 array[l], array[r] = array[r], array[l] array[l], array[begin] = pivot, array[l] recursive(begin, l - 1) recursive(r + 1, end) recursive(0, len(array) - 1) return array
第三个版本
''' 使用对象实例化,原理还是一样的 ''' class SQList: def __init__(self, lis=None): self.r = lis def swap(self, i, j): #定义一个交换元素的方法，方便后面调用。 temp = self.r[i] self.r[i] = self.r[j] self.r[j] = temp def quick_sort(self): #调用入口 self.qsort(0, len(self.r)-1) def qsort(self, low, high): #递归调用 if low < high: pivot = self.partition(low, high) self.qsort(low, pivot-1) self.qsort(pivot+1, high) def partition(self, low, high): ''' 快速排序的核心代码。 其实就是将选取的pivot_key不断交换，将比它小的换到左边，将比它大的换到右边。 它自己也在交换中不断变换自己的位置，直到完成所有的交换为止。 但在函数调用的过程中，pivot_key的值始终不变。 :param low:左边界下标 :param high:右边界下标 :return:分完左右区后pivot_key所在位置的下标 ''' lis = self.r pivot_key = lis[low] while low < high: while low < high and lis[high] >= pivot_key: high -= 1 self.swap(low, high) while low < high and lis[low] <= pivot_key: low += 1 self.swap(low, high) return low def __str__(self): ret = "" for i in self.r: ret += " %s" % i return ret if __name__ == '__main__': sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22]) sqlist.quick_sort() print(sqlist)
4.快速排序可优化的地方：（以第三个版本举例）
1)优化选取的Pivot
前面我们每次选取Pivot的都是子序列的第一个元素，也就是lis[low]，这就比较看运气。运气好时，该值处于整个序列的靠近中间值，则构造的树比较平衡，运气比较差，处于最大或最小位置附近则构造的树接近斜树。
为了保证pivot选取的尽可能适中，采取选取序列左中右三个特殊位置的值中，处于中间值的那个数为pivot，通常会比直接用lis[low]要好一点。在代码中，在原来的pivot = lis[low]这一行前面增加下面的代码：
m = low + int((high-low)/2) if lis[low] > lis[high]: self.swap(low, high) if lis[m] > lis[high]: self.swap(high, m) if lis[m] > lis[low]: self.swap(m, low)
如果觉得这样还不够好，还可以将整个序列先划分为3部分，每一部分求出个pivot_key，再对3个pivot_key再做一次上面的比较得出最终的pivot_key。这时的pivot_key应该很大概率是一个比较靠谱的值。
2)减少不必要的交换
原来的代码中pivot_key这个记录总是再不断的交换中，其实这是没必要的，完全可以将它暂存在某个临时变量中，如下所示：
def partition(self, low, high): lis = self.r m = low + int((high-low)/2) if lis[low] > lis[high]: self.swap(low, high) if lis[m] > lis[high]: self.swap(high, m) if lis[m] > lis[low]: self.swap(m, low) pivot_key = lis[low] # temp暂存pivot_key的值 temp = pivot_key while low < high: while low < high and lis[high] >= pivot_key: high -= 1 # 直接替换，而不交换了 lis[low] = lis[high] while low < high and lis[low] <= pivot_key: low += 1 lis[high] = lis[low] lis[low] = temp return low
3)优化小数组时的排序
快速排序算法的递归操作在进行大量数据排序时，其开销能被接受，速度较快。但进行小数组排序时则不如直接插入排序来得快，也就是杀鸡用牛刀，未必就比菜刀来得快。
因此，一种很朴素的做法就是根据数据的多少，做个使用哪种算法的选择而已，如下改写qsort方法：
def qsort(self, low, high): """根据序列长短，选择使用快速排序还是简单插入排序""" # 7是一个经验值，可根据实际情况自行决定该数值。 MAX_LENGTH = 7 if high-low < MAX_LENGTH: if low < high: pivot = self.partition(low, high) self.qsort(low, pivot - 1) self.qsort(pivot + 1, high) else: # insert_sort方法是我们前面写过的简单插入排序算法 self.insert_sort()
4)优化递归操作
可以采用尾递归的方式对整个算法的递归操作进行优化，改写qsort方法如下：
def qsort(self, low, high): """根据序列长短，选择使用快速排序还是简单插入排序""" # 7是一个经验值，可根据实际情况自行决定该数值。 MAX_LENGTH = 7 if high-low < MAX_LENGTH: # 改用while循环 while low < high: pivot = self.partition(low, high) self.qsort(low, pivot - 1) # 采用了尾递归的方式 low = pivot + 1 else: # insert_sort方法是我们前面写过的简单插入排序算法 self.insert_sort()