本文实例讲述了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 位上的值
⑦ 最后进行递归操作
示例代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#!/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程序设计有所帮助。
原文链接：http://www.cnblogs.com/qlshine/p/6032111.html
