Python实现冒泡排序和选择排序

发表于 更新于 分类于 Waline： 本文字数： 2.1k 阅读时长 ≈ 4 分钟

Every obstacle is an opportunity. ——《快乐的大脚》

每一次挫折都是一次机会。

冒泡排序

原理

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def bubble_sort(nums_list):
    flag = 0    # 是否交换的标志
    for j in range(len(nums_list) - 1):    # 这个循环负责设置冒泡排序进行的次数
        for i in range(len(nums_list) - j - 1):    # i为列表下标
            if nums_list[i] > nums_list[i + 1]:
                nums_list[i], nums_list[i + 1] = nums_list[i + 1], nums_list[i]
                flag += 1
                print(f"目前交换{flag}次了, 列表现在是：{nums_list}")
    if flag == 0:
        print('这个列表原本就是有序列表，不需要排序了！')
    else:
        print(f'这个列表共交换了{flag}次。')
    return nums_list



print(bubble_sort([66, 19, 21, 14, 13, 21, 88]))
print()
print(bubble_sort([1, 2, 3]))

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
目前交换1次了, 列表现在是：[19, 66, 21, 14, 13, 21, 88]
目前交换2次了, 列表现在是：[19, 21, 66, 14, 13, 21, 88]
目前交换3次了, 列表现在是：[19, 21, 14, 66, 13, 21, 88]
目前交换4次了, 列表现在是：[19, 21, 14, 13, 66, 21, 88]
目前交换5次了, 列表现在是：[19, 21, 14, 13, 21, 66, 88]
目前交换6次了, 列表现在是：[19, 14, 21, 13, 21, 66, 88]
目前交换7次了, 列表现在是：[19, 14, 13, 21, 21, 66, 88]
目前交换8次了, 列表现在是：[14, 19, 13, 21, 21, 66, 88]
目前交换9次了, 列表现在是：[14, 13, 19, 21, 21, 66, 88]
目前交换10次了, 列表现在是：[13, 14, 19, 21, 21, 66, 88]
这个列表共交换了10次。
[13, 14, 19, 21, 21, 66, 88]

这个列表原本就是有序列表，不需要排序了！
[1, 2, 3]

选择排序

原理

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def selection_sort(nums_list):
    flag = 0  # 是否交换的标志
    for i in range(0, len(nums_list)-1):
        min_index = i    # 将本次循环第一个位置值的下标设为i
        for j in range(i + 1, len(nums_list)):    # 和当前i元素之后的所有值进行比较
            if nums_list[j] < nums_list[min_index]:
                min_index = j    # 使min_index为本次循环最小值下标
        nums_list[i], nums_list[min_index] = nums_list[min_index], nums_list[i]
        flag += 1
        print(f"目前交换{flag}次了, 列表现在是：{nums_list}")
    if flag == 0:
        print('这个列表原本就是有序列表，不需要排序了！')
    else:
        print(f'这个列表共交换了{flag}次。')
    return nums_list


print(selection_sort([66, 19, 21, 14, 13, 21, 88]))
print()
print(bubble_sort([1, 2, 3]))

输出结果：

1
2
3
4
5
6
7
8
目前交换1次了, 列表现在是：[13, 19, 21, 14, 66, 21, 88]
目前交换2次了, 列表现在是：[13, 14, 21, 19, 66, 21, 88]
目前交换3次了, 列表现在是：[13, 14, 19, 21, 66, 21, 88]
目前交换4次了, 列表现在是：[13, 14, 19, 21, 66, 21, 88]
目前交换5次了, 列表现在是：[13, 14, 19, 21, 21, 66, 88]
目前交换6次了, 列表现在是：[13, 14, 19, 21, 21, 66, 88]
这个列表共交换了6次。
[13, 14, 19, 21, 21, 66, 88]