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

Linux自动化运维——Python(12)(用Python实现冒泡排序和插入排序)

程序员文章站 2022-03-04 13:01:03
...

1.冒泡排序
过程: 
1. 从0位置开始,比较相邻两个数的大小,如果后面的数小于前面,则交换位置。 
2. 遍历一遍下来,最后一个数为整个数组中的最大值。 
3. 把最后一个数排除,继续比较剩下的数组。 
4. 总共比较次数为N*N,时间复杂度为O(n²)

代码实现

list=[3,5,6,32,5,6,2,35,65,22]
def bubble(list1):
    for i in range(len(list1)):
        for j in range(len(list1)-1-i):
            if list1[j+1]<list1[j]:
                list1[j],list1[j+1]=list1[j+1],list1[j]
    print(list1)
bubble(list)

2.插入排序

过程:

1.从1位置开始,比较与前面数的大小,如果小于前面的数,则交换位置,直到不再小于停止。
2.接着从2位置开始,重复这个过程。直到最后位置为止。
3.时间复杂度取决于数组的排序情况,当数组基本有序时候,复杂度很低,接近O(n)。当数组完全无序时,每个数都要经过多次移动,复杂度趋近于O(n²)。
代码实现:

def insert_sort(list):
    """插入排序"""
    n = len(list)
    for i in range(1, n):  # 未排序序列从第二个元素开始遍历
        for j in range(i, 0, -1):  # 已排序序列从后往前遍历
            if list[j] < list[j - 1]:  # 如果当前元素小于前一个元素, 则交换元素位置
                list[j], list[j - 1] = list[j - 1], list[j]
            else:  # 如果大于前一个元素, 则保持位置不变
                break

if __name__ == '__main__':
    list1 = [23,3,4,2,5,44,54,23,11]
    print("排序前:%s" % list1)
    insert_sort(list1)
    print("排序后:%s" % list1)

 

相关标签: 运维开发