交换排序

　　交换排序有冒泡排序和快速排序

冒泡排序

　　冒泡排序就是每次找出最大（最小）元素，放在集合最前或最后，这是最简单的排序算法

def bubble_sort(collection):
    #升序排列
    length=len(collection)
    for s in range(length-1):#可以假设只有一个元素的情况，这样可以直接返回
        flage=True#应该放在这里，而不是上面
        for i in range(length-1-s):
            if collection[i]>collection[i+1]:#前者大需要换位置,并需要判断他是否是最大的
                flage=False
                collection[i],collection[i+1]=collection[i+1],collection[i]
        # print("排序第",s+1,"轮之后：",collection)#print()好占时间啊
        # i++#i是自动递增的，我竟然写出如此愚蠢的
        if flage:
            break
    return collection

　　特点：是稳定的 T(n)=O(n^2) 原地排序

　　内层循环的操作是O（1）的，共执行n-1轮循环，每轮分别执行（n-1,n-2....1)=(n-1)(n-1+1)/2

快速排序

　　效率：

　　算法思想：分治法

　　快速排序是对冒泡排序的一种改进，冒泡排序作为一种广为人知的最简单的排序算法，存在着很多不足，比如他每趟遍历后只能从当前数列中挑出一个最大（最小）的数值，然后下趟工作再挑出剩下中的最大元素。这样看来，每趟之间几乎是完全独立的，这一趟的排序除了能使带排序的元素减少一个之外，并不会留下任何信息。这很明显就浪费了这一趟又一趟的比较。完全可以从一趟一趟中了解关于带排序的样本的更多信息。

　　快速排序就是另外一种思路，他最明显的特点就是“分而治之”。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

　　快速排序版本1

　　特点：需要额外的空间用来存放两个数组（一个比比较点大的，一个比比较点小的）、不需要两个游标，从前往后遍历就行

def quick_sort3(collection):
    length=len(collection)
    if length<=1:
        return collection
    else:
        pivot=collection[0]
        greater=[]#学会接受这样每当递归中定义变量，并不复杂
        lesser=[]
        for i in collection[1:]:
            greater.append(i) if i>=pivot else lesser.append(i)
        return quick_sort3(lesser)+[pivot]+quick_sort3(greater)

　　这个是稳定排序、需要额外的空间、时间复杂度是

　　快速排序版本2

　　另一种广为流传的思想是选择两个游标，游标是移动的，在初始化的时候，我们一般将数组元素的第一个和最后一个元素（注意，代表的数组地址，会移动），然后他们两个交替的向前或者向后移动，每次移动一个元素，然后与一个值比较（直到找到为止并不是一次移动一个），（并不会让他们两个相互比较，）我们习惯上将这个值称为key，这个值初始化为数组首元素。

　　在比较的过程中，由于两个游标（一个i，一个j）是交替移动的，所以他们必然有相遇的时候，我将每次相遇，看作为一轮比较的结束，这一轮会将待排序的数组分为3个部分，一个部分只有key，另外两个部分分别存放比key小和比key大的元素。这就是分而治之的结果，除了只有一个元素的结果，下一次的分治过程又会从他们里面开始。

　　每一轮中的比较结果首先从i或j与key的比较开始，是i还是j怎样都行。我只需要记住，比较是为了将结果向有序的升序（或者降序）去靠拢。每一轮都是为了减小颗粒度。拿升序来说，如果i代表的下标所指的数组元素比key大，那么他就应该和j交换，如果没有就向后移动一次，然后换j与key比较，如果j比key小，j和i就交换。

def quick_sort3(collection):
    length=len(collection)
    if length<=1:
        return collection
    else:
        pivot=collection[0]
        key=0
        i=0
        j=length-1
        while i<j:
            while collection[j]>pivot:
                j-=1
            if(i<j):
                collection[key],collection[j]=collection[j],collection[key]
                key=j
            while collection[i]<pivot:
                i+=1
            if i<j:
                collection[i],collection[key]=collection[key],collection[i]
                key=i
        return quick_sort3(collection[:key])+[collection[key]]+quick_sort3(collection[key+1:])

