用Python实现选择排序、冒泡排序,利用,python

发表时间:2021-05-11

1.选择排序

我们先来回顾一下什么是选择排序:
选择排序
我的代码(实现的是由大到小排序):

# 选择排序问题
n = int(input('输入元素的总个数:'))
number = []
for i in range(0, n):
    x1 = input('请输入第{}个元素的取值: '.format(i+1))
    number.append(x1)
print(number)
print('从大到小输出结果为:')
# 利用循环每次先找出一个最大值放到第一个位置,再从剩下的元素找出最大值,循环往复,内层循环实现的是寻找最大值,外层循环界定的是寻找最大值的次数,以及更新公用部分,比如flag,max1,number
for j in range(0, len(number)):
    # 最后一个元素直接输出
    if len(number) == 1:
        print(number[0])
    else:
        # 设置最大数值的标志
        flag = 0
        # 设置最大值
        max1 = 0
        for i in range(j, len(number)):
            if float(number[i]) >= float(max1):
                max1 = number[i]
                flag = i
        # 将最大值存放在第一个位置
        b = number[j]
        number[j] = number[flag]
        number[flag] = b
print(number)

选择排序复杂度分析:
(1)外层循环实现的是寻找最大数值的次数,假设列表内有n个元素,那么我们就要寻找n次最大值;
(2) 内层循环,实现的是寻找最大值,分别比较n,n-1,n-2次…
找最大值的复杂度为O(n),一共有n次,所以选择排序的复杂度为O(n²)。

2.冒泡排序

2.1 什么是冒泡排序?

冒泡排序
2.2 冒泡排序的算法步骤

冒泡排序
2.3 代码实现(实现从小到大排序)

# 冒泡排序问题
n = int(input('输入元素的总个数:'))
number = []
for i in range(0, n):
    x1 = input('请输入第{}个元素的取值: '.format(i+1))
    number.append(x1)
print(number)
print('从小到大输出结果为:')
# 内层循环实现的是交换两个元素的顺序,使得较大的元素处于后面;外层循环每进行一次,就有一个最大元素排列在最后
for j in range(0, n):
    # 外层循环进行完一次,最后末尾元素为最大的,只需要对其余元素进行排序即可,所以i的上限为n-j-1
    for i in range(0, n-j-1):
        if float(number[i]) >= float(number[i+1]):
            # 保留较大的数值
            b = number[i]
            number[i] = number[i+1]
            number[i+1] = b
print(number)
输入元素的总个数:5
请输入第1个元素的取值: 1
请输入第2个元素的取值: 7
请输入第3个元素的取值: 8
请输入第4个元素的取值: 2
请输入第5个元素的取值: 3
['1', '7', '8', '2', '3']
从小到大输出结果为:
['1', '2', '3', '7', '8']

2.4 分析

如果给出的列表元素它的数值大小本身就是由小到大排列,那么此时冒泡排序的复杂度就是最低的;但如果此时是从大到小排序,那么复杂度是非常高的,可以达到O(n²)。

在我的代码中,选择排序中是将最大元素放置在开端,开始的元素一定是最大的,所以下一次遍历,从 已经确定好最新的最大值 所在下标(假设最新确定好的最大元素所在下标为n)的下一个元素(下标为n+1)开始;而对于冒泡排序,我们最后的元素是确定的最大值,那我们就限制我们循环遍历的元素它的结束点是在哪一个下标,我们可以看出这个结束点下标是 已经确定好的最新的最大值元素 所在下标(假设当前确最新确定好的最大元素所在下标为m)的前一个元素所在的下标(m-1)。

文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号-4
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free