python实现十大排序算法（详解）

之前在这C语言实现八大排序算法（一）和C语言实现八大排序算法（二）2篇文章中，已经详细介绍了各种排序算法的思想，参考资料主要是用C语言实现的。本文主要用python语言再次实现十大排序算法。

十大排序算法的复杂度及稳定性分析如下表所示：

插入排序

代码

''' 1. 从第一个元素开始，该元素可以认为已经被排序 2.取出下一个元素，在已经排序的元素序列中从后向前扫描 3.如果该元素（已排序）大于新元素，将该元素移到下一位置 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5.将新元素插入到该位置中 6.重复步骤2 '''
def insert_sort(list):
    for i in range(1,len(list)):
        print("第{}轮：".format(i))
        key=list[i]
        j=i-1
        while j>=0:
            if list[j]>key:
                list[j+1]=list[j]
                list[j]=key
            j-=1
        print(list)
    return list

a=[2,4,3,8,1,5,7,6]
result=insert_sort(a)
#print(result)

结果

第1轮：
[2, 4, 3, 8, 1, 5, 7, 6]
第2轮：
[2, 3, 4, 8, 1, 5, 7, 6]
第3轮：
[2, 3, 4, 8, 1, 5, 7, 6]
第4轮：
[1, 2, 3, 4, 8, 5, 7, 6]
第5轮：
[1, 2, 3, 4, 5, 8, 7, 6]
第6轮：
[1, 2, 3, 4, 5, 7, 8, 6]
第7轮：
[1, 2, 3, 4, 5, 6, 7, 8]

希尔排序

代码

''' 1.希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序； 2.随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。 '''
def shell_sort(list):
    # 设定步长
    step = int(len(list)/2)
    while step > 0:
        print(step)
        for i in range(step, len(list)):
            # 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置
            while i >= step and list[i-step] > list[i]:
                list[i], list[i-step] = list[i-step], list[i]
                i -= step
        step = int(step/2)
        print(list)
    return list

a=[2,4,3,8,1,5,7,6]
result=shell_sort(a)
#print(result)

结果

4
[1, 4, 3, 6, 2, 5, 7, 8]
2
[1, 4, 2, 5, 3, 6, 7, 8]
1
[1, 2, 3, 4, 5, 6, 7, 8]

冒泡排序

代码

''' 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3.针对所有的元素重复以上的步骤，除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 '''
def bubble_sort(list):
    global flag
    for i in range(len(list)-1):
        print("第{}轮：".format(i))
        flag=False                         #本次冒泡是否发生交换的标志
        for j in range(len(list)-i-1):
            if list[j]>list[j+1]:
                list[j],list[j+1]=list[j+1],list[j]
                flag=True
        print(list)
        if flag==False:                    #未交换，数组已经有序，无须冒泡
            return

a=[2,4,3,8,1,5,7,6]
result=bubble_sort(a)

结果

第0轮：
[2, 3, 4, 1, 5, 7, 6, 8]
第1轮：
[2, 3, 1, 4, 5, 6, 7, 8]
第2轮：
[2, 1, 3, 4, 5, 6, 7, 8]
第3轮：
[1, 2, 3, 4, 5, 6, 7, 8]
第4轮：
[1, 2, 3, 4, 5, 6, 7, 8]

快速排序

代码

''' 1.从数列中挑出一个元素，称为 “基准”（pivot）； 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）； 3.对所有两个小数列重复第二步，直至各区间只有一个数。 '''
def quicksort(list,start,end):
    if start>=end:
        return
    low=start
    high=end
    base=list[start]
    while low<high:
        while low<high and list[high]>=base:  #从后向前找第一个小于基准值的数
            high-=1
        if low<high:
            list[low]=list[high]
            low+=1
        while low<high and list[low]<base:    #从前向后找第一个大于基准值的数
            low+=1
        if low<high:
            list[high]=list[low]
            high-=1
    list[low]=base                           #填坑

    quicksort(list,start,low-1)              #递归排序
    quicksort(list,low+1,end)

a=[2,4,3,8,1,5,7,6]
quicksort(a,0,len(a)-1)
print(a)

结果

[1, 2, 3, 4, 5, 6, 7, 8]

选择排序

代码

