DDR爱好者之家

Python快速排序算法实例分析
站长资源 2024/11/26 佚名
7 1538
DDR爱好者之家 Design By 杰米

本文实例讲述了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程序设计有所帮助。

DDR爱好者之家 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
DDR爱好者之家 Design By 杰米
ddrfans.com DDR爱好者之家
8,675无损音乐
1,324高清电影
213破解软件
70,141收录资讯

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

昨天有一位朋友在大神群里分享，自己亚服账号被封号之后居然弹出了国服的封号信息对话框。

这里面让他访问的是一个国服的战网网址，com.cn和后面的zh都非常明白地表明这就是国服战网。

而他在复制这个网址并且进行登录之后，确实是网易的网址，也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情，因为以前都没有出现这样的情况，现在突然提示跳转到国服战网的网址，是不是说明了简体中文客户端已经开始进行更新了呢？

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网
DDR爱好者之家 Design By 杰米