python实现常见的排序算法

傷城~ 2023-06-04 06:53 15阅读 0赞

# python实现常见的排序算法 #

## 冒泡排序 ##

#冒泡排序
    def bubble_sort(li):
        for i in range(len(li) - 1):
            exchange = False
            for j in range(len(li) - i - 1):
                if li[j] > li[j+1]:  # > 号升序    <号降序
                    li[j],li[j+1] = li[j+1],li[j]  # 调换位置
                    exchange = True
            if not exchange:
                return

## 选择排序 ##

#选择排序
    def select_sort(li):
        for i in range(len(li)-1):  #一共需要遍历的次数，因为最后一个元素时，不需要排序，n-1次
            min_loc = i   #无序区第一个元素的位置，记做最小值
            for j in range(i+1,len(li)):  #从无序区第二个元素开始遍历到结尾
                if li[min_loc] > li[j]:#找到最小值得索引
                    min_loc = j
            li[i],li[min_loc] = li[min_loc],li[i]  #每次排序结束后，将无序区第一个元素与最小值得元素替换位置
            print(li)

## 插入排序 ##

#插入排序
    def insert_sort(li):
        for i in range(1,len(li)):  # 循环n-1次，而且无序区元素是从索引为1的元素开始，到结尾，依次插入有序区中
            tmp = li[i]  # 保存要插入的元素
            j = i -1 # j为有序区最后一个元素，和tmp进行比较
            while j >= 0 and tmp < li[j]: # 如果tmp比j元素小，则j向前移动一位
                li[j+1] = li[j]
                j -= 1
            li[j+1] = tmp # tmp比j元素大时，插入在j元素右边

## 快速排序 ##

def partition(li,left,right):
        tmp = li[left]  #获取最左边一个值，将其归位
        while left < right: #通过控制left和right
            #从最右边开始，向左找，找一个比tmp小的数，放在tmp的位置上
            while left < right and tmp <= li[right]: #当tmp比右边值大或等于，右边游标向左移动一位
                right -= 1
            li[left] = li[right]  #将右边比5小的数放入左边
            #从左边向右边找，找比tmp大的数，放入右边这个空里
            # print("左",li)
            while left < right and tmp >= li[left]:
                left += 1
            li[right] = li[left]
            # print("右",li)
        li[left] = tmp  #当左右游标重合时，就是中间位置，将该元素放入中间位置
        return left
    
    
    def re_quick_sort(li,left,right):  #用于递归
        if left < right:  #最少两个元素，一个元素不用排序
            mid = partition(li,left,right)  #将第一个元素归位到中间，获取其索引
            re_quick_sort(li,left,mid-1)  #排序左边
            re_quick_sort(li,mid+1,right) #排序右边

## 堆排序 ##

