• 10大经典排序算法python实现
  • 1.冒泡排序
  • 2.选择排序
  • 3.插值排序
  • 4.希尔排序
  • 5.归并排序
  • 6.快排
  • 7.堆排序
  • 8.计数排序
  • 9.桶排序
  • 10.基数排序

10大经典排序算法python实现

1.冒泡排序

#算法思想:每次比较相邻的两个元素,较大的值放后面
#1,每次循环都有一个最大值被排好序了
#2,每次都是从头开始再一次比较,但是需要被比较的次数又少了一次

def bubble_sort(raw_list):
    length = len(raw_list)
    for i in range(length-1): 
        #这里首先要判断一共可能会循环几次,因为每次循环都有一个最大值被放到最后,所以最多循环n-1次就能排序完成
        print(f'第{i}次')
        for j in range(length-1-i):
            #因为循环了i次就排好了i个最大值,所以再循环时需要比较的次数就少了i,结果就是再需要比较n-1-i次
            if raw_list[j]>raw_list[j+1]:
                raw_list[j],raw_list[j + 1] = raw_list[j+1],raw_list[j] 
                #python的交叉赋值语法
                print(raw_list)
    return raw_list

算法排序过程
假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6]
"""
第0次
[3, 5, 7, 8, 4, 9, 0, 1, 2, 6]
[3, 5, 7, 4, 8, 9, 0, 1, 2, 6]
[3, 5, 7, 4, 8, 0, 9, 1, 2, 6]
[3, 5, 7, 4, 8, 0, 1, 9, 2, 6]
[3, 5, 7, 4, 8, 0, 1, 2, 9, 6]
[3, 5, 7, 4, 8, 0, 1, 2, 6, 9]
第1次
[3, 5, 4, 7, 8, 0, 1, 2, 6, 9]
[3, 5, 4, 7, 0, 8, 1, 2, 6, 9]
[3, 5, 4, 7, 0, 1, 8, 2, 6, 9]
[3, 5, 4, 7, 0, 1, 2, 8, 6, 9]
[3, 5, 4, 7, 0, 1, 2, 6, 8, 9]
第2次
[3, 4, 5, 7, 0, 1, 2, 6, 8, 9]
[3, 4, 5, 0, 7, 1, 2, 6, 8, 9]
[3, 4, 5, 0, 1, 7, 2, 6, 8, 9]
[3, 4, 5, 0, 1, 2, 7, 6, 8, 9]
[3, 4, 5, 0, 1, 2, 6, 7, 8, 9]
第3次
[3, 4, 0, 5, 1, 2, 6, 7, 8, 9]
[3, 4, 0, 1, 5, 2, 6, 7, 8, 9]
[3, 4, 0, 1, 2, 5, 6, 7, 8, 9]
第4次
[3, 0, 4, 1, 2, 5, 6, 7, 8, 9]
[3, 0, 1, 4, 2, 5, 6, 7, 8, 9]
[3, 0, 1, 2, 4, 5, 6, 7, 8, 9]
第5次
[0, 3, 1, 2, 4, 5, 6, 7, 8, 9]
[0, 1, 3, 2, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
第6次
第7次
第8次
"""

2.选择排序

#算法思想:每次遍历都找到一个最小的元素拿到前面
#1,从第一个元素开始和后面的元素比较,如果小就记录位置,然后拿这个记录位置的较小元素继续和后面的比较,如果更小的就记录这个更小的位置,一直到该轮循环结束
#2,一轮循环下来就会得到一个最小值得位置,拿这个最小值位置的值和循环开始的值交换

def selection_sort(raw_list):
    length = len(raw_list)
    for i in range(length-1):
        print(f'第{i}次')
        minindex = i
        for j in range(i+1,length):
            if raw_list[minindex] > raw_list[j]:
                minindex = j  #每次记录最小值的位置
        if i != minindex:
            raw_list[i],raw_list[minindex] = raw_list[minindex],raw_list[i]
            #一轮循环结束之后把最小值的位置和循环开始位置交换
            print(raw_list)
    return raw_list