　　原地排序、时间复杂度不会算一趟的算法复杂度是N，然后大约需要logN次递归，所以时间复杂度是NlogN、空间复杂度是logN，每次需要一个嘛

　　数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差

　　快速排序版本2 修改

　　上面的快速排序在正常排序时时没有问题的，不过当遇到有大量重复的元素，而且元素为key的时候，就会造成排序失败

def quick_sort3(collection):
    length=len(collection)
    if length<=1:
        return collection
    else:
        pivot=collection[0]
        key=0
        i=0
        j=length-1
        repeat=[]#将重复的元素添入，只有大量的key重复的时候才会出错
        while i<j:#外层while负责让i，j一直移位，内层循环保证找到要交换的值，然后分为两个while，这样，i，j能交替运行

            while collection[j]>=pivot:
                if collection[j]==pivot and j!=key:
                    repeat.append(collection.pop(j))
                    # key-=1#因为此时key永远等于i的
                    #判断j！=key
                if j>0:
                    j-=1
                else:
                     return collection 
            if(i<j):
                collection[i],collection[j]=collection[j],collection[i]
                key=j
            while collection[i]<=pivot:
                if collection[i]==pivot and i!=key:
                    repeat.append(collection.pop(i))
                    j-=1#因为少了一个元素，j在后边
                    key-=1
                    # if i<length-1:因为j后面的都被干掉了
                    #     continue
                    # else:
                    #     i-=1
                if i<length-1:
                    i+=1 
                else:
                    return collection
            if i<j:
                collection[i],collection[j]=collection[j],collection[i]
                key=i
        repeat.append(collection[key])
        return quick_sort3(collection[:key])+repeat+quick_sort3(collection[key+1:])              

　　四不像版本

def quick_sort(collection):
    length=len(collection)
    i=0
    j=length-1
    if(length>1):
        key=collection[0]
        logging.info("新一轮的排序开始了i,j,key的值分别为",i,j,key,"被排序的数组是：",collection,'此次被排序数组的长度是：',length)
        while(i<j):
            logging.info('先输出i=%s  j=%s'%(i,j))
            while(collection[j]>key):
                j=j-1    
            collection[i],collection[j]=collection[j],collection[i]
            logging.info('*'*25+'又经过了一次j交换，交换的数组下标j的值为',j,'这时的数组为',collection)
            while(collection[i]<key):
                i=i+1
            collection[i],collection[j]=collection[j],collection[i]#正是这一句导致了重复定位ij的结果，因为即使上面的while
            #起了作用，这句也会运行的。
            logging.info('*'*25+'又经过了一次i交换，交换的数组下标i的值为',i,'这时的数组为',collection)
        logging.info("这一轮过后key两边的数组是："+' '*53,collection[0:i],'[',key,']',collection[i+1:length],'整个数组为：',collection,'\n')#要加逗号啦
        # L.extend(collection)
        #递归
        if(i>0):#是这里的问题，之前的i=0了因为数组的第一个元素是最小的就会出现这样的情况
            # print('现在的L是：',L)
            logging.info('对%s的左边排序'%(key))
            logging.info('%s左边返回的结果是'%(key),quick_sort(collection[0:i]),'key是',key)
            L.append(key)#这里也是哦，不必担心递归的原因会不会添加错，应该这样想，正是因为递归的原因，才保证了添加的顺序
            #性，因为这里也算是在方法体中嘛。
            # s=quick_sort(collection[0:i])
            # if(s!=-1):
            #     L.extend(s)
            # L.append(key)
            # print("存储了:",s,'key是',key)
        else:
            L.append(key)
            logging.info('%s的左边没有元素了'%(key),'向L中添加key，此时L为：',L)
        if(j+1<length):#为什么这里不能写成elif类，因为这两个判断应该是相互独立的，即在分而治之的过程中，i代表的左边
            #没有元素了，然后在处理右边，如果改成elif，那么情况就会变成如果i<0了，那么就会不管右边了，即判断
            #右边需不需要处理的判断就会只有满足了第一个条件之后才会进入。
            # print('右边返回的结果是',quick_sort(collection[j+1:length]))
            logging.info('对%s的右边进行排序'%(key))
            logging.info('%s右边返回的结果是'%(key),quick_sort(collection[j+1:length]))
            # s=quick_sort(collection[j+1:length])
            # if(s!=-1):
            #     L.extend(s)
            # print("存储了:",s)
            # print('现在的L是：',L)
        else:
            logging.info('%s的右边没有元素了'%(key))
    # print("此轮被排序的数组长度为1")
    elif(length>0):
        L.extend(collection)#在这里添加这个想法真的很棒，虽然是想了好久才想出来这个办法，但不得不佩服我自己，正是经过了前面的试错
        #才能让我想到不需要在递归中对结果进行判断，而是在被调用的方法体中，直接找出正确的（即想要的）返回结果去添加。
        return collection#忽略了一点，原以为这里即使不写else return也会只有在数组长度等于1的长度下被返回的，即返回单个数，但实际情况可能不是这样的。
    logging.info('返回-1代表这里已经没有元素了，或许是已经被排序过了或者是原数组的两端')
    return -1

