Python实现的快速排序算法详解

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

快速排序基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

如序列[6，8，1，4，3，9]，选择6作为基准数。从右向左扫描，寻找比基准数小的数字为3，交换6和3的位置，[3，8，1，4，6，9]，接着从左向右扫描，寻找比基准数大的数字为8，交换6和8的位置，[3，6，1，4，8，9]。重复上述过程，直到基准数左边的数字都比其小，右边的数字都比其大。然后分别对基准数左边和右边的序列递归进行上述方法。

实现代码如下：

def parttion(v, left, right):
  key = v[left]
  low = left
  high = right
  while low < high:
    while (low < high) and (v[high] >= key):
      high -= 1
    v[low] = v[high]
    while (low < high) and (v[low] <= key):
      low += 1
    v[high] = v[low]
    v[low] = key
  return low
def quicksort(v, left, right):
  if left < right:
    p = parttion(v, left, right)
    quicksort(v, left, p-1)
    quicksort(v, p+1, right)
  return v
s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
print("before sort:",s)
s1 = quicksort(s, left = 0, right = len(s) - 1)
print("after sort:",s1)

运行结果：

before sort: [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
after sort: [1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 9, 11, 15]

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

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

赞 (0)

相关推荐

  • python实现折半查找和归并排序算法

    python实现折半查找和归并排序算法

    今天依旧是学算法,前几天在搞bbs项目,界面也很丑,评论功能好像也有BUG.现在不搞了,得学下算法和数据结构,笔试过不了,连面试的机会都没有-- 今天学了折半查找算法,折半查找是蛮简单的,但是归并排序我就挺懵比,看教材C语言写的归并排序看不懂,后来参考了别人的博客,终于搞懂了. 折半查找 先看下课本对于 折半查找的讲解.注意了,折半查找是对于有序序列而言的.每次折半,则查找区间大约缩小一半.low,high分别为查找区间的第一个下标与最后一个下标.出现low>high时,说明目标关键字在整个有序

  • 用Python实现随机森林算法的示例

    拥有高方差使得决策树(secision tress)在处理特定训练数据集时其结果显得相对脆弱.bagging(bootstrap aggregating 的缩写)算法从训练数据的样本中建立复合模型,可以有效降低决策树的方差,但树与树之间有高度关联(并不是理想的树的状态). 随机森林算法(Random forest algorithm)是对 bagging 算法的扩展.除了仍然根据从训练数据样本建立复合模型之外,随机森林对用做构建树(tree)的数据特征做了一定限制,使得生成的决策树之间没有关联,

  • python回溯法实现数组全排列输出实例分析

    本文实例讲述了python回溯法实现数组全排列输出的方法.分享给大家供大家参考.具体分析如下: 全排列解释:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. from sys import stdout #code from http://www.jb51.net/ def perm(li, start, end): if(start == end): for elem in li: stdout.wr

  • Python基于回溯法子集树模板实现8皇后问题

    Python基于回溯法子集树模板实现8皇后问题

    本文实例讲述了Python基于回溯法子集树模板实现8皇后问题.分享给大家供大家参考,具体如下: 问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0.1.2.....7列,我们认为每一行的皇后有8种状态.那么,我们只要套用子集树模板,从第0行开始,自上而下,对每一行的皇后,遍历它的8个状态即可. 代码: ''' 8皇后问题 '''

  • Python基于回溯法子集树模板解决0-1背包问题实例

    Python基于回溯法子集树模板解决0-1背包问题实例

    本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题.分享给大家供大家参考,具体如下: 问题 给定N个物品和一个背包.物品i的重量是Wi,其价值位Vi ,背包的容量为C.问应该如何选择装入背包的物品,使得放入背包的物品的总价值为最大? 分析 显然,放入背包的物品,是N个物品的所有子集的其中之一.N个物品中每一个物品,都有选择.不选择两种状态.因此,只需要对每一个物品的这两种状态进行遍历. 解是一个长度固定的N元0,1数组. 套用回溯法子集树模板,做起来不要太爽!!! 代码 '''0-

  • Python使用回溯法子集树模板解决迷宫问题示例

    Python使用回溯法子集树模板解决迷宫问题示例

    本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.

  • Python实现的中国剩余定理算法示例

    本文实例讲述了Python实现的中国剩余定理算法.分享给大家供大家参考,具体如下: 中国剩余定理(Chinese Remainder Theorem-CRT):又称孙子定理,是数论中的一个定理.即如果一个人知道了一个数n被多个整数相除得到的余数,当这些除数两两互质的情况下,这个人就可以唯一的确定被这些个整数乘积除n所得的余数. 维基百科上wiki:The Chinese remainder theorem is a theorem of number theory, which states t

  • Python实现的文本简单可逆加密算法示例

    本文实例讲述了Python实现的文本简单可逆加密算法.分享给大家供大家参考,具体如下: 其实很简单,就是把一段文本每个字符都通过某种方式改变(比如加1) 这样就实现了文本的加密操作,解密就是其逆运算 # -*-coding:utf-8 -*- import sys reload(sys) sys.setdefaultencoding('utf8') #加密 def jiami(): filename=raw_input('please input file:\n') while True: tr

  • Python基于递归算法实现的走迷宫问题

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

  • Python多线程经典问题之乘客做公交车算法实例

    Python多线程经典问题之乘客做公交车算法实例

    本文实例讲述了Python多线程经典问题之乘客做公交车算法.分享给大家供大家参考,具体如下: 问题描述: 乘客乘坐公交车问题,司机,乘客,售票员协同工作,通过多线程模拟三者的工作. 司机:开车,停车 售票员:打开车门,关闭车门 乘客:上车,下车 用Python的Event做线程同步通信,代码如下: # *-* coding:gb2312 *-* import threading import time stationName=("车站0","车站1","车

  • Python常用算法学习基础教程

    Python常用算法学习基础教程

    本节内容 算法定义 时间复杂度 空间复杂度 常用算法实例 1.算法定义 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制.也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出.如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题.不同的算法可能用不同的时间.空间或效率来完成同样的任务.一个算法的优劣可以用空间复杂度与时间复杂度来衡量. 一个算法应该具有以下七个重要的特征: ①有穷性(Fin

  • python算法表示概念扫盲教程

    python算法表示概念扫盲教程

    本文为大家讲解了python算法表示概念,供大家参考,具体内容如下 常数阶O(1) 常数又称定数,是指一个数值不变的常量,与之相反的是变量 为什么下面算法的时间复杂度不是O(3),而是O(1). int sum = 0,n = 100; /*执行一次*/ sum = (1+n)*n/2; /*执行一次*/ printf("%d", sum); /*行次*/ 这个算法的运行次数函数是f(n)=3.根据我们推导大O阶的方法,第一步就是把常数项3改为1.在保留最高阶项时发现,它根本没有最高阶

随机推荐