''' 选择排序的基本思想：比较 + 交换。 第一趟，在待排序记录r1 到 r[n]中选出最小的记录，将它与r1交换； 第二趟，在待排序记录r2 到 r[n]中选出最小的记录，将它与r2交换； 以此类推，第 i 趟，在待排序记录ri 到 r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕。 '''
def select_sort(list):
    for i in range(0,len(list)):
        print("第{}轮：".format(i))
        min=i
        for j in range(i+1,len(list)):
            if list[min]>list[j]:
                min=j
        list[min],list[i]=list[i],list[min]          #每轮找出最小的交换
        print(list)
    return list

a=[2,4,3,8,1,5,7,6]
result=select_sort(a)
#print(result)

结果

第0轮：
[1, 4, 3, 8, 2, 5, 7, 6]
第1轮：
[1, 2, 3, 8, 4, 5, 7, 6]
第2轮：
[1, 2, 3, 8, 4, 5, 7, 6]
第3轮：
[1, 2, 3, 4, 8, 5, 7, 6]
第4轮：
[1, 2, 3, 4, 5, 8, 7, 6]
第5轮：
[1, 2, 3, 4, 5, 6, 7, 8]
第6轮：
[1, 2, 3, 4, 5, 6, 7, 8]
第7轮：
[1, 2, 3, 4, 5, 6, 7, 8]

堆排序

代码

''' 大根堆：每个节点的值都大于或等于其子节点的值，用于升序排列； 小根堆：每个节点的值都小于或等于其子节点的值，用于降序排列。 以大根堆为例，每次将最大元素放置在堆顶 '''
def adjust_heap(lists, i, size):                      #向下调整大根堆
    ''' :param lists: 数组元素 :param i: 当前结点 :param size: 数组长度 '''
    # 非叶子结点的左右两个孩子
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    # 在当前结点、左孩子、右孩子中找到最大元素的索引
    max = i
    if i < size // 2:
        if lchild < size and lists[lchild] > lists[max]:
            max = lchild
        if rchild < size and lists[rchild] > lists[max]:
            max = rchild
        # 如果最大元素的索引不是当前结点，把大的结点交换到上面，继续调整堆
        if max != i:
            # 第 2 个参数传入 max 的索引是交换前大数字对应的索引
            # 交换后该索引对应的是小数字，应该把该小数字向下调整
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)

def build_heap(lists, size):                    #建立大根堆
    for i in range(0, (size//2))[::-1]:         # 从倒数第一个非叶子结点开始建立大根堆
        adjust_heap(lists, i, size)             # 对所有非叶子结点进行堆的调整

def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    for i in range(0, size)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]     # 每次根结点都是最大的数，最大数放到后面
        adjust_heap(lists, 0, i)       # 交换完后还需要继续调整堆，只需调整根节点，此时数组的 size 不包括已经排序好的数
        print("第{}轮：".format(size-i))
        print(lists)                     # 由于每次大的都会放到后面，因此最后的 lists 是从小到大排列

a=[2,4,3,8,1,5,7,6]
result=heap_sort(a)

结果

第1轮：
[7, 6, 5, 4, 1, 2, 3, 8]
第2轮：
[6, 4, 5, 3, 1, 2, 7, 8]
第3轮：
[5, 4, 2, 3, 1, 6, 7, 8]
第4轮：
[4, 3, 2, 1, 5, 6, 7, 8]
第5轮：
[3, 1, 2, 4, 5, 6, 7, 8]
第6轮：
[2, 1, 3, 4, 5, 6, 7, 8]
第7轮：
[1, 2, 3, 4, 5, 6, 7, 8]
第8轮：
[1, 2, 3, 4, 5, 6, 7, 8]

归并排序

代码

''' 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列； 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置； 4.重复步骤③直到某一指针达到序列尾； 5.将另一序列剩下的所有元素直接复制到合并序列尾。 '''
def merge(left_list,right_list):
    left_index=0
    right_index=0
    merge_list=[]
    while left_index<len(left_list) and right_index<len(right_list):
        if left_list[left_index]<right_list[right_index]:   #哪一部分小，就添加到合并的列表中
            merge_list.append(left_list[left_index])
            left_index+=1
        else:
            merge_list.append(right_list[right_index])
            right_index+=1
    merge_list+=left_list[left_index:]                   #将剩余的部分添加到合并列表中
    merge_list+=right_list[right_index:]
    return merge_list

def merge_sort(list):
    if len(list)<=1:
        return list
    mid_index=len(list)//2            #拆分数组为两部分
    left_list=merge_sort(list[:mid_index])
    right_list=merge_sort(list[mid_index:])
    return merge(left_list,right_list)

a=[2,4,3,8,1,5,7,6]
result=merge_sort(a)
print(result)

结果

[1, 2, 3, 4, 5, 6, 7, 8]

基数排序

代码

''' 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。 然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。 '''
def radix_sort(list):
    i = 0 # 记录当前正在排拿一位，最低位为1
    max_num = max(list)  # 最大值
    j = len(str(max_num))  # 记录最大值的位数
    while i < j:
        bucket_list =[[] for _ in range(10)] #初始化桶数组
        for x in list:
            bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组
        print("第{}轮：".format(i+1))
        print(bucket_list)
        list.clear()
        for x in bucket_list:   # 放回原序列
            for y in x:
                list.append(y)
        print(list)
        i += 1
    return list


a = [334,5,67,345,7,5345,99,4,23,78,45,1,453,3424]
result=radix_sort(a)
# print(result)

结果

第1轮：
[[], [1], [], [23, 453], [334, 4, 3424], [5, 345, 5345, 45], [], [67, 7], [78], [99]]
[1, 23, 453, 334, 4, 3424, 5, 345, 5345, 45, 67, 7, 78, 99]
第2轮：
[[1, 4, 5, 7], [], [23, 3424], [334], [345, 5345, 45], [453], [67], [78], [], [99]]
[1, 4, 5, 7, 23, 3424, 334, 345, 5345, 45, 453, 67, 78, 99]
第3轮：
[[1, 4, 5, 7, 23, 45, 67, 78, 99], [], [], [334, 345, 5345], [3424, 453], [], [], [], [], []]
[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 5345, 3424, 453]
第4轮：
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 453], [], [], [3424], [], [5345], [], [], [], []]
[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 453, 3424, 5345]

