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  #排完个位，排十位