经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » Python » 查看文章
python如何实现常用的五种排序算法详解
来源：jb51　　时间：2021/8/9 15:17:29　　对本文有异议

一、冒泡排序

原理：

  1. 比较相邻的元素。如果第一个比第二个大就交换他们两个
  2. 每一对相邻元素做同样的工作，直到结尾最后一对
  3. 每个元素都重复以上步骤，除了最后一个

第一步：

将乱序中的最大值找出，逐一移到序列最后的位置

  1. alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]
  2.  
  3.  
  4. def bubble_sort(alist):
  5.     # 找最大值的方式是通过对列表中的元素进行两两比较，值大的元素逐步向后移动
  6.     # 序列中有n个元素，两两比较的话，需要比较n-1次
  7.     for i in range(len(alist) - 1):  # 循环n-1次，控制两两比较的次数
  8.         if alist[i] > alist[i + 1]:
  9.             # 如果前面的元素大于后面的元素，交换两个元素的位置，否则不做任何操作
  10.             alist[i], alist[i + 1] = alist[i + 1], alist[i]
  11.  
  12.     return alist
  13.  
  14.  
  15. print(bubble_sort(alist))
  16.  
  17. # 输出：最大值已经移动到最右边了
  18. [3, 5, 2, 1, 6, 7, 8, 4, 9]
  19.  

当上述代码已经可以将序列中的最大值放置到合适的位置，然后我们就可以将上述操作继续作用到 n-1 和元素对应的新序列，则就可以将 n-1 个元素对应的最大值放置到了 n-1 和元素的最后位置。

结论：发现如果将上述的操作逐步的作用 n-1 此就可以将整个序列变成有序的。

第二步：

将第一步的操作继续作用 n-1 次

  1. alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]
  2.  
  3.  
  4. def bubble_sort(alist):
  5.  
  6.     for j in range(len(alist)-1):   # 外层循环次数递增，内层循环次数递减
  7.         for i in range(len(alist) - 1-j):  # 循环次数需要递减-j，控制两两比较的次数
  8.             if alist[i] > alist[i + 1]:
  9.                 # 如果前面的元素大于后面的元素，交换两个元素的位置，否则不做任何操作
  10.                 alist[i], alist[i + 1] = alist[i + 1], alist[i]
  11.  
  12.     return alist
  13.  
  14.  
  15. print(bubble_sort(alist))
  16.  
  17. # 输出
  18. [1, 2, 3, 4, 5, 6, 7, 8, 9]
  19.  

二、选择排序

思路：

  1. 首先在序列中找到最大（小）元素，存放到序列的最后
  2. 在从剩余的序列元素中继续找最大（小）的元素，放到序列中上一个最大值的前一个位置
  3. 重复第二步，直到所有元素排序完毕

第一步：

将乱序中的元素两两比较，找出最大值，然后直接将最大值放置到序列最后的位置（将最大值直接和最后一个元素交换位置）

  1. def select_sort(alist):
  2.     max_index = 0  # 最大值元素的下标，一开始假设下标为0的元素为最大值
  3.     for i in range(len(alist) - 1):  # 循环控制两两比较的次数
  4.         # 如果在比较的过程中发现，下标为max_index不是最大值，那么就改变max_index
  5.         if alist[max_index] < alist[i + 1]:
  6.             max_index = i + 1
  7.  
  8.     # 循环结束后max_index就一定是最大值的下标，并且把该数和最后一个值做交换
  9.     alist[len(alist) - 1], alist[max_index] = alist[max_index], alist[len(alist) - 1]
  10.     return alist
  11.  
  12.  
  13. alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]
  14. print(select_sort(alist))
  15.  
  16. # 输出
  17. [3, 5, 4, 2, 1, 7, 8, 6, 9]
  18.  

第二步：

将第一步继续作用 n-1 次

  1. def select_sort(alist):
  2.     for j in range(len(alist) - 1):# 外层循环递增n-1次
  3.         max_index = 0  # 最大值元素的下标，一开始假设下标为0的元素为最大值
  4.         for i in range(len(alist) - 1 - j):  # 内层循环递减，循环控制两两比较的次数
  5.             # 如果在比较的过程中发现，下标为max_index不是最大值，那么就改变max_index
  6.             if alist[max_index] < alist[i + 1]:
  7.                 max_index = i + 1
  8.  
  9.         # 循环结束后max_index就一定是最大值的下标，并且把该数和最后一个值做交换
  10.         alist[len(alist) - 1 - j], alist[max_index] = alist[max_index], alist[len(alist) - 1 - j]
  11.     return alist
  12.  
  13.  
  14. alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]
  15. print(select_sort(alist))
  16.  

三、插入排序

思路：

  • 需要将原始序列分为两个部分：有序部分、无序部分。
  • 将无序部分中的元素逐一插入到有序部分中

注意：初始情况下，有序部分为乱序序列中的第一个元素，无序部分为乱序序列的 n-1 个元素

