没有合适的资源?快使用搜索试试~ 我知道了~
确定性快速排序与随机化快速排序的比较
需积分: 28 12 下载量 187 浏览量
2017-11-12
09:29:27
上传
评论
收藏 491KB PDF 举报
温馨提示
试读
15页
在输入序列个数、排序情况不同的情况下对确定性快速排序与随机化快速排序的比较。比较他们的运行时间,验证是否与理论相符。
资源推荐
资源详情
资源评论
快速排序与随机化快排运速度实验较
⼀. 前⾔
在计算机科学与数学中,⼀个排序算法是⼀种能将⼀串数据依照特定排序⽅式进⾏排列
的⼀种算法。最常⽤到的排序⽅式是数值顺序以及字典顺序。有效的排序算法在⼀些算法(例
如搜索算法与合并算法)中是重要的,如此这些算法才能得到正确解答。排序算法也⽤在处
理⽂字数据以及产⽣⼈类可读的输出结果。基本上,排序算法的输出必须遵守下列两个原则:
1、输出结果为递增序列(递增是针对所需的排序顺序⽽⾔)
2、输出结果是原输⼊的⼀种排列、或是重组。虽然排序算法是⼀个简单的问题,但是在计
算机数据处理上发挥了很⼤的作⽤,从计算机科学发展以来,在此问题上也已经有⼤量的研
究。
⼆. 快速排序
快速排序⽤到了分治思想,同样的还有归并排序。乍看起来快速排序和归并排序⾮常相
似,都是将问题变⼩,先排序⼦串,最后合并。不同的是快速排序在划分⼦问题的时候经过
多⼀步处理,将划分的两组数据划分为⼀⼤⼀⼩,这样在最后合并的时候就不必像归并排序
那样再进⾏⽐较。但也正因为如此,划分的不定性使得快速排序的时间复杂度并不稳。
快速排序的期望复杂度是 O(nlogn),但最坏情况下可能就会变成 O(n^2),最坏情况就是每次
将⼀组数据划分为两组的时候,分界线都选在了边界上,使得划分了和没划分⼀样,最后就
变成了普通的选择排序了。
快速排序使⽤分治法策略来把⼀个序列分为两个⼦序列。
步骤为:
1、从数列中挑出⼀个元素,称为"基准",
2、重新排序数列,所有元素⽐基准值⼩的摆放在基准前⾯,所有元素⽐基准值⼤的摆在基
准的后⾯(相同的数可以到任⼀边)。在这个分区结束之后,该基准就处于数列的中间位置。
这个称为分区操作。
3、递归地把⼩于基准值元素的⼦数列和⼤于基准值元素的⼦数列排序。
递归的最底部情形,是数列的⼤⼩是零或⼀,也就是永远都已经被排序好了。虽然⼀直递归
下去,但是这个算法总会结束,因为在每次的迭代中,它⾄少会把⼀个元素摆到它最后的位
置去。
def quick_sort(array,low,high):
''' realize from book "data struct" of author 严蔚敏
'''
if low < high:
key_index = partion(array,low,high)
quick_sort(array,low,key_index)
quick_sort(array,key_index+1,high)
def partion(array,low,high):
key = array[low]
while low < high:
while low < high and array[high] >= key:
high -= 1
if low < high:
array[low] = array[high]
while low < high and array[low] < key:
low += 1
if low < high:
array[high] = array[low]
array[low] = key
return low
def calculate(data):
time1 = time.time()
quick_sort(data, 0, len(data) - 1)
time2 = time.time()
spend_time = time2 - time1
print(spend_time)
return spend_time
三. 随机化快速排序
当输⼊序列为有序时,快排的时间复杂度最⼤,效率最低,为了使快排在任何序列中,
效率始终处于最优,引⼊随机化的思想。随机化即是随机地选择主元,使其运⾏时间不依赖
于输⼊序列的顺序。
经分析,!随机化快排的算法效率是Θ(nlgn)。
实现:我们只需在选取主元时加⼊随机因素即可。其他与快排⼀样。
def randomize_quick_sort(array, left, right):
if left < right:
i = random.randint(left, right)
temp = array[i]
array[i] = array[left]
array[left] = temp
key_index = partion(array,left,right)
randomize_quick_sort(array,left,key_index-1)
randomize_quick_sort(array,key_index+1,right)
def randomize_calculate(data):
time1 = time.time()
randomize_quick_sort(data, left = 0, right = len(data) - 1)
time2 = time.time()
spend_time = time2 - time1
print(spend_time)
return spend_time
四. 普通快排与随机化快排性能分析
4.1 程序运环境
计算机配置:
硬件:
CPU :2.2 GHz Intel Core i7 内存:16GB
软件:
系统:macOS Sierra 64 位操作系统 编译器:Spyder
4.2 普通快排与随机化快排在随机数据下的较
表4.1 普通快排与随机化快排在随机数据下的较
图4.1 普通快排与随机化快排在随机数据输下的运时间较
从数据与图可以看出,在计算速度上,同⼀数据量的快速排序中,确定性算法要⽐随
机化算法迅速,⽽且随着数据量的增⼤,差距越来越明显。
4.3 普通快排与随机化快排在10w、1000w数据下的波动情况
1w
10w
100w
1000w
10000w
普通快排(s)
0.03504
0.43939
5.69872
67.88774
838.85121
随机化快排(s)
0.04512
0.54306
6.36516
78.69839
964.07663
剩余14页未读,继续阅读
资源评论
dsjdjsa
- 粉丝: 154
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功