python实现7种排序

青旅半醒 2022-05-29 04:45 36阅读 0赞

虽然python做排序这些是比不过c的，可是权当复习下算法也好。

import random #用于测试
    import time # 用于测试
    
    def selection_sort(mylist):
        #选择排序的思路是从头到尾，每次选择未排序中最小那个
        #然后把它放到已排序的末尾直到排序结束
        length=len(mylist)
        #能用for不要用while，for比while快
        for i in range(length-1):#最末尾那个不用排了，所以是length-1
            min_index=i
            for j in range(i+1,length):#从mylist[i]后面一个直到末尾找最小的
                if mylist[j]<mylist[min_index]:
                    min_index=j
            if i!=min_index:
                mylist[i], mylist[min_index] = mylist[min_index], mylist[i]  # 交换
        return mylist
    
    def bubble_sort(mylist):
        #冒泡排序的思路是从后往前，与前一个元素比较然后把小的数交换上去，形如冒泡
        #一次冒泡就完成一个数的排序
        length=len(mylist)
        for i in range(length):
            for j in range(length-1,i,-1):#列表的末尾到i+1
                if mylist[j]<mylist[j-1]:
                    mylist[j],mylist[j-1]=mylist[j-1],mylist[j]
        return mylist
    
    def insertion_sort(mylist):
        #插入排序的思路是从未排序的部分列表从头到尾选一个元素插到已排序的部分列表中
        #下面的是在传统的插入排序中做了小优化，没有交换操作,性能会好一点
        for i in range(1,len(mylist)):
            curr_num=mylist[i]
            for j in range(i-1,-1,-1):
                if mylist[j]>curr_num:#如果已排序的比准备排的这个大
                    mylist[j+1]=mylist[j]#那么这个元素就推后一位（最后再把要排的那个赋值回来）
                else:#说明找到了不比要排的大的，那么此元素的后一个要替换，故要+1
                    j+=1
                    break
            mylist[j]=curr_num#非中断结束的就直接赋值换回来
        return mylist
    
    def quick_sort(mylist):
        # 快排的思想是，在一个待排序的列表中，抽取一个作为轴
        # 然后小于轴的放在左边，大于轴的放在右边，然后左边和右边的递归调用快排
        # 这种算法基于分治的思想，但轴的选择的好坏会导致速度的差异，快排算法的效率并不稳定
        # 在python强大的列表下，快排可以写得很简单
        # 你没看错只需8行代码！
        length=len(mylist)
        if length<=1:
            return mylist
        pivot=mylist[length//2]#轴取中间，也可以取头尾
        left=[e for e in mylist if e<pivot]
        middle=[e for e in mylist if e==pivot]
        right=[e for e in mylist if e>pivot]
        return quick_sort(left)+middle+quick_sort(right)
    
    def bucket_sort(mylist,bucket_size=5):#默认平均每个桶的数据少于等于5个
        # 桶排序的思想是通过映射函数映射到一系列排序桶的中一个
        # 然后桶内部使用基于比较的排序方法
        # 最后按顺序output就完成排序了
        # 当然，如果数据分布平均的话，这个算法是O(n)级的
        length=len(mylist)
        if length ==0:
            return mylist
        # 先找列表中的最大和最小值，为了造桶和构造映射函数
        maxi=mini=mylist[0]
        for i in range(1,length):
            if mylist[i]<mini:
                mini=mylist[i]
            elif mylist[i]>maxi:
                maxi=mylist[i]
        # 桶的数量
        bucket_count=int((maxi-mini)/bucket_size)+1
        # 构造桶
        buckets=[]
        for i in range(bucket_count):
            buckets.append([])
        #映射到桶
        for i in range(length):
            buckets[int((mylist[i]-mini)/bucket_size)].append(mylist[i])
        #桶内部排序后输出
        sorted_list=[]
        for i in range(len(buckets)):
            buckets[i]=insertion_sort(buckets[i])#少量数据的话，用到插入排序也不错
            for j in range(len(buckets[i])):
                sorted_list.append(buckets[i][j])
        return sorted_list
    
    def shell_sort(mylist):
        # 希尔排序的是插入排序的改进版，容易知道插入排序在基本有序的数列中排序效率很高
        # 基于这个思想，希尔排序以半数减少增量分组进行插入排序
        # 最后进行全体的插入排序（即增量为1，此时已经基本有序）
        gap = len(mylist) // 2
        while gap > 0:
            for i in range(gap, len(mylist)):
                current_item = mylist[i]
                j = i
                while j >= gap and mylist[j - gap] > current_item:
                    mylist[j] = mylist[j - gap]
                    j -= gap
                mylist[j] = current_item
            gap //= 2
    
        return mylist
    
    
    
    def merge_sort(mylist):
        # 归并排序的思想是分治的，先分组，分到不可再分
        # 然后再归并，完成排序
        length=len(mylist)
        if length<=1:
            return mylist
        #分组
        mid=length//2
        left=merge_sort(mylist[:mid])
        right=merge_sort(mylist[mid:])
        #归并
        left_flag,right_flag=0,0
        sorted_list=[]
        while left_flag<len(left) and right_flag<len(right):
            if left[left_flag]<right[right_flag]:
                sorted_list.append(left[left_flag])
                left_flag+=1
            else:
                sorted_list.append(right[right_flag])
                right_flag+=1
        sorted_list+=left[left_flag:]
        sorted_list+=right[right_flag:]
        return sorted_list
    
    #测试
    data_num=10000
    sort_dict={
        0:selection_sort,
        1:bubble_sort,
        2:insertion_sort,
        3:bucket_sort,
        4:shell_sort,
        5:quick_sort,
        6:merge_sort
    }
    list1=list(range(data_num))
    random.shuffle(list1)
    for i in range(7):
        copy_list=list1.copy()
        start=time.time()
        sort_dict[i](copy_list)
        end=time.time()
        print(str((end-start)*1000)+'ms')
    #与python内置排序的形成对比
    copy_list=list1.copy()
    start=time.time()
    sorted(copy_list)
    end=time.time()
    print(str((end-start)*1000)+'ms')

输出：

16497.77340888977ms
    40010.46800613403ms
    14441.999197006226ms
    50.03523826599121ms
    223.65856170654297ms
    109.07816886901855ms
    198.81176948547363ms
    11.007070541381836ms

令我没想到的是，希尔排序能那么快。桶排序比快排快很自然。不过还是python内置的sorted()最快，这个没得说了，估计是c级别的速度了，内置具体用的是什么排序也不清楚。可能是快排？