例如：

  1. # 乱序序列：[8,3,5,7,6]
  2. [8,    3,5,7,6] # 8就是初始的有序部分，3、5、7、6就是初始的无序部分
  3. [3,8,    5,7,6]
  4. [3,5,8,    7,6]
  5. [3,5,7,8,    6]
  6. [3,5,7,6,8,   ]

第一步：

定义一个变量 i ，i 表示的是有序部分元素的个数和无序部分第一个元素小标

  1. alist = [8, 3, 1, 6, 7]
  2.  
  3. i = 1  # i 就是有序部分元素的个数和无序部分第一个元素下标
  4. # alist[i-1]：有序部分最后一个元素下标
  5. # alist[i]：无序部分第一个元素下标
  6. if alist[i - 1] > alist[i]:
  7.     alist[i], alist[i - 1] = alist[i - 1], alist[i]
  8.  # [3, 8,    1, 6, 7]
  9.  

第二步：循环作用到每个元素中

  1. alist = [8, 3, 1, 6, 7]
  2.  
  3. i = 2
  4. # alist[i-1]：有序部分最后一个元素下标
  5. # alist[i]：无序部分第一个元素下标
  6. while i > 0:
  7.     if alist[i - 1] > alist[i]:
  8.         # 循环第一次时[3,1,8,   6,7]
  9.         alist[i], alist[i - 1] = alist[i - 1], alist[i]
  10.         i -= 1
  11.         # 循环继续
  12.         # [1,3,8,   6，7]
  13.     else:
  14.         break
  15.  

第三步：

处理变量 i，需要让 i 进行自己递增

  1. for i in range(1, len(alist)): # i = [1,2,3,4]
  2.     # alist[i-1]：有序部分最后一个元素下标
  3.     # alist[i]：无序部分第一个元素下标
  4.     while i > 0:
  5.         if alist[i - 1] > alist[i]:
  6.             alist[i], alist[i - 1] = alist[i - 1], alist[i]
  7.             i -= 1
  8.         else:
  9.             break

完整代码：

  1. def insert_sort(alist):
  2.     for i in range(1, len(alist)):
  3.         while i > 0:
  4.             if alist[i - 1] > alist[i]:
  5.                 alist[i - 1], alist[i] = alist[i], alist[i - 1]
  6.                 i -= 1
  7.             else:
  8.                 break
  9.     return alist

四、希尔排序

关键变量：增量gap

gap：初始值为 len(alist) // 2

  • 表示分组的组数
  • 每一组数据之间的间隔

插入排序就是增量为 1 的希尔排序

第一步：

将插入排序代码写出

  1. def hill_sort(alist):
  2.     for i in range(1, len(alist)):
  3.         while i > 0:
  4.             if alist[i - 1] > alist[i]:
  5.                 alist[i - 1], alist[i] = alist[i], alist[i - 1]
  6.                 i -= 1
  7.             else:
  8.                 break
  9.     return alist

第二步：

在插入排序代码中加入增量的概念

  1. def hill_sort(alist):
  2.     gap = len(alist) // 2  # 初识增量
  3.     
  4.     # 将插入排序中的增量1替换成gap
  5.     # 由增量1变成了增量为gap了
  6.     for i in range(gap, len(alist)):
  7.         while i > 0:
  8.             if alist[i - gap] > alist[i]:
  9.                 alist[i - gap], alist[i] = alist[i], alist[i - gap]
  10.                 i -= gap
  11.             else:
  12.                 break
  13.     return alist

第三步：

在第二步中进行增量的缩减（增量缩减到1结束）完整代码

  1. def hill_sort(alist):
  2.     gap = len(alist) // 2  # 初识增量
  3.  
  4.     while gap >= 1:
  5.         for i in range(gap, len(alist)):
  6.             while i > 0:
  7.                 if alist[i - gap] > alist[i]:
  8.                     alist[i - gap], alist[i] = alist[i], alist[i - gap]
  9.                     i -= gap
  10.                 else:
  11.                     break
  12.         gap //= 2  # 缩减增量
  13.     return alist
  14.  

五、快速排序

思路：

  1. 将列表中第一个元素设定为基准数字，赋值给mid变量，然后将整个列表中比基准小的数值放在基准的左侧，比基准大的数字放在基准右侧，然后将基准数字左右两侧的序列在根据此方法进行排放
  2. 定义两个指针，low 指向最左侧，high 指向最右侧
  3. 然后对最右侧指针进行向左移动，移动法则是，如果指针指向的数值比基准小，则将指针指向的数字移动到基准数字原始位置，否则继续移动指针。
  4. 如果最右侧指针指向的数值移动到基准位置时，开始移动最左侧指针，将其向右移动，如果该指针指向的数值大于基准侧将该数值移动到最右侧指针指向的位置，然后停止移动。
  5. 如果左右侧指针重复则，将基准放入左右指针重复的位置，则基准左侧为比其小的数值，右侧为比其大的数值

第一步：

