酷站(www.ku0.com)-致力于为互联网从业者提供动力!

热门关键词:  企业  as  baidu  c4rp3nt3r  美女
【阿里云】采购季上云仅¥223/3年

Python实现快速排序的方法

来源:互联网搜集 作者:秩名 人气: 发布时间:2019-10-25
本篇文章主要介绍了Python实现快速排序的方法,对大家的学习或者工作具有一定的参考学习价值,感兴趣的小伙伴们可以参考一下,也感谢大家对酷站(ku0.com)的支持。

说起快排的Python实现,首先谈一下,快速排序的思路:

1、取一个参考值放到列表中间,初次排序后,让左侧的值都比他小,右侧的值,都比他大。

2、分别对左侧和右侧的部分递归第1步的操作

实现思路:
 

  • 两个指针left,right分别指向列表的第一个元素和最后一个元素,然后取一个参考值,默认为第一个列表的第一个元素list[0],称为K
  • 然后left指向的值先和参考值K进行比较,若list[left]小于或等于K值,left就一直向右移动,left+1,直到移动到大于K值的地方,停住
  • right指向的值和参考值K进行比较,若list[right]大于K值,right就一直向左移动,right-1,直到移动到小于K值的地方,停住
  • 此时,left和right若还没有相遇,即left还小于right,则二者指向的值互换
  • 若已经相遇则说明,第一次排序已经完成,将list[right]与list[0]的值进行互换,进行之后的递归


编程实现:
 

#快排的主函数,传入参数为一个列表,左右两端的下标
def QuickSort(list,low,high):
  if high > low:
    #传入参数,通过Partitions函数,获取k下标值
    k = Partitions(list,low,high)
    #递归排序列表k下标左侧的列表
    QuickSort(list,low,k-1)
    # 递归排序列表k下标右侧的列表
    QuickSort(list,k+1,high)
def Partitions(list,low,high):
  left = low
  right = high
  #将最左侧的值赋值给参考值k
  k = list[low]
  #当left下标,小于right下标的情况下,此时判断二者移动是否相交,若未相交,则一直循环
  while left < right :
    #当left对应的值小于k参考值,就一直向右移动
    while list[left] <= k:
      left += 1
    # 当right对应的值大于k参考值,就一直向左移动
    while list[right] > k:
      right = right - 1
    #若移动完,二者仍未相遇则交换下标对应的值
    if left < right:
      list[left],list[right] = list[right],list[left]
  #若移动完,已经相遇,则交换right对应的值和参考值
  list[low] = list[right]
  list[right] = k
  #返回k值
  return right
list_demo = [6,1,2,7,9,3,4,5,10,8]
print(list_demo)
QuickSort(list_demo,0,9)
print(list_demo)

运行结果:
 

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

版权声明:本文内容来源于互联网或用户自行发布贡献,该文观点仅代表原作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 959677720#qq.cn(#换@) 举报,一经查实,本站将立刻删除。
原文链接:https://www.cnblogs.com/kunpengv5/p/7833361.html

相关文章

  • django连接数据库出现1045错误的解决方法

    django连接数据库出现1045错误的解决方法

    根据菜鸟教程Django教程学习,运行python manage.py migrate 报错,出现 django.db.utils.OperationalError: (1045, Access denied for user 账号@localhost (using password: YES)) 错误。 这种错误指的是连接数据库时账号密码错误。 1.......
    05-15
  • Django在Model保存前记录日志

    Django在Model保存前记录日志

    Django中如何在Model保存前做一定的固定操作,比如写一句日志? 关键词: 信号 利用Django的Model的Signal Dispatcher, 通过django.db.models.signals.pre_save() 方法,在事件发生前, 发射 触发信号,这一切都被调度中的receiver方法深......
    05-15
  • 解决python动态库m.so.1.0错误问题

    解决python动态库m.so.1.0错误问题

    $ python -V python: error while loading shared libraries: libpython3.6m.so.1.0: cannot open shared object file: No such file or directory ldd是列出动态库依赖关系: $ ldd /usr/local/bin/python3.6linux-vdso.so.1 = (0x00007......
    05-09
  • 基于windows实现python定时爬虫

    基于windows实现python定时爬虫

    Windows系统下使用任务计划程序,Linux下可以使用crontab命令添加自启动计划。 这里写Windows 10 / windows Server 2016系统的设置方法。 首先编写一个.bat脚本。新建一个txt,将下面三行代码复制进去,main.py改成自己程序名字。保存为.......
    05-01
  • 全网首秀之Pycharm十大实用技巧介绍!

    全网首秀之Pycharm十大实用技巧介绍!

    PyCharm 应该是大多数 python 开发者的首选 IDE,每天我们都在上面敲着熟悉的代码,写出一个又一个奇妙的功能。它是帮助用户在使用 Python 语言开发时提高其效率的工具,但是好多人只是把它当做一个文本编辑器使用,并没有发挥出它的优势......
    04-27
  • python追踪except信息方式的介绍

    python追踪except信息方式的介绍

    看下面这个函数 def test(): sum = 3/0 if __name__ == __main__: test() 除0肯定是不对的,会引发一个except,内容如下: File E:\Src\dongsheng\TestPython\testtrace_back.py, line 23, in module test() File E:\Src\dongsheng\TestP......
    04-25
  • Python实现仿射密码的代码

    Python实现仿射密码的代码

    仿射密码思路: 1、加解密公式: 2、构造对应字典: 3、代码实现 构造字典,建立映射关系: ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 # 构造字典,A -- 0 ... def char_2_num(x): list_s = [] list_num = [] for i i......
    04-23
  • 利用matplotlib为图片上添加触发事件进行交互的介绍

    利用matplotlib为图片上添加触发事件进行交互的介绍

    解决方案网上有很多,尝试以后依然bug,这里先做一个记录,有时间再来处理。 错误报告如下: OpenCV Error: Unspecified error (The function is not implemented. Rebuild the library with Windows, GTK+ 2.x or Carbon support. If you ......
    04-23
  • jupyter notebook 实现matplotlib图动态刷新的介绍

    jupyter notebook 实现matplotlib图动态刷新的介绍

    我就废话不多说了,大家还是直接看代码吧! import matplotlib%matplotlib inlinefrom IPython import display 需要刷新的地方,画完图之后添加 display.clear_output(wait=True) 补充知识:jupyter notebook matplotlib绘制动态图并显示......
    04-22
  • Django框架配置mysql数据库实现过程详细介绍

    Django框架配置mysql数据库实现过程详细介绍

    django配置mysql数据库: 1.首先更改django项目文件中的settings.py的数据库配置 ? 1 2 3 4 5 6 7 8 9 10 DATABASES = { default : { ENGINE : django.db.backends.mysql , NAME : django_test , # 使用的数据库名, USER : root , # 用户......
    04-22

最新更新