排序算法（python实现）

小咪咪 2022-04-17 01:56 215阅读 0赞

排序算法一共有2类:

算法时间fuzh复杂读与nlogn比较，大为非线性类，小为线性类；

###         非线性类比较类排序有：交换排序（冒泡，快速），插入排序（简单插入，shell），归并排序（2路归并，多路归并）,选择排序（简单选择，堆排序）； ###

###         线性时间非比较类排序有：基数排序，计数排序，还有桶排序。 ###

## ##

下面代码实现了8种算法，用户进入后直接按命令选择就好，代码如下：

import copy
    
    #插入排序
    def insert_sort(ilist):
        for i in range(len(ilist)):
            for j in range(i):
                if ilist[i] < ilist[j]:
                    ilist.insert(j, ilist.pop(i))
                    break
        return ilist
    
    #shell排序
    def shell_sort(slist):
        gap = len(slist)
        while gap > 1:
            gap = gap // 2
            for i in range(gap, len(slist)):
                for j in range(i % gap, i, gap):
                    if slist[i] < slist[j]:
                        slist[i], slist[j] = slist[j], slist[i]
        return slist
    
    #冒泡排序
    def bubble_sort(blist):
        count = len(blist)
        for i in range(0, count):
            for j in range(i + 1, count):
                if blist[i] > blist[j]:
                    blist[i], blist[j] = blist[j], blist[i]
        return blist
    
    #快速排序
    def quick_sort(qlist):
        if qlist == []:
            return []
        else:
            qfirst = qlist[0]
            qless = quick_sort([l for l in qlist[1:] if l < qfirst])
            qmore = quick_sort([m for m in qlist[1:] if m >= qfirst])
            return qless + [qfirst] + qmore
        
    #选择排序
    def select_sort(slist):
        for i in range(len(slist)):
            x = i
            for j in range(i, len(slist)):
                if slist[j] < slist[x]:
                    x = j
            slist[i], slist[x] = slist[x], slist[i]
        return slist
    
    
     #堆排序
    def heap_sort(hlist):
        def heap_adjust(parent):
            child = 2 * parent + 1  # left child
            while child < len(heap):
                if child + 1 < len(heap):
                    if heap[child + 1] > heap[child]:
                        child += 1  # right child
                if heap[parent] >= heap[child]:
                    break
                heap[parent], heap[child] = heap[child], heap[parent]
                parent, child = child, 2 * child + 1
     
        heap, hlist = copy.copy(hlist), []
        for i in range(len(heap) // 2, -1, -1):
            heap_adjust(i)
        while len(heap) != 0:
            heap[0], heap[-1] = heap[-1], heap[0]
            hlist.insert(0, heap.pop())
            heap_adjust(0)
        return hlist
    
    #基数排序
    def radix_sort(array):
        bucket, digit = [[]], 0
        while len(bucket[0]) != len(array):
            bucket = [[], [], [], [], [], [], [], [], [], []]
            for i in range(len(array)):
                num = (array[i] // 10 ** digit) % 10
                bucket[num].append(array[i])
            array.clear()
            for i in range(len(bucket)):
                array += bucket[i]
            digit += 1
        return array
    
    
    #归并排序
    def merge_sort(array):
        def merge_arr(arr_l, arr_r):
            array = []
            while len(arr_l) and len(arr_r):
                if arr_l[0] <= arr_r[0]:
                    array.append(arr_l.pop(0))
                elif arr_l[0] > arr_r[0]:
                    array.append(arr_r.pop(0))
            if len(arr_l) != 0:
                array += arr_l
            elif len(arr_r) != 0:
                array += arr_r
            return array
     
        def recursive(array):
            if len(array) == 1:
                return array
            mid = len(array) // 2
            arr_l = recursive(array[:mid])
            arr_r = recursive(array[mid:])
            return merge_arr(arr_l, arr_r)
     
        return recursive(array)
    
    def main():
        
         print("!!!!!!!!!!!!!!!!欢迎进入杨远林的排序世界!!!!!!!!!!!!!!!!")
         print("1(冒泡排序)！")
         print("2(快速排序)！")
         print ("3(插入排序)！")
         print("4(shell排序)！")
         print("5(简单选择排序)！")
         print("6(堆排序)！")
         print("7(2路归并排序)！")
         print("8(多路归并排序)！")
         a=[4,5,6,7,3,2,6,9,8]
         print("原来数组为！",a)
         a=int(input("请输入数据选择:"))
         i=1
         while(i==1):
             
             
             if(a==1):
                 
                 blist = bubble_sort([4,5,6,7,3,2,6,9,8])
                 print(blist)
                 break
             
             elif(a==2):
                 qlist = quick_sort(a)
                 print(qlist)
                 break
             elif(a==3):
                 
                 ilist = insert_sort([4,5,6,7,3,2,6,9,8])
                 print(ilist)
                 break
             elif(a==4):
                 slist = shell_sort([4,5,6,7,3,2,6,9,8])
                 print(slist)
                 break
             elif(a==5):
                 slist = select_sort([4,5,6,7,3,2,6,9,8])
                 print(slist)
                 break
             elif(a==6):
                 hlist = heap_sort([4,5,6,7,3,2,6,9,8])
                 print(hlist)
                 break
             elif(a==7):
                 rlist=radix_sort([4,5,6,7,3,2,6,9,8])
                 print(rlist)
                 break
             elif(a==8):
                  glist = merge_sort([4,5,6,7,3,2,6,9,8])
                  print(glist)
                  break
             elif(a==0):
                  
                 break
             else :
                 print("输入不合法。重新输入！")
                 a=int(input("请输入数据选择:"))
                 continue
            
                    
    main()