算法排序过程
假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6]
"""
第0次
[0, 7, 5, 8, 4, 9, 3, 1, 2, 6]
第1次
[0, 1, 5, 8, 4, 9, 3, 7, 2, 6]
第2次
[0, 1, 2, 8, 4, 9, 3, 7, 5, 6]
第3次
[0, 1, 2, 3, 4, 9, 8, 7, 5, 6]
第4次
第5次
[0, 1, 2, 3, 4, 5, 8, 7, 9, 6]
第6次
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
第7次
第8次
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
"""

3.插值排序

#算法思想:假设我有一堆已经排序好的序列,现在又给我一个值,我只需要把这个值放到合适的位置就行了(这里和冒泡排序类似)
#现在我有一堆无序的数列,那么第一个值肯定是有序的(一个值就是有序的)
#然后拿第二个值放到第一个后面这时组成的序列就变的无序了,把刚拿到的值和第一个值排序,得到有序的序列
#再拿第三个值和前两个值放一起,然后再把第三个值和前两个值排序,以此类推

def insert_sort(raw_list):
    length = len(raw_list)
    for i in range(1,length):
        print(f'第{i}次')
        for j in range(i,0,-1):
            if raw_list[j]<raw_list[j-1]:
                raw_list[j], raw_list[j-1] = raw_list[j-1], raw_list[j]
                print(raw_list)
            else:#这里如果添加的这个值比最大的值还大,就没必要继续忘下比较了
                continue

算法排序过程
假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6]
"""
第1次
第2次
[3, 5, 7, 8, 4, 9, 0, 1, 2, 6]
第3次
第4次
[3, 5, 7, 4, 8, 9, 0, 1, 2, 6]
[3, 5, 4, 7, 8, 9, 0, 1, 2, 6]
[3, 4, 5, 7, 8, 9, 0, 1, 2, 6]
第5次
第6次
[3, 4, 5, 7, 8, 0, 9, 1, 2, 6]
[3, 4, 5, 7, 0, 8, 9, 1, 2, 6]
[3, 4, 5, 0, 7, 8, 9, 1, 2, 6]
[3, 4, 0, 5, 7, 8, 9, 1, 2, 6]
[3, 0, 4, 5, 7, 8, 9, 1, 2, 6]
[0, 3, 4, 5, 7, 8, 9, 1, 2, 6]
第7次
[0, 3, 4, 5, 7, 8, 1, 9, 2, 6]
[0, 3, 4, 5, 7, 1, 8, 9, 2, 6]
[0, 3, 4, 5, 1, 7, 8, 9, 2, 6]
[0, 3, 4, 1, 5, 7, 8, 9, 2, 6]
[0, 3, 1, 4, 5, 7, 8, 9, 2, 6]
[0, 1, 3, 4, 5, 7, 8, 9, 2, 6]
第8次
[0, 1, 3, 4, 5, 7, 8, 2, 9, 6]
[0, 1, 3, 4, 5, 7, 2, 8, 9, 6]
[0, 1, 3, 4, 5, 2, 7, 8, 9, 6]
[0, 1, 3, 4, 2, 5, 7, 8, 9, 6]
[0, 1, 3, 2, 4, 5, 7, 8, 9, 6]
[0, 1, 2, 3, 4, 5, 7, 8, 9, 6]
第9次
[0, 1, 2, 3, 4, 5, 7, 8, 6, 9]
[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

"""

4.希尔排序

#为什么会有希尔排序:插值排序对比较有序的数组排序时效率会高很多
#算法思想:先将整个数据分成多组,然后对组内数据进行插值排序,循环前面的步骤,
#注意:每次分组,组内元素越来越多(也就是说组数越来越少),直到把所有数据都分成一组,这样所有的数据基本就有序了然后再进行插值排序