核心操作，将基数 mid 放置到序列中间，使得基数左侧都是比它小的，右侧是比它大的

  1. def quick_sort(alist):
  2.     low = 0  # 第一个元素下标
  3.     high = len(alist) - 1  # 最后一个元素下标
  4.  
  5.     mid = alist[low]  # 基数：初始值为序列中的第一个数值
  6.     while low != high:
  7.         # 先移动high
  8.         while low < high:
  9.             if mid < alist[high]:  # 下标high对应的值大于mid，high就向右偏移1
  10.                 high = high - 1
  11.             else:
  12.                 # 否则，就把将high指向的数值放置到左侧下标为low对应的空位
  13.                 alist[low] = alist[high]
  14.                 break  # 传递后high下标偏移结束
  15.  
  16.         # 开始移动low
  17.         while low < high:
  18.             if mid > alist[low]:  # 下标low对应的值小于mid，low就向左偏移1
  19.                 low = low + 1
  20.             else:
  21.                 # 否则，就把将low指向的数值放置到左侧下标为high对应的空位
  22.                 alist[high] = alist[low]
  23.                 break  # 并结束
  24.     # 最后当low和high相等的时候，那么就把mid传给下标为low或high的位置
  25.     alist[low] = mid
  26.     return alist
  27.  
  28.  
  29. alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
  30. print(quick_sort(alist))
  31.  
  32. # 输出——>6左边都是比6小的，右边都是比6大的
  33. [5, 1, 2, 4, 3,    6,    9, 7, 10, 8]
  34.  

第二步：

将第一步的核心操作递归作用到基数的左右两侧的子序列中

  1. # 那么如何区分根据基数拆分出的左右子序列呢？可以通过传入指定的left和right来指定不同的子序列
  2. def quick_sort(alist, left, right):
  3.     low = left  # 第一个元素下标
  4.     high = right  # 最后一个元素下标
  5.  
  6.     if low > high:  # 递归结束条件，low是不能大于high的
  7.         return
  8.  
  9.     mid = alist[low]  # 基数：初始值为序列中的第一个数值
  10.     while low != high:
  11.         # 先移动high
  12.         while low < high:
  13.             if mid < alist[high]:  # 下标high对应的值大于mid，high就向右偏移1
  14.                 high -= 1
  15.             else:
  16.                 # 否则，就把将high指向的数值放置到左侧下标为low对应的空位
  17.                 alist[low] = alist[high]
  18.                 break  # 传递后high下标偏移结束
  19.         # 开始移动low
  20.         while low < high:
  21.             if mid >= alist[low]:  # 下标low对应的值小于mid，low就向左偏移1
  22.                 low += 1
  23.             else:
  24.                 # 否则，就把将low指向的数值放置到左侧下标为high对应的空位
  25.                 alist[high] = alist[low]
  26.                 break  # 并结束
  27.  
  28.     # 最后当low和high相等的时候，那么就把mid传给下标为low或high的位置
  29.     if low == high:
  30.         alist[low] = mid
  31.  
  32.     # 上述为核心操作，需要将核心操作递归作用到左右子序列中
  33.     quick_sort(alist, left, low - 1)  # 递归到左侧序列中
  34.     quick_sort(alist, high + 1, right)  # 递归到右侧序列中
  35.  
  36.     return alist
  37.  
  38.  
  39. alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
  40. print(quick_sort(alist, 0, len(alist) - 1))
  41.  
  42. # 输出
  43. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

总结

到此这篇关于python如何实现常用的五种排序算法的文章就介绍到这了,更多相关python实现排序算法内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue！

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

Python热门文章

  • Python | 新冠肺炎疫情数据的爬取与可视化分析
  • Python爬小草1024图片，盖达尔的诱惑（urllib.request）
  • pytorch如何获得模型的计算量和参数量
  • 计算曲线与坐标轴的面积
  • 基于Python实现语音合成小工具
  • PyQt5笔记之弹出窗口大全
  • python反编译学习之字节码详解
  • Python爬虫基础讲解（二十）：多进程——multiprocessing模块的使用
  • python?OpenCV计算图片相似度的5种算法
  • matplotlib 设置图形大小时 figsize 与 dpi 的关系

    • Python推荐文章

  • python 音频处理（2)——提取PPG特征之whisper库的使用（2.1）
  • 《最新出炉》系列初窥篇-Python+Playwright自动化测试-60 - 判断元素是否显示 - 下篇 - 北京-宏哥
  • [python] 启发式算法库scikit-opt使用指北
  • 《最新出炉》系列初窥篇-Python+Playwright自动化测试-59 - 判断元素是否显示 - 上篇 - 北京-宏哥
  • 界面自动化测试录制工具，让python selenium自动化测试脚本开发更加方便
  • 《最新出炉》系列入门篇-Python+Playwright自动化测试-56- 多文件上传 - 下篇 - 北京-宏哥
  • 音频文件降噪及python示例
  • 全网最适合入门的面向对象编程教程：20 类和对象的 Python 实现-组合关系的实现与 CSV 文件保存
  • 张高兴的 MicroPython 入门指南：（一）环境配置、Blink、部署
  • Python——比 Seaborn 更好的相关性热力图：Biokit Corrplot

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号