专栏首页python3python排序算法(三)

python排序算法(三)

   OK,又到了苦逼的周一了

。快排比较复杂,花了快两天琐碎时间琢磨了感觉还不是很好,据我们老师说当年提出快排的人是在上课突然想起来的,我等只能深深膜拜了

   快速排序是一种具有良好平均性能的排序方法,插入排序将控制当前插入的基准记录插入相对于已经排好序的子表的正确位置,与此不同的是,快速排序将基准记录放在相对于整个列表的正确位置。这个听上去有点闹人,具体的解释我就不巴拉了,可以上网百度。

   以前写快排只实现最基本的功能,完全没考虑到一些边界问题,这些问题当我用python这门语言,当我想用随机数的列表来检验时,一下子暴露了,不过修补程序也是件很快乐的事啊!

   下面是修改后健壮性比较好的代码,基本不会报错或者陷入死循环:

,,

import random
def QuickSort(x,left,right):
    counter=0
    if(left<right):
        j=right
        pivot=x[left]
        i=left+1
        while(i<=j):
            while(x[i]<=pivot and i<right):
                i+=1
                counter+=1
            while(x[j]>pivot and j>left):
                j-=1
                counter+=1
            if(i<j):
                InterChange(x,i,j)
                counter+=1
            if(i==j):
                break
        InterChange(x,left,j)
        counter+=1
        if(j-left>1):
            counter+=QuickSort(x,left,j-1)
        if(right-j>1):
            counter+=QuickSort(x,j+1,right)
    return counter
def InterChange(x,i,j):
    temp=x[i]
    x[i]=x[j]
    x[j]=temp
x=[]
for a in range(1000):
    x.append(random.randint(1,1000))
#x=[27,85,69,99,97,49,22,64,7,24,10,13,73,99,95,12,89,83,54]
#for a in x:
    #print(a)
print('*********')
for a in x:
    if(a>x[len(x)-1]):
        InterChange(x,x.index(a),len(x)-1)
counter=QuickSort(x,0,len(x)-1)
for a in x:
    print(a)
print(counter)

   这个程序中我counter计算应该不是很准确,主要精力不是放在上面了。整个过程可以用修好一个bug冒出一个bug来形容。其实主要的问题还是由于大量随机数会产生相同的数导致的……

   34、35行我注释掉了,当时其实程序大部分时候已经能跑成功了,当排序的数的单位设置为百时,但是运行十次会出一次错。为了调这个bug,我只好把排序的数设置为20,然后运行了几十遍之后终于得到这行宝贵的数据,对于这个bug,读者可以把第9行和第12行and后面的判断去掉体会一下。

   第9行和第12行本应该对称,但是9行多了个=号是因为有个潜在的死循环问题,主要是由相同的数引起的,比如这样的排列10,10,10,其中left指向第一个10,i指向第二个,j指向第3个,这样会陷入死循环出不去。但加了=号也导致了下面的问题。

   第8行一开始是没有=号的,但是这个会导致一个排序不彻底的bug,这个的话可以以x=[1,3,9,7,12,23,4,16,20],也就是我之前一直用的例子体会下。至于第18行和第19行又额外加了个i==j的判断是防止它若x[i]=x[j]=x[right],x[i+1]会越界的错这个问题也是用大规模随机数找到的。

   至于38—40行在开始把列表中最大数放到末尾,也是出于避免一些边界问题的考虑。

   现在的程序已经很稳定了,可以经得住随机数的考验,运行下来counter分布在10000—15000之间,但是偶尔(几十次会有一次)也会很高,达到100000的水平,这是因为快排的最坏复杂度是o(n*n)的原因。明天可能还要研究研究快排优化的问题,下面把这个程序最基本的部分给出来方便读者自己修改,基本程序本身是有bug的,读者可以根据需要自行调整下:

def QuickSort(x,left,right):
    counter=0
    if(left<right):
        j=right
        pivot=x[left]
        i=left+1
        while(i<=j):
            while(x[i]<pivot):
                i+=1
            while(x[j]>pivot):
                j-=1
            if(i<j):
                InterChange(x,i,j)
        InterChange(x,left,j)
        QuickSort(x,left,j-1)
        QuickSort(x,j+1,right)
def InterChange(x,i,j):
    temp=x[i]
    x[i]=x[j]
    x[j]=temp
x=[1,3,9,7,12,23,4,16,20]
print('*********')
for a in x:
    if(a>x[len(x)-1]):
        InterChange(x,x.index(a),len(x)-1)
QuickSort(x,0,len(x)-1)
for a in x:
    print(a)

   这个基本程序的bug是不能有相同的数,否则会陷入死循环的哦~~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python3之弹性力学——应力张量1

    \[ \left[ \begin{array}{ccc} \sigma_{x} &\tau_{xy} &\tau_{xz}\\ \tau_{yx} &\sigm...

    py3study
  • 详细理解平衡二叉树AVL与Python实

    上一篇文章讨论的二叉搜索树,其时间复杂度最好的情况下是O(log(n)),但是最坏的情况是O(n),什么时候是O(n)呢?

    py3study
  • 给Python加速(性能加速的方法)

    这个说法深有体会。Python中多变的数据结构可以造成很大的差异,使用一个set就可以事半功倍。甚至一个自己定义的数据结构,对于内存,运算速度,处理方式等都有很...

    py3study
  • 2.布局解决方案 两列、三列、多列、不定宽+一列自适应<6>

    和上面的解决方案是一样的,自己动脑筋哦 下面的overflow的方式 display:table和flex大家自己练习。

    河湾欢儿
  • css+ js 实现圆环时钟

    小蔚
  • 微信公开课Pro提前曝光!腾讯云智慧零售会带来哪些新玩法?

    “去中心化”的智慧零售到底是什么? 腾讯云是如何实现智慧零售方案落地的呢? 智能+零售,腾讯云联合腾讯优图打造的优Mall又会有哪些创新玩法? 这一切答案,将...

    腾讯云智慧零售
  • Django学习笔记之Django的url反向解析

    Jetpropelledsnake21
  • Magic Leap One多款应用体验报告|在高清画质下看有趣的内容,并可长时间使用

    难道Magic Leap One真如外媒所说,只有在体验过后才能发现其优点?果不其然,自上周Next Reality开箱报告推出之后,大部分持怀疑态度的平台都逐...

    VRPinea
  • [javaSE] 网络编程(URL)

    陶士涵
  • IntelliJ IDEA 和 Eclipse等工具部署项目到Tomcat

    时下流行的两款IDE工具多为idea,Eclipse等产品,相比之下,idea更便捷,以页面样式,快捷性赢得了市场大部分开发者的喜爱。

    疯狂的KK

扫码关注云+社区

领取腾讯云代金券