圆月山庄资源网

快速排序的算法思想及Python版快速排序的实现示例
脚本专栏 2024/11/8 佚名
3 2
圆月山庄资源网 Design By www.vgjia.com

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

1.分治法的基本思想

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

2.快速排序的基本思想

设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：

（1）分解：

在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。

注意：

划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：

R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys

其中low≤pivotpos≤high。

（2）求解：

通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

（3）组合：

因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

Python实现

原理: 先用初始数据， 然后对这个数据进行排序使左边的数据小于
该数据，右边的大于该数据，然后用递归的方法对两边的数据进行依次排序。

#!/usr/bin/env python
#_*_coding:utf-8_*_ 

def rand(x):
 import random
 if x < 3:
  x = 5
 if x > 1000:
  print "big data"
  return []
 l = range(1, x)
 li = []
 while l:
  r = random.randint(0, len(l)-1)
  li.append(l.pop(r))
 return li

def quicksort(l, low, hight):
 key = l[low]
 while low < hight:
  while key <= l[hight] and low < hight:
   hight -= 1
  l[low], l[hight] = l[hight], l[low]

  while key >= l[low] and low < hight:
   low += 1
  l[low], l[hight] = l[hight], l[low]

 l[hight] = key
 return hight

def m_sort(l, low, hight):
 if low >= hgiht:
  return 

 index = quicksort(l, low, hight)
 m_sort(l, low, index)
 m_sort(l, index+1, hight)

def main():
 l = rand(1500)
 m_sort(l, 0, len(l)-1)
 print l

if __name__ == '__main__':
 main()

标签：
Python,快速排序
圆月山庄资源网 Design By www.vgjia.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
圆月山庄资源网 Design By www.vgjia.com
www.vgjia.com 圆月山庄资源网
139,976互联网资源
144,792高清电影
21,817无损音乐
631,128技术资源

更新日志

友情链接

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