def shell_sort(row_list):
    length = len(row_list)
    group = length//2  #先把两个数据分到一组,下次把4个数据分到一组,下次8个,32个....
    count=1
    while group>0: #组会越来越小直到group为1时结束
        print(f'分组个数:{group}')
        print(f'第{count}次')
        for i in range(0,group): #要把每一组的都跑一遍
            j=i
            while j<length-group: 
                #每一组里面可能有多个元素,元素之间的索引位置相差一个group,这里要对这一组元素进行差值排序,防止索引越界的问题
                if row_list[j]>row_list[j+group]:
                    row_list[j], row_list[j + group] = row_list[j + group], row_list[j]
                    print(row_list)
                j += group #元素之间的索引位置相差一个group
        group = group//2 #下次把4个数据分到一组,下次8个,32个....
        count+=1

算法排序过程
假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6]
"""
分组个数:5
第1次
[3, 0, 5, 8, 4, 9, 7, 1, 2, 6]
[3, 0, 1, 8, 4, 9, 7, 5, 2, 6]
[3, 0, 1, 2, 4, 9, 7, 5, 8, 6]
分组个数:2
第2次
[1, 0, 3, 2, 4, 9, 7, 5, 8, 6]
[1, 0, 3, 2, 4, 5, 7, 9, 8, 6]
[1, 0, 3, 2, 4, 5, 7, 6, 8, 9]
分组个数:1
第3次
[0, 1, 3, 2, 4, 5, 7, 6, 8, 9]
[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

"""

5.归并排序

#归并排序利用了分而治的思想:递的时候分(拆分),归的时候治(排序+并),注意与快排的区别

def merge(l1,l2):
    """
    排序逻辑,递归归来的时候调用改方法
    """
    res_list = []
    print(f'归-待治:{l1},{l2}')
    #两个有序的列表怎么才能合成一个有序的列表呢?
    while l1 and l2:
        if l1[0] <= l2[0]:
            res_list.append(l1.pop(0))
        else:
            res_list.append(l2.pop(0))
    while l1:
        res_list.append(l1.pop(0))
    while l2:
        res_list.append(l2.pop(0))
    print(f'归-已治:{res_list}')
    return res_list

def merge_sort(row_list):
    #第一步:分,每次把数据分成两份直到不能再分为止
    length = len(row_list)
    if len(row_list)<2:
        return row_list

    mid = length // 2
    ll = row_list[:mid]
    lr = row_list[mid:]
    print(f'递:左{ll},右{lr}')
    # 第二步:治,每往回退一层就 合并+排序 一次
    return merge(merge_sort(ll),merge_sort(lr))
    #归并排序的精髓在这里,
    # 1.在归的时候再排序,由于递的时候都是把元素分为单个值.单个值就是有序的,
    # 2.所以归的时候的任务就是把两个有序的列表合并为一个列表

算法排序过程
假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6,10]
"""
递:左[3, 7, 5, 8, 4],右[9, 0, 1, 2, 6, 10]
递:左[3, 7],右[5, 8, 4]
递:左[3],右[7]
归-待治:[3],[7]
归-已治:[3, 7]
递:左[5],右[8, 4]
递:左[8],右[4]
归-待治:[8],[4]
归-已治:[4, 8]
归-待治:[5],[4, 8]
归-已治:[4, 5, 8]
归-待治:[3, 7],[4, 5, 8]
归-已治:[3, 4, 5, 7, 8]
递:左[9, 0, 1],右[2, 6, 10]
递:左[9],右[0, 1]
递:左[0],右[1]
归-待治:[0],[1]
归-已治:[0, 1]
归-待治:[9],[0, 1]
归-已治:[0, 1, 9]
递:左[2],右[6, 10]
递:左[6],右[10]
归-待治:[6],[10]
归-已治:[6, 10]
归-待治:[2],[6, 10]
归-已治:[2, 6, 10]
归-待治:[0, 1, 9],[2, 6, 10]
归-已治:[0, 1, 2, 6, 9, 10]
归-待治:[3, 4, 5, 7, 8],[0, 1, 2, 6, 9, 10]
归-已治:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
"""

6.快排

#快排也利用了分而治的思想:递的时候又分又治(拆分+排序),归的时候合并就行了