对比

　　采用版本1与选择排序相比较，数据为随机数据，大小为1000，运行100次结果差了

详细数据：[0.07895469666, 0.07895302773, 0.08095312119, 0.08338785172, 0.08293843269, 0.08093643188, 0.08128547668, 0.0819542408, 0.08295297623, 0.08095312119, 0.08395147324, 0.08097147942, 0.082947
01576, 0.08095216751, 0.07995295525, 0.08095240593, 0.0829513073, 0.0809533596, 0.0839509964, 0.0829513073, 0.08095312119, 0.08097696304, 0.08094286919, 0.08095240593, 0.08195757866, 0.08095288277, 0.0809533596, 0.08095407486, 0.07995390892, 0.07995271683, 0.08095264435, 0.08295178413, 0.08395934105, 0.07995295525, 0.08295154572, 0.08195376396, 0.08097577095, 0.08192324638, 0.0809533596, 0.08294081688, 0.08194708824, 0.08295035362, 0.08295178413, 0.08195447922, 0.08295416832, 0.08094596863, 0.08295106888, 0.08195185661, 0.08195209503, 0.08195328712, 0.08095407486, 0.08197164536, 0.08094024658, 0.08195352554, 0.08195328712, 0.0819504261, 0.08195257187, 0.08095240593, 0.08095288277, 0.08095312119, 0.08395195007, 0.08095312119, 0.08195996284, 0.08093881607, 0.08095312119, 0.08494997025, 0.08195304871, 0.08095192909, 0.08195161819, 0.08046650887, 0.08190274239, 0.08197069168, 0.08202648163, 0.08195185661, 0.08094859123, 0.07995486259, 0.08295321465, 0.08095264435, 0.08194589615, 0.08194684982, 0.07995510101, 0.08095288277, 0.07995533943, 0.08095288277, 0.08295106888, 0.08295273781, 0.0799536705, 0.08195281029, 0.08193540573, 0.07994103432, 0.08295202255, 0.08195304871, 0.08095312119, 0.08195400238, 0.08095359802, 0.08195233345, 0.08295321465, 0.08095383644, 0.08095288277, 0.08295273781]
运行了100次，平均运行时间差(me-other)/(bubble-quick)(正数代表你是个弟弟）是：0.08164532900
前者平均运行时间0.08336502552,后者平均运行时间0.00171969652,前者约是后者的48.4766倍

我的问题

　　1）当所有分而治之的结果 的左边都被排序好了，或者颗粒度是最小的，那么右边的就不排了。换句话说，剩下的所有工作都不去做了。

(sort) λ python bubble_sort.py
未排序之前：      [70, 78, 85, 10, 66, 43, 89, 62, 11, 41]
key两边的数组是： [41] [ 70 ] [85, 10, 66, 43, 89, 62, 11, 78]
*************************i，j的值分别为 1 9
key两边的数组是： [41, 11] [ 70 ] [10, 66, 43, 89, 62, 85, 78]
*************************i，j的值分别为 2 8
key两边的数组是： [41, 11, 62, 10, 66, 43] [ 70 ] [89, 85, 78]
*************************i，j的值分别为 6 7
key两边的数组是： [41, 11, 62, 10, 66, 43] [ 70 ] [89, 85, 78]
*************************i，j的值分别为 6 6
key两边的数组是： [10, 11] [ 41 ] [62, 66, 43]
*************************i，j的值分别为 2 3
key两边的数组是： [10, 11] [ 41 ] [62, 66, 43]
*************************i，j的值分别为 2 2
key两边的数组是： [] [ 10 ] [11]
*************************i，j的值分别为 0 0
key两边的数组是： [] [ 41 ] [62, 66, 43]
*************************i，j的值分别为 0 0
key两边的数组是： [] [ 70 ] [89, 85, 78]
*************************i，j的值分别为 0 0
排序之后： [41, 11, 62, 10, 66, 43, 70, 89, 85, 78]
耗费时间： 0.023987293243408203

　　2）为什么第二趟都从0开始啊

　　解决办法：这个不是程序的原因，而是因为程序递归到第二次时，穿过去的数组中指定的key就是最小的了。　　　

未排序之前：                                                                     [6, 5, 4, 8, 7, 9, 3, 2, 1]
*************************又经过了一次j交换，交换的数组下标j的值为 8 这时的数组为 [1, 5, 4, 8, 7, 9, 3, 2, 6]
*************************又经过了一次i交换，交换的数组下标i的值为 3 这时的数组为 [1, 5, 4, 6, 7, 9, 3, 2, 8]
*************************又经过了一次j交换，交换的数组下标j的值为 7 这时的数组为 [1, 5, 4, 2, 7, 9, 3, 6, 8]
*************************又经过了一次i交换，交换的数组下标i的值为 4 这时的数组为 [1, 5, 4, 2, 6, 9, 3, 7, 8]
*************************又经过了一次j交换，交换的数组下标j的值为 6 这时的数组为 [1, 5, 4, 2, 3, 9, 6, 7, 8]
*************************又经过了一次i交换，交换的数组下标i的值为 5 这时的数组为 [1, 5, 4, 2, 3, 6, 9, 7, 8]
*************************又经过了一次j交换，交换的数组下标j的值为 5 这时的数组为 [1, 5, 4, 2, 3, 6, 9, 7, 8]
*************************又经过了一次i交换，交换的数组下标i的值为 5 这时的数组为 [1, 5, 4, 2, 3, 6, 9, 7, 8]
这一轮过后key两边的数组是：                                                      [1, 5, 4, 2, 3] [ 6 ] [9, 7, 8]
*************************又经过了一次j交换，交换的数组下标j的值为 0 这时的数组为 [1, 5, 4, 2, 3]
*************************又经过了一次i交换，交换的数组下标i的值为 0 这时的数组为 [1, 5, 4, 2, 3]
这一轮过后key两边的数组是：                                                      [] [ 1 ] [5, 4, 2, 3]
*************************又经过了一次j交换，交换的数组下标j的值为 0 这时的数组为 [6, 9, 7, 8]
*************************又经过了一次i交换，交换的数组下标i的值为 0 这时的数组为 [6, 9, 7, 8]
这一轮过后key两边的数组是：                                                      [] [ 6 ] [9, 7, 8]
排序之后： [1, 5, 4, 2, 3, 6, 9, 7, 8] L: [1, 5, 4, 2, 3, 6, 9, 7, 8]

　　第一次版本，失败了

def quick_sort(collection):
    length=len(collection)
    i=0
    j=length-1
    if(length>1):
        key=collection[0]
        print("新一轮的排序开始了i,j,key的值分别为",i,j,key,"被排序的数组是：",collection,'此次被排序数组的长度是：',length)
        while(i<j):
            while(collection[j]>key):
                j=j-1    
            collection[i],collection[j]=collection[j],collection[i]
            print('*'*25+'又经过了一次j交换，交换的数组下标j的值为',j,'这时的数组为',collection)
            while(collection[i]<key):
                if(i<j):
                    i=i+1
                break
            collection[i],collection[j]=collection[j],collection[i]
            print('*'*25+'又经过了一次i交换，交换的数组下标i的值为',i,'这时的数组为',collection)
        print("这一轮过后key两边的数组是："+' '*53,collection[0:i],'[',key,']',collection[i+1:length],'整个数组为：',collection,'\n')#要加逗号啦
        # L.extend(collection)
        #递归
        if(i>0):
            # print('现在的L是：',L)
            print('对%s的左边排序'%(key))
            print('%s左边返回的结果是'%(key),quick_sort(collection[0:i]),'key是',key)
            # s=quick_sort(collection[0:i])
            # if(s!=-1):
            #     L.extend(s)
            # L.append(key)
            # print("s是：",s,'key是',key)
        if(j>0):#为什么这里不能写成elif类，因为这两个判断应该是相互独立的，即在分而治之的过程中，i代表的左边
            #没有元素了，然后在处理右边，如果改成elif，那么情况就会变成如果i<0了，那么就会不管右边了，即判断
            #右边需不需要处理的判断就会只有满足了第一个条件之后才会进入。
            # print('右边返回的结果是',quick_sort(collection[j+1:length]))
            print('对%s的右边进行排序'%(key))
            print('%s右边返回的结果是'%(key),quick_sort(collection[j+1:length]))
            # s=quick_sort(collection[j+1:length])
            # if(s!=-1):
            #     L.extend(s)
            # print("s是：",s)
            # print('现在的L是：',L)
    # print("此轮被排序的数组长度为1")
    elif(length>0):
        return collection#忽略了一点，原以为这里即使不写else return也会只有在数组长度等于1的长度下被返回的，即返回单个数，但实际情况可能不是这样的。
    print('这里已经没有元素了')
    return -1



#产生排序数组
# collection=random.sample(range(1,100),10)
# collection =[6,5,4,8,7,9,3,1,2]
collection= [94, 37, 97, 31, 26, 79, 10, 35, 40, 6]
startTime=time.time()
print("未排序之前："+' '*68,collection)#不能写成+(会提示为不是str类型数据，要写成这样)
print("排序之后：",quick_sort(collection),'L:',L)
endTime=time.time()
print("耗费时间：",endTime-startTime)

　　失败的原因是：

未排序之前：                                                                     [94, 37, 97, 31, 26, 79, 10, 35, 40, 6]
新一轮的排序开始了i,j,key的值分别为 0 9 94 被排序的数组是： [94, 37, 97, 31, 26, 79, 10, 35, 40, 6] 此次被排序数组的长度是： 10
*************************又经过了一次j交换，交换的数组下标j的值为 9 这时的数组为 [6, 37, 97, 31, 26, 79, 10, 35, 40, 94]
*************************又经过了一次i交换，交换的数组下标i的值为 1 这时的数组为 [6, 94, 97, 31, 26, 79, 10, 35, 40, 37]
*************************又经过了一次j交换，交换的数组下标j的值为 9 这时的数组为 [6, 37, 97, 31, 26, 79, 10, 35, 40, 94]
*************************又经过了一次i交换，交换的数组下标i的值为 2 这时的数组为 [6, 37, 94, 31, 26, 79, 10, 35, 40, 97]
*************************又经过了一次j交换，交换的数组下标j的值为 8 这时的数组为 [6, 37, 40, 31, 26, 79, 10, 35, 94, 97]
*************************又经过了一次i交换，交换的数组下标i的值为 3 这时的数组为 [6, 37, 40, 94, 26, 79, 10, 35, 31, 97]
*************************又经过了一次j交换，交换的数组下标j的值为 8 这时的数组为 [6, 37, 40, 31, 26, 79, 10, 35, 94, 97]
*************************又经过了一次i交换，交换的数组下标i的值为 4 这时的数组为 [6, 37, 40, 31, 94, 79, 10, 35, 26, 97]
*************************又经过了一次j交换，交换的数组下标j的值为 8 这时的数组为 [6, 37, 40, 31, 26, 79, 10, 35, 94, 97]
*************************又经过了一次i交换，交换的数组下标i的值为 5 这时的数组为 [6, 37, 40, 31, 26, 94, 10, 35, 79, 97]
*************************又经过了一次j交换，交换的数组下标j的值为 8 这时的数组为 [6, 37, 40, 31, 26, 79, 10, 35, 94, 97]
*************************又经过了一次i交换，交换的数组下标i的值为 6 这时的数组为 [6, 37, 40, 31, 26, 79, 94, 35, 10, 97]
*************************又经过了一次j交换，交换的数组下标j的值为 8 这时的数组为 [6, 37, 40, 31, 26, 79, 10, 35, 94, 97]
*************************又经过了一次i交换，交换的数组下标i的值为 7 这时的数组为 [6, 37, 40, 31, 26, 79, 10, 94, 35, 97]
*************************又经过了一次j交换，交换的数组下标j的值为 8 这时的数组为 [6, 37, 40, 31, 26, 79, 10, 35, 94, 97]
*************************又经过了一次i交换，交换的数组下标i的值为 8 这时的数组为 [6, 37, 40, 31, 26, 79, 10, 35, 94, 97]
这一轮过后key两边的数组是：                                                      [6, 37, 40, 31, 26, 79, 10, 35] [ 94 ] [97] 整个数组为： [6, 37, 40, 31, 26, 79, 10, 35, 94, 97]

对94的左边排序
新一轮的排序开始了i,j,key的值分别为 0 7 6 被排序的数组是： [6, 37, 40, 31, 26, 79, 10, 35] 此次被排序数组的长度是： 8
*************************又经过了一次j交换，交换的数组下标j的值为 0 这时的数组为 [6, 37, 40, 31, 26, 79, 10, 35]
*************************又经过了一次i交换，交换的数组下标i的值为 0 这时的数组为 [6, 37, 40, 31, 26, 79, 10, 35]
这一轮过后key两边的数组是：                                                      [] [ 6 ] [37, 40, 31, 26, 79, 10, 35] 整个数组为： [6, 37, 40, 31, 26, 79, 10, 35]#这里该向下递归的没有递归

这里已经没有元素了
94左边返回的结果是 -1 key是 94
对94的右边进行排序
94右边返回的结果是 [97]
这里已经没有元素了
排序之后： -1 L: []
耗费时间： 0.008994817733764648

　　我猜想可能是因为对左边或右边进行排序的时候没有响应的判断逻辑。

3）修正

while(i<j):#这里不应该是i<j-1，即使这样能避免有些交换数组下标的重复，但会产生下面的问题，当排序三个元素的数组中key为中间值时，会忽略右边的元素。
            print('先输出i=%s  j=%s'%(i,j))
            while(collection[j]>key):
                j=j-1    
            collection[i],collection[j]=collection[j],collection[i]
            print('*'*25+'又经过了一次j交换，交换的数组下标j的值为',j,'这时的数组为',collection)
            while(collection[i]<key):
                i=i+1
            collection[i],collection[j]=collection[j],collection[i]#正是这一句导致了重复定位ij的结果，因为即使上面的while
            #起了作用，这句也会运行的。
            print('*'*25+'又经过了一次i交换，交换的数组下标i的值为',i,'这时的数组为',collection)


新一轮的排序开始了i,j,key的值分别为 0 2 4 被排序的数组是： [4, 5, 3] 此次被排序数组的长度是： 3
先输出i=0  j=2
*************************又经过了一次j交换，交换的数组下标j的值为 2 这时的数组为 [3, 5, 4]
*************************又经过了一次i交换，交换的数组下标i的值为 1 这时的数组为 [3, 4, 5]
先输出i=1  j=2
*************************又经过了一次j交换，交换的数组下标j的值为 1 这时的数组为 [3, 4, 5]
*************************又经过了一次i交换，交换的数组下标i的值为 1 这时的数组为 [3, 4, 5]
这一轮过后key两边的数组是：                                                      [3] [ 4 ] [5] 整个数组为： [3, 4, 5]

对4的左边排序
4左边返回的结果是 [3] key是 4
对4的右边进行排序
4右边返回的结果是 [5]
这里已经没有元素了
2右边返回的结果是 -1
这里已经没有元素了
6左边返回的结果是 -1 key是 6
对6的右边进行排序