#堆排序
    #大根堆
    def sift(li,low,high):
        '''
    
        :param li:  传入需要调整的堆
        :param low:  堆顶，堆的根节点
        :param high:  堆底，堆中最后一个元素
        :return:
        '''
        i = low  # i指向领导位置，需要放入元素的位置
        j = 2 * i + 1  # j指向i的左孩子结点
        tmp = li[low]  # tmp指向需要调整元素的值
        while j <= high:  # j的元素索引不能超过元素的最后一个索引
            # 找左右孩子中最大的孩子的索引  j + 1为右孩子
            if j + 1 <= high and li[j+1] > li[j]:
                j += 1  # 如果右孩子比左孩子大，取右孩子结点
            if li[j] > tmp: # 把 j 指向的最大的孩子结点和 tmp需要调整的元素值进行比较，
                li[i] = li[j]
                # j元素进入领导层，将i指向j的空位上，j是i的孩子节点
                i = j
                j = 2 * i + 1
            else:
                li[i] = tmp  # 如果tmp需要调整的元素值更大，则将其放入i这个空位上，结束循环
                break
        else:
            li[i] = tmp  # 如果j比high大，代表i是叶子节点的空位，放入tmp调整元素
    
    #小根堆
    def sift_min(li,low,high):
        i = low        # 需要的替换位置
        j = i * 2 + 1  # 左节点
        tmp = li[low]
        while j <= high:
            #找左右子节点中最小的节点 的索引
            if j + 1 <= high and li[j+1] < li[j]:
                j += 1
            # 判断替换元素和子节点谁大
            if li[j] < tmp:  # 如果j索引坐上领导位，空位索引给i，j为i的子元素
                li[i] = li[j]
                i = j
                j = i * 2 + 1
            else:  # 位置找到了
                li[i] = tmp
                break
        else:  # j索引超过了i，i为叶子节点时候
            li[i] = tmp
    
    def heap_sort(li):    # 建堆
        n = len(li) - 1  # 获取最后一个元素索引
        for i in range((n - 1)//2,-1,-1):  # 最后一个非叶子节点 ( n - 1 )//2  从后向前找  从索引为（n - 1）//2的元素找到索引为0的元素
            sift_min(li,i,n)
        #每次从顶部取一个数，和底部最后一个元素交换，然后向下调整。每次底部减少一个数
        for i in range(n,-1,-1):    # 最后一个元素索引一直在变化，所以从后向前
            li[0],li[i] = li[i],li[0]
            sift_min(li,0,i-1)  #最上面的元素始终为0，最后一个元素为i-1,因为i的元素已经被拿出来了
        print(li)

## 归并排序 ##

#  归并排序
    def merge(li,low,mid,high):
        '''
        :param li:  两个有序列表组成的一个列表
        :param low:  列表最左端
        :param mid:  列表中间位置，左边最后一个元素的位置
        :param high: 列表最右边
        :return:
        '''
        i = low  # 左边游标
        j = mid + 1  # 右边游标
        tmpArr = []
        while i <= mid and j <= high:  # 两个游标都不能超过他们最后一个元素
            if li[i] < li[j]: # 左边比右边小，将左边元素放入临时数组中
                tmpArr.append(li[i])
                i += 1  # 将左边游标向后移动一位
            else:
                tmpArr.append(li[j])
                j += 1
        #将剩下的元素放入临时列表中
        while i <= mid:
            tmpArr.append(li[i])
            i += 1
        while j <= high:
            tmpArr.append(li[j])
            j += 1
        #将排好序的列表放入原列表中
        li[low:high+1] = tmpArr
    
    def merge_sort(li,low,high):
        if low < high: # 保证进入递归的条件：始终有两个元素   0 1 2 3
            mid = (low + high) // 2
            merge_sort(li,low,mid)    # 先将左右两边排序
            merge_sort(li,mid+1,high)
            merge(li,low,mid,high)   # 将左右两边排好序的列表归并

## 希尔排序 ##

#分组插入  每个分组间插入
    def insert_sort_gap(li,gap):
        for i in range(gap,len(li)): #初始位置都是从gap位置开始
            j = i - gap    # j取这个分组的最后一个元素
            tmp = li[i]    # 将这个值存储下来
            while j >= 0 and li[j] > tmp:  # j索引有效，且j当前指的元素比要插入的元素大
                li[j+gap] = li[j]   # j位置空下来，把j的值向右移动一个
                j -= gap    # j指向向左一个元素
            li[j+gap] = tmp
    #希尔排序
    def shell_sort(li):
        d = len(li)//2   #第一次分组，每组的大小为元素的一半
        while d >= 1:
            insert_sort_gap(li,d)  #分一次组排一次序
            d //= 2  # 每次分组，每组的元素个数都减少一半

## 计数排序 ##

#计数排序
    def count_sort(li,max_count=100):
        count = [0 for i in range(max_count+1)] #生成一个全0的列表，范围0-max_count
        # print(len(count))
        for val in li:
            count[val] += 1   # 遍历原列表，将每个数都统计到新列表中
        li.clear()  # 清除原来列表
        for index,val in enumerate(count):  # 获取新列表的索引（代表原列表中的数）和值（值代表这个数在原列表中的个数）
            for i in range(val):  # 将数写入原列表中
                li.append(index)

## 桶排序 ##

#桶排序
    def bucket_sort(li,n=100,max_num=10000):
        buckets = [[] for i in range(n)]  # 先创建n个数的桶
        # 遍历值，将每个数插入到桶中
        for val in li:
            i = min(val // (max_num//n),n - 1 ) # max_num/n代表每个桶中有多少个元素 i代表应该房放入哪个桶中 当超过最大桶的索引时，放入最大桶中
            buckets[i].append(val) # 将元素放入目标桶中
            # 给元素进行排序 用冒泡排序
            for j in range(len(buckets[i])-1,0,-1): # 从最后一个元素，一直遍历到第二个元素，j代表冒泡索引
                if buckets[i][j] < buckets[i][j-1]: # 没有找到位置，和前面的元素替换值
                    buckets[i][j],buckets[i][j-1] = buckets[i][j-1],buckets[i][j]
                else:  # 该元素找到位置后就退出
                    break
        # 将所有排序完的元素合并
        sorted_li = []
        for buc in buckets:
            sorted_li.extend(buc)
        return sorted_li

桶排序如果先将数据放入桶中，再使用快排，速度非常快

def buckets_sort2(li,n=100,max_val=10000): # n代表有n个桶，max_val为最大数字
        buckets = [[] for _ in range(n)]
        for val in li: # 将每个数字遍历出来
            i = min(val // (max_val // n),n-1)  #确定数字在哪个桶里面
            buckets[i].append(val)
    
        #给每个桶排序
        for bucket in buckets:
            _quick_sort(bucket)   #这是一个快排函数，见上面快速排序
    
        #将元素整合
        result_list = []
        for bucket in buckets:
            result_list.extend(bucket)
        return result_list

测试函数：

import time
    #用于统计函数时间的装饰器
    def calTime(func):
        def inner(*args,**kwargs):
            t1 = time.time()
            result = func(*args,**kwargs)
            t2 = time.time()
            print("%s running time:%.8s secs"%(func.__name__,t2-t1))
            return result
        return inner
    #将时间装饰器，装饰到函数上，在函数名上一行开头使用@calTime
    
    #用于产生随机数
    import random
    import copy
    SORT_NUM = 100000
    li = [random.randint(0,10000) for i in range(SORT_NUM)]
    list1 = copy.deepcopy(li)
    list2 = copy.deepcopy(li)
    list3 = copy.deepcopy(li)
    quick_sort(list1)
    buckets_sort(list2)
    buckets_sort2(list3)

`SORT_NUM`为1000个时，速度为  
quick\_sort running time:0.002979 secs  
buckets\_sort running time:0.001994 secs  
buckets\_sort2 running time:0.001007 secs

`SORT_NUM`为100000个时（十万），速度为  
quick\_sort running time:0.400920 secs  
buckets\_sort running time:14.30812 secs  
buckets\_sort2 running time:0.293269 secs

### 基数排序 ###

def radix_sort(li):
        max_num = max(li)
        it = 0
        while 10 ** it <= max_num:
            buckets = [[] for _ in range(10)]
            for val in li:
                digit = (val // 10 ** it) % 10 #从个位开始，十位，百位依次排序
                buckets[digit].append(val)
            li.clear()
            # 将每次排序完，将其依次放入数组中
            for buc in buckets:
                li.extend(buc)
            it += 1  #排完个位，排十位