排序算法|室友1把王者的时间写出了快速排序（）算法|排序算法

前言 "欢迎来到王者荣耀，敌军还有5秒钟达到战场！请做好准备！"

文章图片

战争的号角已吹响！
文章图片

文章图片

文章图片

本次我方上场的英雄有：小鲁班，诸葛亮，廉颇，韩信，后羿。

文章图片

文章图片

文章图片

文章图片

文章图片

还没走出泉水，机智的诸葛亮就率先提出作战策略：游戏可以输，姿势一定要帅！看咱现在这站位，高高低低，乘次不齐，一点排面都没有！

文章图片

韩信也马上补充道：“没错！你看这个廉颇，又矮又胖，他还站在C位，你说这像话吗？？？”
（此时，站在一旁的小鲁班悄悄地想旁边挪了一下）
憨厚的廉颇：我我。。。
诸葛亮扶了扶眼镜框马上补充道：在座的各位，有没有觉得自己数学好一点的？
（全场寂静了一分钟。。。）
诸葛亮清了清嗓子，再次扶了扶眼镜框，说道：我也当了几十年的数学老师了，黄金分割率就是我提出来的，要不我提个意见怎么样？
（寂静了片刻。。。）
站在一旁的后羿默默地支了一声：也行吧！其他人也一一应和：可以。。。
于是诸葛亮马上又补充道：以我为基准，比我矮的站在我的左边，比我高的站在我的右边。
话音刚落：廉颇就默默地走到了小鲁班的右边，韩信和后羿依次站在了诸葛亮的右边，诸葛亮站到了C位！
现在的站位如下：

文章图片

文章图片

文章图片

文章图片

文章图片

调皮的小鲁班称赞道：喔！诸葛亮哥哥真厉害，咱们现在不仅是排面杠杆滴！这阵容路线也到位！我和廉颇爷爷个子比较矮，但我的输出高，而廉颇爷爷抗伤能力强，所以我们适合走发育路；而后羿大叔腿子长，输出也还不错，走对抗路也还不错；韩信哥哥更是走位灵活，适合打野发育抓人；诸葛亮哥哥神机妙算，法术高强，走中路再适合不过啦！
韩信也忍不住鼓起了掌声：看你小子个儿不高，脑子还挺灵活的，这波分析杠杆滴！

文章图片

【排序算法|室友1把王者的时间写出了快速排序（）】

言归正传看到诸葛亮的作战策略，不经让我浮想联翩，此情此景似乎在哪里见过？
咦？
这不正是快速排序的核心思想吗？

思路

# 思路每次排序时，取一个参考元素mid_val，将小于mid_val的元素放到它的左边，将大于mid_val的元素放到它的右边
之后，再分别对在mid_val两边的元素分别进行如上操作

结束条件：分组后的元素个数小于等于1

快速排序
如果理解了上面的内容，那么你就已经拿下一血了！！

文章图片

思路简化

def quick_sort(li, left, right): if left < right:# 至少两个元素 mid = partition(li, left, right) #原子操作每次操作后[left,right]区间内的元素，mid左边的都比mid小；mid右边的都比mid大 quick_sort(li, left, mid - 1)# 对mid左边的进行排序 quick_sort(li, mid + 1, right)# 对mid右边的进行排序

将策略分为3步走：

输入区间，得出mid值
操作mid左边的值
操作mid右边的值

这样思路就清晰了很多！double kill！

文章图片

原子操作最后就是解决这个原子操作的问题了！
列出原子操作的核心功能：

输入区间
排序区间
返回mid

所以来实现一下吧！

def partition(li, left, right): mid_val = li[left]while left < right:# 只要左指针不等于右指针循环就没有结束 while left < right and li[right] >= mid_val: right -= 1 li[left] = li[right] while left < right and li[left] <= mid_val: left += 1 li[right] = li[left]li[left] = mid_val return left

Q：外层循环的条件是left A：因为内层的循环，left的一直是不减的，right的值是一直不增的，所以两者可能会相遇！

手动复现一下这个过程！

文章图片

初始列表：[3,1,4,2,5]
经过一轮的原子操作后，得到mid=2，在mid左边的都小于mid，在mid右边的都大于mid！
符合预期结果！triple kill！

文章图片

完整代码

import sys sys.setrecursionlimit(1000000)# 设置递归深度 def partition(li, left, right): mid_val = li[left]while left < right:# 只要左指针不等于右指针循环就没有结束 while left < right and li[right] >= mid_val: right -= 1 li[left] = li[right]while left < right and li[left] <= mid_val: left += 1 li[right] = li[left]li[left] = mid_val return leftdef quick_sort(li, left, right): if left < right:# 至少两个元素 mid = partition(li, left, right) #原子操作每次操作后[left,right]区间内的元素，mid左边的都比mid小；mid右边的都比mid大 quick_sort(li, left, mid - 1)# 对mid左边的进行排序 quick_sort(li, mid + 1, right)# 对mid右边的进行排序

测试
跑了10w条数据，耗时不到1秒，这效率也是杠杆滴！

结束突然寝室里整齐的一声：“victory！”
诸葛亮：咦？游戏结束了吗？我还没杀够呢哈哈哈哈
不过快排到时学废了哈哈哈

同步更新于个人博客系统：室友1把王者的时间写出了快速排序？