def merger(left,m,right):
    return quick_sort(left)+m+quick_sort(right)

def quick_sort(row_list):
    if len(row_list)<=1:
        return row_list
    length = len(row_list)
    mid = length//2
    right = [i for i in row_list if i>row_list[mid]]
    left = [i for i in row_list if i<row_list[mid]]
    m = [i for i in row_list if i==row_list[mid]]
    print(f'递:左{left}:,中{m}:,右{right}')
    return merger(left,m,right)
    #左和右都是已经排好序的列表,归的时候只需要合并就行了

7.堆排序

#利用堆的性质排序,其实这里用的堆是一颗完全二叉树(如果某个节点的子节点不满2个就不会有下一层,不足一层的子节点依左边对齐)
#如何把列表看成对呢:其实堆的编号是2^0,2^1,2^2...依次增加的,把列表的索引看成是堆的编号,列表就成了堆

def max_heap(row_list,n,maxid):
    i = maxid #节点自己的编号

    l = 2*maxid+1 #左子节点编号
    r = l+1 #右子节点编号
    if l<n and row_list[l]>row_list[maxid]:
        maxid = l
    if r<n and row_list[r]>row_list[maxid]:
        maxid = r
    if maxid != i:
        row_list[i],row_list[maxid] = row_list[maxid],row_list[i]
        print(maxid)
        print(row_list)
        #这里一旦调整了节点那么要递归的把改动的节点都要再比较一遍
        max_heap(row_list,n,maxid)

def heap_sort(row_list):
    n = len(row_list)
    #1创建大根堆
    for i in range(n-1,-1,-1):#这里的i开始其实可是设置成n//2,因为n>n//2时节点是没有子节点的
        max_heap(row_list,n,i)
    #2对调首位位置继续创建大根堆
    for i in range(n-1,-1,-1):
        row_list[0],row_list[i] = row_list[i],row_list[0]
        print(f'剩下的元素对调首尾:{row_list}')
        max_heap(row_list, i, 0) #这里每次循环列表末尾的元素都是已经排序好的,都不计算在内

    return row_list

算法排序过程
假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6,10]
"""
10
[3, 7, 5, 8, 10, 9, 0, 1, 2, 6, 4]
5
[3, 7, 9, 8, 10, 5, 0, 1, 2, 6, 4]
4
[3, 10, 9, 8, 7, 5, 0, 1, 2, 6, 4]
1
[10, 3, 9, 8, 7, 5, 0, 1, 2, 6, 4]
3
[10, 8, 9, 3, 7, 5, 0, 1, 2, 6, 4]
剩下的元素对调首尾:[4, 8, 9, 3, 7, 5, 0, 1, 2, 6, 10]
2
[9, 8, 4, 3, 7, 5, 0, 1, 2, 6, 10]
5
[9, 8, 5, 3, 7, 4, 0, 1, 2, 6, 10]
剩下的元素对调首尾:[6, 8, 5, 3, 7, 4, 0, 1, 2, 9, 10]
1
[8, 6, 5, 3, 7, 4, 0, 1, 2, 9, 10]
4
[8, 7, 5, 3, 6, 4, 0, 1, 2, 9, 10]
剩下的元素对调首尾:[2, 7, 5, 3, 6, 4, 0, 1, 8, 9, 10]
1
[7, 2, 5, 3, 6, 4, 0, 1, 8, 9, 10]
4
[7, 6, 5, 3, 2, 4, 0, 1, 8, 9, 10]
剩下的元素对调首尾:[1, 6, 5, 3, 2, 4, 0, 7, 8, 9, 10]
1
[6, 1, 5, 3, 2, 4, 0, 7, 8, 9, 10]
3
[6, 3, 5, 1, 2, 4, 0, 7, 8, 9, 10]
剩下的元素对调首尾:[0, 3, 5, 1, 2, 4, 6, 7, 8, 9, 10]
2
[5, 3, 0, 1, 2, 4, 6, 7, 8, 9, 10]
5
[5, 3, 4, 1, 2, 0, 6, 7, 8, 9, 10]
剩下的元素对调首尾:[0, 3, 4, 1, 2, 5, 6, 7, 8, 9, 10]
2
[4, 3, 0, 1, 2, 5, 6, 7, 8, 9, 10]
剩下的元素对调首尾:[2, 3, 0, 1, 4, 5, 6, 7, 8, 9, 10]
1
[3, 2, 0, 1, 4, 5, 6, 7, 8, 9, 10]
剩下的元素对调首尾:[1, 2, 0, 3, 4, 5, 6, 7, 8, 9, 10]
1
[2, 1, 0, 3, 4, 5, 6, 7, 8, 9, 10]
剩下的元素对调首尾:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
1
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10]
剩下的元素对调首尾:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
剩下的元素对调首尾:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

"""

