Python语言的冒泡排序、选择排序、插入排序、快速排序

小咪咪 2021-12-14 04:34 439阅读 0赞

冒泡排序 稳定  
两两比较，每一轮最大的数会排序到右边（即最右边慢慢排序至左边）

def bubbleSort(list):
        for i in range(len(list)):
            for  j in range(0,len(list)-1-i):
                if list[j]>list[j+1]:
                    list[j],list[j+1]=list[j+1],list[j]
            #print(list) #查看每一轮的排序结果
        return list
    test=[23,38,22,45,23,67,31,15,41]
    print(bubbleSort(test))
    
    # [23, 22, 38, 23, 45, 31, 15, 41, 67]
    # [22, 23, 23, 38, 31, 15, 41, 45, 67]
    # [22, 23, 23, 31, 15, 38, 41, 45, 67]
    # [22, 23, 23, 15, 31, 38, 41, 45, 67]
    # [22, 23, 15, 23, 31, 38, 41, 45, 67]
    # [22, 15, 23, 23, 31, 38, 41, 45, 67]
    # [15, 22, 23, 23, 31, 38, 41, 45, 67]

选择排序 稳定  
与所有未排序的数比较，每一轮最小的数会排序到左边（即最左边慢慢排序至右边）

def selectSort(list):
        for i in range(len(list)):
            for  j in range(i+1,len(list)):
                if list[i]>list[j]:
                    list[i],list[j]=list[j],list[i]
            #print(list) #查看每一轮的排序结果
        return list
    test =[0, 13, 2, 81, 13, 127, 19, 312, 42]
    #test = [13,38,65,97,76,49,27]
    print(selectSort(test))
    
    # [13, 38, 65, 97, 76, 49, 27]
    # [13, 27, 65, 97, 76, 49, 38]
    # [13, 27, 38, 97, 76, 65, 49]
    # [13, 27, 38, 49, 97, 76, 65]
    # [13, 27, 38, 49, 65, 97, 76]
    # [13, 27, 38, 49, 65, 76, 97]

插入排序 稳定  
从第二个数起，与前面的数逐一比较，见缝插针

def insertSort(list):
        for i in range(1,len(list)):
            for  j in range(0,i):
                if list[i]<list[j]:
                    list[i],list[j]=list[j],list[i]
           #print(list) #查看每一轮的排序结果
        return list
    test =[0, 13, 2, 81, 13, 127, 19, 312, 42]
    print(insertSort(test))
    
    # [0, 13, 2, 81, 13, 127, 19, 312, 42]
    # [0, 2, 13, 81, 13, 127, 19, 312, 42]
    # [0, 2, 13, 81, 13, 127, 19, 312, 42]
    # [0, 2, 13, 13, 81, 127, 19, 312, 42]
    # [0, 2, 13, 13, 81, 127, 19, 312, 42]
    # [0, 2, 13, 13, 19, 81, 127, 312, 42]
    # [0, 2, 13, 13, 19, 81, 127, 312, 42]
    # [0, 2, 13, 13, 19, 42, 81, 127, 312]

快速排序

def quickSort(list,left,right):
        if left>=right:
            return
        i=left
        j = right
        key = list[i]
        while i<j:
            while i<j and key<=list[j]:
                # --j
                j -=1
            list[i]=list[j]
            while i<j and key>list[i]:
                # --j
                i +=1
            list[j]=list[i]
            list[i]=key
            quickSort(list,left,i-1)
            quickSort(list,i+1,right)
        return list
    # test =[0, 13, 2, 81, 13, 127, 19, 312, 42]
    test = [ 5 ,  3 ,  8   ,6  , 0  , 9  , 1,   7  , 4  , 2  ]
    print(quickSort(test,0,len(test)-1 ))
    
    #     # 稳定性：不稳定
    #     # 最优时间复杂度：O(nlogn)
    #     # 最坏时间复杂度：O(n^2)