金狮镖局

Python快速排序算法实例分析
脚本专栏 2024/11/14 佚名
2 0
金狮镖局 Design By www.egabc.com

本文实例讲述了Python快速排序算法。分享给大家供大家参考，具体如下：

快速排序的时间复杂度是O(NlogN)

算法描述：

① 先从序列中取出一个数作为基准数
② 分区过程, 将比这个数大的数全部放到它的右边, 小于或等于它的数全部放到它的左边
③ 再对左右区间重复第二步, 直到各区间只有一个数

假设对 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 进行排序, 首先在这个序列中随便找一个基准数(用来参照), 比如选择 6 为基准数, 接下来把所有比基准数大的数放在6的右边, 比6小的数放在左边

原理分析:

① 选择最左边的数为基准数key
② 设立两个游标 low 和 high , 分别指向数组的最低位和最高位
③ 然后high先动, 如果high位上的数比key大, 则向前走, 如果high-1位上的数比key大, 继续向前走, 直到该位上的数<=key
④ 此时比较low位, 如果<=key, low向后走, 变为low+1, 依次类推, 直到该位上的数比key大
⑤ 交换high和low位上的数
⑥ 重复以上步骤, 直到low=high , 交换 key 和 high 位上的值
⑦ 最后进行递归操作

示例代码：

#!/usr/bin/env python
# coding:utf-8
# 设置最低位和最高位
def quickSort(nums, low, high):
  # 设置一个比较基准key
  key = nums[low]
  while low<high:
    # 如果最高位的数 大于等于 key则向前走
    while low<high and nums[high] >= key:
      high -= 1
    # 如果最低位的数 小于等于 key则向后走
    while low<high and nums[low] <= key:
      low += 1
    # 交换值
    nums[low], nums[high] = nums[high], nums[low]
  #最后low=high, 此时交换key和high位上的值, 使小于key的值在key左边, 大的在key右边
  nums[nums.index(key)], nums[low] = nums[low], nums[nums.index(key)]
  # 返回最低位的位置
  return low
# 进行重复操作
def interval(nums, low, high):
  if low<high:
    # 进行排序并得到最低位位置以循环操作
    key_index = quickSort(nums, low, high)
    interval(nums, low, key_index)
    interval(nums, key_index+1, high)
nums = [64,3,9,2,4,7,0,12,45,]
interval(nums, 0, len(nums)-1)
print "测试结果："
print nums
"""
[0, 2, 3, 4, 7, 9, 12, 45, 64]
"""

运行结果：

Python快速排序算法实例分析

PS：关于排序算法的详细说明还可参考本站在线工具：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具
http://tools.jb51.net/aideddesign/paixu_ys

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

标签：
Python,快速排序,算法
金狮镖局 Design By www.egabc.com
金狮镖局 免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
金狮镖局 Design By www.egabc.com

评论“Python快速排序算法实例分析”

暂无Python快速排序算法实例分析的评论...
www.egabc.com 金狮镖局
139,976影音资源
144,792福利资源
21,817软件资源
631,128技术资源

P70系列延期，华为新旗舰将在下月发布

3月20日消息，近期博主@数码闲聊站 透露，原定三月份发布的华为新旗舰P70系列延期发布，预计4月份上市。

而博主@定焦数码 爆料，华为的P70系列在定位上已经超过了Mate60，成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢？

根据目前爆料的消息来看，华为P70系列将推出三个版本，其中P70和P70 Pro采用了三角形的摄像头模组设计，而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智，但辨识度绝对拉满。

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接
金狮镖局 Design By www.egabc.com