8.计数排序

#计数排序有使用条件限制,值不为小数,且知道最大值最小值,这里假设最小值为0
#生产最大值和最小值整数区间,循环列表的元素把对应的整数计数加一,元素循环一遍之后把计数区间按计数个数展开

def count_sort(row_list):
    max_value = max(row_list)
    dic = {i:0 for i in range(0,max_value+1)}
    for num in row_list:
        dic[num]+=1
    res_list = []
    print(dic)
    for key in dic:
        temp_list = dic[key]*[key]
        res_list.extend(temp_list)
    return res_list

9.桶排序

# 计数排序的升级版,知道最大值最小值,这里假设最小值为0

def bucket_sort(row_list):
    max_value = max(row_list)
    #1确定桶的大小,可以用(最大值-最小值)/元素个数,我们用于演示,这里随便定一个值4,那么桶的个数就是最大值//3+1
    size = 4
    bucket = max_value//size
    #桶的个数一单确定那么每个桶的区间就确定了
    bucket_list = [[] for i in range(bucket+1)]
    #2把元素放到对应的桶中
    for num in row_list:
        bucket_id = num//size  #用元素值除以桶的大小来确定该元素该放到那个桶
        bucket_list[bucket_id].append(num)
        print(bucket_list)
    #3桶内排序,随便使用一种排序算法,这里直接调用python自带的排序函数
    res_list = []
    for bucket in bucket_list:
        bucket.sort()
        # 4把桶内的数据展开
        res_list.extend(bucket)

    return res_list

算法排序过程
假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6,10]
"""
[[3], [], []]
[[3], [7], []]
[[3], [7, 5], []]
[[3], [7, 5], [8]]
[[3], [7, 5, 4], [8]]
[[3], [7, 5, 4], [8, 9]]
[[3, 0], [7, 5, 4], [8, 9]]
[[3, 0, 1], [7, 5, 4], [8, 9]]
[[3, 0, 1, 2], [7, 5, 4], [8, 9]]
[[3, 0, 1, 2], [7, 5, 4, 6], [8, 9]]
[[3, 0, 1, 2], [7, 5, 4, 6], [8, 9, 10]]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
"""

10.基数排序

#和桶排序类似,这里桶的个数固定10个,
#最大值有几位就循环几次,第i次就除以10**i,对10取余放入对应的桶桶中,合并第i次排序的结果进入下一次循环

def radix_sort(row_list):
    max_value = max(row_list)
    n = len(str(max_value))
    for i in range(n):
        print(f'第{i+1}次')
        bucket = 10
        bucket_list = [[] for i in range(bucket)]
        for value in row_list:
            bucket_id = (value//10**i)%10
            bucket_list[bucket_id].append(value)
        print(bucket_list)
        row_list = [i for _list in bucket_list for i in _list] #将桶内的数据按循序展开
        print(row_list)
        # row_list = []
        # for _list in bucket_list:
        #     row_list.extend(_list)
    return row_list

算法排序过程
假设待排序的序列为list0 = [3, 7, 5, 8, 4, 9, 0, 1, 2, 6,10]
"""
第1次
[[0, 10], [1], [2], [3], [4], [5], [6], [7], [8], [9]]
[0, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
第2次
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [10], [], [], [], [], [], [], [], []]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
"""