Python实现八大排序算法

快来打我* 2022-05-23 07:29 209阅读 0赞

**（原创作者：陈玓玏）**

import math
    import random
    '''
    时间复杂度记忆- 
       冒泡、选择、直接插入排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O（n2）O（n2）（一遍找元素O(n)O(n)，一遍找位置O(n)O(n)）
    快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)O(nlogn)（一遍找元素O(n)O(n)，一遍找位置O(logn)O(logn)），在最坏的情况下，快排和希尔复杂度还会变得和冒泡一样
       计数排序和基排序不属于这些范畴，它们的时间复杂度和空间复杂度如下：
       计数排序	O(n+k)	O(n+k)	O(n+k)	是
       基数排序	O(N∗M)	O(N∗M)	O(M)	是
    稳定性记忆-“快希选堆”（快牺牲稳定性） 
       排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。
    '''
    
    
    
    # 1. 冒泡排序
    def maopao(list):  #两个for循环，时间复杂度始终为n^2
        for i in range(len(list)):
            for j in range(len(list)-i-1):
                if(list[j]>list[j+1]):
                    list[j],list[j+1] = list[j+1],list[j]
            print(list)
        return list
    
    
    # 2. 选择排序
    def xuanze(list):   #两个for循环，不一样的是不会每次都交换，一轮内部循环后交换一次
        tmp = ['','']
        for i in range(len(list)):
            tmp = [list[i],i]
            for j in range(i+1,len(list),1):
                if(list[j]<tmp[0]):
                    tmp = [list[j],j]
            if tmp[1]!=i:
                list[i],list[tmp[1]] = list[tmp[1]],list[i]
            print(i,list)
        return list
    
    # 3. 插入排序
    def charu(list):    #两个for循环，外层是一个个往后挪，里层是前面已经排好序的
        for i in range(1,len(list),1):
            for j in range(0,i,1):
                print(i,j,list)
                if list[i]<list[j]:
                    list[i],list[j] = list[j],list[i]
            print(list)
        return list
    
    # 3. 插入排序改良版，前面的插入排序是直接交换，可能出现2插入[1,2,3,4]中变为[1,2,2,4,3]这种情况，其实是不对的，所以要改成从后往前比较
    def charu2(list):
        for i in range(1,len(list),1):
            tmp = list[i]
            for j in range(0,i,1):
                #tmp = list[i]   #不知道为什么，当把tmp定义在这里的时候，tmp的值会在两轮list[i-j] = tmp之后改变，导致结果错误
                #print(tmp,list[i-j])
                if tmp<list[i-j]:
                    list[i-j+1] = list[i-j]
                    list[i-j] = tmp
            print(list)
        return list
    插入排序一个更容易理解的版本：
    def charu(list):
        for i in range(1,len(list)):
            for j in range(i,0,-1):
                print(i,j)
                if list[j]<list[j-1]:
                   list[j-1],list[j] = list[j],list[j-1]
                print(list)
            print(list)
    
    # 4. 快排
    def kuaipai(list):  #随机选择一个中位数，做二分，大的放左边，小的放右边，再递归，一个for循环，但是要递归，所以复杂度根据初始序列的好坏程度来决定
        print(list)
        if len(list) > 1:
            mid = list[0]
            bigger = []
            smaller = []
            for i in range(1,len(list),1):
                if list[i] <mid:
                    smaller.append(list[i])
                else:
                    bigger.append(list[i])
            # if smaller!= []:
            #     smaller = kuaipai(smaller)
            # if bigger!= []:
            #     bigger = kuaipai(bigger)
            list = kuaipai(smaller)+ [mid] + kuaipai(bigger)
            #list = smaller + [mid] + bigger
            print(list)
            return list
        else:
            return list
    
    
    # 5. 归并
    def guibing(list):  #以中间位置为划分，左边右边按位置分开，然后依次类推做划分，最后组内排序、合并，也有递归过程
        if len(list) > 1:
            print('shuru',list)
            before = list[0:int(len(list)/2)]
            after = list[int(len(list)/2):]
            print('before,after',before,after)
            before = guibing(before)
            after = guibing(after)
            print('before1,after1', before, after)
            #下面是对两个排序数组进行合并，tmplist记录的是before和after两个数组的指针
            tmplist = [0,0]
            while tmplist[0]!=len(before) and tmplist[1]!=len(after):
                if before[tmplist[0]] < after[tmplist[1]]:
                    tmplist.append(before[tmplist[0]])】
                    tmplist[0] = tmplist[0]+1
                else:
                    tmplist.append(after[tmplist[1]])
                    tmplist[1] = tmplist[1] + 1
            #下面代码的意思是：如果两个有序数组合并的过程中，有一个先遍历完了，那另一个就直接加入到数组后面
            if tmplist[0] == len(before):
                tmplist = tmplist + after[tmplist[1]:]
            if tmplist[1] == len(after):
                tmplist = tmplist + before[tmplist[0]:]
            print('shuchu',tmplist[2:])
            return tmplist[2:]
        else:
            return list
    
    
    # 6. 计数排序
    def jishu(list):
        count_list = []
        relist = []
        tmp = [0,0]
        while sum(count_list) < len(list):
            for i in list:
                if i==tmp[0]:
                    tmp[1] = tmp[1] +1
                print(i,tmp[1])
            tmp[0] = tmp[0] + 1
            count_list.append(tmp[1])
            tmp[1] = 0
            print(count_list)
        for i in range(len(count_list)):
            while count_list[i]!=0:
                relist.append(i)
                count_list[i] = count_list[i]-1
        print(relist)
        return relist
    
    # 6. 改良的计数排序，因为上面的需要遍历n次，时间复杂度太高，而改良版只需要遍历一次
    #两个for循环，但是只遍历一次列表，第一个是建立列表的，第二个是输出列表的
    def jishu2(list):
        count_list = []
        relist = []
        list0 = [0]
        for i in list:
            if i+1 > len(count_list):
                count_list = count_list + list0*(i+1-len(count_list))   #增加数组的长度，并且新增项的初始值都是0
                print(count_list)
            count_list[i] = count_list[i] + 1
        for i in range(len(count_list)):
            while count_list[i]!=0:
                relist.append(i)
                count_list[i] = count_list[i]-1
        print(relist)
        return relist
    
    
    # 7. 桶排序
    def tongpai(list):
        count_list = []
        relist = []
        for i in list:
            flo = math.floor(i)
            if flo + 1 > len(count_list):
                for h in range(flo + 1 - len(count_list)):
                    count_list.append([])
                #count_list = count_list + list0 * (flo + 1 - len(count_list))  #对于数组用这种方法会出错
                print(count_list)
            count_list[flo].append(i)
            if len(count_list[flo])>1:
                for j in range(len(count_list[flo])):
                    if count_list[flo][len(count_list[flo])-j-1] > i:
                        count_list[flo][len(count_list[flo]) - j] = count_list[flo][len(count_list[flo]) - j-1]
                        count_list[flo][len(count_list[flo]) - j-1] = i
        for i in range(len(count_list)):
            if len(count_list[i]) != 0:
                relist = relist + count_list[i]
                print('relist',relist)
        return relist
    
    
    # 8. 堆排序
    def dadingdui(list):   #先建大顶堆
        n = math.log(len(list)+1,2)
        for i in range(len(list)):
            if i*2+1<=len(list)-1:  #这句判断当前节点是否是叶子节点,条件成立时表示不是叶子节点
                if i*2+1==len(list)-1:  #这句表示只有一个左叶子节点
                    if list[i]<list[i*2+1]:
                        list[i],list[i * 2 + 1] = list[i*2+1],list[i]
                else:  #当节点有左右两个叶子节点时
                    maxl = list[i]
                    loc = i
                    for j in [1,2]:
                        if list[i*2+j]>maxl:
                            maxl = list[i*2+j]
                            loc = i*2+j
                    list[i],list[loc] = list[loc],list[i]
        print(list)
        return list
    
    #二叉树有多少层，就要检查多少遍大顶堆的正确性
    def duipai(list):
        for i in range(math.floor(math.log(len(list),2))+3):
            list = dadingdui(list)
        print(list)
        relist = [0]*len(list)
        for i in range(len(list)):
            list[0],list[len(list)-1] = list[len(list)-1],list[0]
            relist[len(list)-1] = list[len(list)-1]
            list.pop()
            if len(list)>0:
                for j in range(math.floor(math.log(len(list), 2)) + 3):
                    list = dadingdui(list)
            print(len(relist),relist)
    
    
    
    
    
    list = [100,900,60,30,1000,1]
    list = [1,3,5,7,9,10,3]
    list = []
    for i in range(40):
        list.append(random.randint(1,100))
    print(list)
    # list = [7,6,5,4,3,2,1]
    # list = [0,4,5,6,2,2,6,8,9,1,2,4,5,6,7,8,9,10,9,2,2,2,3,4,5,11]  #针对计数排序的
    # list = [0,4.1,5.2,6.3,2.9,2.5,6.1,8.7,9.1,1,2.5,4.6,5.9,6.1,7.2,8,9,10,9.7,2.5,2.2,2,3.3,4.6,5.1,11]  #针对桶排序的
    #maopao(list)
    #xuanze(list)
    #charu(list)
    #charu2(list)
    #kuaipai(list)
    #guibing(list)
    #jishu(list)
    #jishu2(list)
    #tongpai(list)
    duipai(list)