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是不能有相同的数，否则会陷入死循环的哦~~