欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

十大排序、七大查找算法python实现——冒泡排序(bubble sort)

程序员文章站 2022-06-04 08:23:26
...

一、十大排序算法

 

详细原理参考地址:https://www.cnblogs.com/onepixel/articles/7674659.html

数据准备

使用random库随机生成无序数组

import random
def random_list(start, end, number):
    temp = []
    i = 0
    while i < number:
        temp.append(random.randint(start,end))
        i += 1
    return temp

 

1.冒泡排序(bubble sort)

根据冒泡算法的排序原理可知,每次比较相邻的两个元素,根据元素的数值大小进行交换位置。具体步骤如下:

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  • 针对所有的元素重复以上的步骤,除了最后一个;
  • 重复步骤1~3,直到排序完成。
#冒泡排序
def bubble_sort(L):
    n = len(L)
    for j in range(n-1): # 比较n-1次
        for i in range(n-1): # 循环比较数组中两个相邻元素
            if L[i] > L[i+1]:  # 交换位置
                a = L[i]
                L[i] = L[i+1]
                L[i+1] = a
        print("第{}步排序结果:{}".format(j, L))
    return L

执行上述代码,结果如下,我们会发现每轮排序后,总会将前面出现的最大的数移到数组的后面,使得数组从后面开始逐渐有序化。但是我们的代码在第二次循环开始一直是比较整个数组,忽略了已经有序的数组段。

十大排序、七大查找算法python实现——冒泡排序(bubble sort)

为此,我们优化一下代码,如下:

def bubble_sort_1(L):
    n = len(L)
    for i in range(n-1):
        for j in range(n-1-i):  #  注意这里
            if L[j] > L[j+1]:
                L[j], L[j+1] = L[j+1], L[j]
        print(L)
    return L

执行结果如下,这样每循环一次都可以缩小一次排序的范围,可以大大提高算法的运行效率,其实这也是冒泡算法的正确做法。

十大排序、七大查找算法python实现——冒泡排序(bubble sort)