确定性快速排序与随机化快速排序的比较

快速排序

需积分: 28 93 浏览量更新于2023-03-16 收藏 491KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

快速排序与随机化快排运󰢩速度实验较 
⼀. 前⾔
 在计算机科学与数学中，⼀个排序算法是⼀种能将⼀串数据依照特定排序⽅式进⾏排列
的⼀种算法。最常⽤到的排序⽅式是数值顺序以及字典顺序。有效的排序算法在⼀些算法（例
如搜索算法与合并算法）中是重要的，如此这些算法才能得到正确解答。排序算法也⽤在处
理⽂字数据以及产⽣⼈类可读的输出结果。基本上，排序算法的输出必须遵守下列两个原则：
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: