Python进阶系列: 实现各种排序算法

qinggedada 发表于 2020/10/27 10:59:04 2020/10/27
【摘要】 Python 实现各种排序算法冒泡排序(Bubble Sort):选择排序(Selection Sort):插入排序(Insertion Sort):基本思想:将一个记录插入到已经排好序的有序表中,从而得到一个新的,录数增1的有序表。你可以把这种排序想象成整理扑克牌,当你拿到一个新牌要插入已排好序的一把牌中。希尔排序(Shell Sort):基本思想:分组插入排序,即通过将数据分成不同的组,...

Python 实现各种排序算法

图片.png

冒泡排序(Bubble Sort):

Image图片.png

选择排序(Selection Sort):

Image图片.png

插入排序(Insertion Sort):

基本思想:将一个记录插入到已经排好序的有序表中,从而得到一个新的,录数增1的有序表。你可以把这种排序想象成整理扑克牌,当你拿到一个新牌要插入已排好序的一把牌中。

Image图片.png

希尔排序(Shell Sort):

基本思想:分组插入排序,即通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。

Image图片.png

归并排序(Merge Sort):

基本思想:它的中心思想就是先递归分解数组,再合并数组,这是分治法的一个非常典型的应用。先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。分治法是一种算法设计策略。它的思想是将原始问题划分为n个规模较小且与原问题相似的子问题,然后递归的解决子问题,再合并结果,即得到原问题的解。大体上,每一层递归都包含三个步骤:分解,解决,合并。

Image.png

快速排序(Quick Sort):

基本思想:它也是分治法的一个典型应用。

步骤:

从数列中挑出一个元素作为基准数。

分区过程,将比基准数大的放到右边,小于或等于它

一个数。

ImageImage.png

堆排序(Heap Sort):

基本思想:采用堆的数据结构进行排序。在堆排序中,用到的是最大堆,即父节点的数要大于其子节点的数值,每个节点的值至多和其父节点的值一样大,堆中的最大元素存放在根节点中。

下面列出了堆排序中的一些基本过程:

构造最大堆(Build_Max_Heap):若数组下标范围为0~n,考虑到单独一个元素是最大堆,则从下标n/2开始的元素均为最大堆。于是只要从n/2-1开始,向前依次构造最大堆,这样就能保证,构造到某个节点时,它的左右子树都已经是最大堆。

堆排序(HeapSort):得到一个最大堆后,每次从根部移除一个节点,但是剩余的元素仍然要保持最大堆的特性。

最大堆调整(Max_Heapify):该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整,使得子节点永远小于父节点。若某个节点的位置为i,那么它的左节点位置为2i,右节点的位置为2i+1。

Image.png


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。