目录

前言

系列文章目录

概述

超超python每日算法思维导图

快速排序

什么是快速排序？

代码讲解

快速排序算法的框架

实现快速排序算法代码

快速排序的效率

快速排序函数与冒泡排序的效率比较

快速排序的缺点

十大排序之四大排序总结

---

超超python每日算法思维导图

快速排序

什么是快速排序？

?快速排序（quick sort）使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

①挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）

②分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成

③递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

举例说明快速排序的思路

首先需要取一个元素P(第一个元素)，使元素归位；随后列表被P分成两部分，左边的都比P小，右边的都比P大，随后递归完成排序。

如何选取基准值？

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

代码讲解

快速排序算法的框架

def quick_sort(lst,left,right):? # 需要传入一个列表lst，以及最左边后最后边的位置

?????? if left < right:? # 如果左边小于右边，则说明列表内至少有两个元素

??????????? mid = partition(lst,left,right)?? # 通过partition获得基准值mid

??? quick_sort(lst,left,mid-1)?? # 递归左边的元素

??? quick_sort(lst,mid+1,right)??? # 递归右边的元素

那么快速排序的关键就在于如何设置基准值，即框架内的partition函数？

举例说明：

有如下列表

第一步：我们先存取“5”的位置，此时“5”的位置空出来，随后从左边和右边开始与“5”比较；

第二步：从最右边的位置的元素与“5”比较，如果比“5”大那么不动，发现比“5”小的（“2”）则放到刚刚空出来的“5”的位置；

?第三步：移动了“2”之后原来“2”的位置就空出来，则从当前“2”的位置（左边）开始查找，将比“5”大的数（7）移动到原先“2”的位置；

?第四步：重复第二到三步，直到左右的位置重合，即为“5”最终存放的位置

以上便是partition函数的思路（可能有点难理解）

实现快速排序算法代码

def partition(lst,left,right):? # partition(分割)函数

??? tmp = lst[left]? # 存放基准点，以最左边的值为例

??? while left < right:? # 当左边的位置（下标）小于右边的时候，说明还有至少两个元素，则进行排序

??????? while lst[right] >= tmp and left < right:? # 从右边找比tmp小的元素

??????????? right -= 1? # 比tmp大，则往左移动一位

??????? lst[left] = lst[right]? # 如果出现lst[right] < tmp，则将右边的值lst[right]写到左边的空位lst[left]

??????? # print(f"从右边找比tmp小的数后的列表:{lst}")

??????? while lst[left] <= tmp and left < right:? # 从左边找比tmp大的元素lst[left]，放到右边的空位上lst[right]

??????????? left += 1

??????? lst[right] = lst[left]

??????? # print(f"从左边找比tmp大的数后的列表:{lst}")

??? lst[left] = tmp? # 最后把tmp归位

??? return left? # 返回mid的值

?

# lst1 = [5,7,4,2,6,8,3,1,9]

# print(f"分割前的列表{lst1}")

# partition(lst1,0,len(lst1)-1)

# print(f"最终tmp归为后的列表:{lst1}")

# 输出结果

# 分割前的列表[5, 7, 4, 2, 6, 8, 3, 1, 9]

# 从右边找比tmp小的数后的列表:[1, 7, 4, 2, 6, 8, 3, 1, 9]

# 从左边找比tmp大的数后的列表:[1, 7, 4, 2, 6, 8, 3, 7, 9]

# 从右边找比tmp小的数后的列表:[1, 3, 4, 2, 6, 8, 3, 7, 9]

# 从左边找比tmp大的数后的列表:[1, 3, 4, 2, 6, 8, 6, 7, 9]

# 从右边找比tmp小的数后的列表:[1, 3, 4, 2, 6, 8, 6, 7, 9]

# 从左边找比tmp大的数后的列表:[1, 3, 4, 2, 6, 8, 6, 7, 9]

# 最终tmp归为后的列表:[1, 3, 4, 2, 5, 8, 6, 7, 9]

?

# 随后完成快速排序主体部分的代码

def quick_sort(lst, left, right):? # 需要传入一个列表lst，以及最左边后最后边的位置

??? if left < right:? # 如果左边小于右边，则说明列表内至少有两个元素

??????? mid = partition(lst, left, right)? # 通过partition获得基准值mid

??????? quick_sort(lst, left, mid - 1)? # 递归左边的元素

??????? quick_sort(lst, mid + 1, right)? # 递归右边的元素

?

?

lst2 = [5,7,4,2,6,8,3,1,9]

print(f"初始列表:{lst2}")

quick_sort(lst2,0,len(lst2)-1)

print(f"快速排序后的{lst2}")

# 输出结果

# 初始列表:[5, 7, 4, 2, 6, 8, 3, 1, 9]

# 快速排序后的[1, 2, 3, 4, 5, 6, 7, 8, 9]

快速排序的效率

快速排序的时间复杂度：O(nlogn)? （一层的复杂度是logn，总共n层）

快速排序函数与冒泡排序的效率比较

from runtime import *

import random,copy

?

@runtime

def bubble_sort(lst):

??? for i in range(len(lst) - 1):? # 表示第i趟

??????? exchange = False? # 每一趟做标记

??????? for j in range(len(lst)-i-1):? # 表示箭头

??????????? if lst[j] > lst[j+1]: # 此时是升序排序，>改为<则改为了降序

??????????????? lst[j],lst[j+1] = lst[j+1],lst[j]

??????????????? exchange = True? # 进行了交换，exchange标记为Ture

??????? # print(f"第{i+1}趟后的列表为：{lst}")? # 查看排序过程

??????? if not exchange: # 如果没有进行交换，直接返回，优化的步骤

??????????? return

?

@runtime

def time_quick_sort(lst):

??? quick_sort(lst, 0, len(lst) - 1)

?

lst3 = list(range(10000))

random.shuffle(lst3)

lst_quick = copy.deepcopy(lst3)

lst_bubble = copy.deepcopy(lst3)

time_quick_sort(lst_quick)

bubble_sort(lst_bubble)

# 输出结果

# time_quick_sort执行用时0.0309906005859375s

# bubble_sort执行用时11.869966506958008s

快速排序的缺点

快速排序出现最糟糕情况时，例如列表从的元素是从10000到1，则突破了计算的最大深度，且复杂度达到了O(n2)，空间复杂度也达到了O(n)。

此时可以通过调整运算的最大深度来进行运算（import sys --> sys.setrecursionlimit（100000）），但仍然运算的时间会变长，那么如何修改呢？

此时可以通过修改基准值位置随机取来调整，这样虽然不可以完全避免最坏情况，但是最坏情况的概率会降低。

十大排序之四大排序总结

稳定性说明：

3 2 1 2 4

稳定的排序可以保证左右两边的2的位置不变；

当我们换成字典来看时：

{"name":'a',"age":18}

{"name":'b',"age":19}

{"name":'a',"age":20}

如果按字母排序，稳定的排序，两个‘a’的位置不会改变

总的来说，挨个移动比较的排序算法为稳定的排序。

代码的复杂度：代表代码难不难写，应个人能力和主观感受而定。