利用python实现选择排序，冒泡排序_分别用选择排序和冒泡排序算法编写程序完成n(n由键盘输入)个不同随机数的降序排列

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

选择排序复杂度分析：
（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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输入元素的总个数：5
请输入第1个元素的取值: 1
请输入第2个元素的取值: 7
请输入第3个元素的取值: 8
请输入第4个元素的取值: 2
请输入第5个元素的取值: 3
['1', '7', '8', '2', '3']
从小到大输出结果为：
['1', '2', '3', '7', '8']
1
2
3
4
5
6
7
8
9

2.4 分析

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

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