计数排序

代码

''' 1.找到给定序列的最小值与最大值 2.创建一个长度为最大值-最小值+1的数组，初始化都为0 然后遍历原序列，记录每个数据出现的次数 此时数组中已经记录好每个值的数量，自然也就是有序的了 '''
def count_sort(list):
    # 找到最大最小值
    min_num = min(list)
    max_num = max(list)
    # 计数列表，即桶的个数
    count_list = [0]*(max_num-min_num+1)
    print(count_list)
    # 将元素值作为键值存储在桶中，记录其出现的次数
    for i in list:
        count_list[i-min_num] += 1   #最小值作为一个偏移量存在，因为数据可能存在负数的
    print(count_list)
    list.clear()
    # 填回
    for ind,i in enumerate(count_list):  #ind为索引，i为数据
        while i != 0:
            list.append(ind+min_num)     #数据的真实值
            i -= 1                       #该数据出现的次数
    return list

a = [34,5,7,34,9,5,23,12,1]
result=count_sort(a)
print(result)

结果

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2]
[1, 5, 5, 7, 9, 12, 23, 34, 34]

桶排序

代码

''' 桶排序与计数排序类似，但可以解决非整数的排序 1.桶排序相当于把计数数组划分为按顺序的几个部分 2.每一部分叫做一个桶，它来存放处于该范围内的数 3.然后再对每个桶内部进行排序，可以使用其他排序方法如快速排序 4.最后整个桶数组就是排列好的数据，再将其返回给原序列 '''
def bucket_sort(list):

    min_num = min(list)
    max_num = max(list)
    # 桶的大小
    bucket_range = (max_num-min_num) / len(list)
    # 桶数组
    count_list = [ [] for i in range(len(list) + 1)]
    print(count_list)
    # 向桶数组填数
    for i in list:
        count_list[int((i-min_num)//bucket_range)].append(i)
    print(count_list)
    list.clear()
    # 回填，这里桶内部排序直接调用了sorted
    for i in count_list:
        for j in sorted(i):
            list.append(j)
        print(list)
    return list

a = [37,5,7.8,37,9,5,23,12,1]
result=bucket_sort(a)
#print(result)

结果

[[], [], [], [], [], [], [], [], [], []]
[[1], [5, 7.8, 5], [9, 12], [], [], [23], [], [], [], [37, 37]]
[1]
[1, 5, 5, 7.8]
[1, 5, 5, 7.8, 9, 12]
[1, 5, 5, 7.8, 9, 12]
[1, 5, 5, 7.8, 9, 12]
[1, 5, 5, 7.8, 9, 12, 23]
[1, 5, 5, 7.8, 9, 12, 23]
[1, 5, 5, 7.8, 9, 12, 23]
[1, 5, 5, 7.8, 9, 12, 23]
[1, 5, 5, 7.8, 9, 12, 23, 37, 37]