发布于 

排序算法备忘录（一）

排序算法时算法中很基础的内容。之前只是会简单的冒泡排序，后来用了 Python 以后，排序直接使用自带的函数，没有去学习一些排序算法的原理。今天课上讲了一些简单的排序算法的原理，比如 冒泡 选择 插入，于是打算自己把这些算法实现一遍，提升自己的理解。

这是 算法备忘录 系列的第一篇，介绍冒泡和选择排序。以下的代码是我自己写的，只是为了表达原理，并不一定是最优的写法。

冒泡排序

冒泡排序的大致原理是依次比较两个数字，如果大小与所要求的相反，就交换位置。在全部比较完一遍后，从头开始，重新比较。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 使用 random 中的 shuffle 生成一个乱序的数字序列
import random
n = 1000
lst = []
for i in range(n):
    lst.append(i)
random.shuffle(lst)

# 算法主体
for i in range(n - 1):
    for j in range(n - 1 - i):
        if lst[j] > lst[j + 1]:
            lst[j], lst[j + 1] = lst[j + 1], lst[j]
print(lst)

选择排序

选择排序的大致原理是从数列中先选出最大（或最小）的数字，再从剩下的数列中选出剩下中最大（或最小）的，依次类推，直到选完。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 使用 random 中的 shuffle 生成随机数列
import random
n = 1000
lst = []
for i in range(n):
    lst.append(i)
random.shuffle(lst)

# 算法主体部分
for i in range(n - 1):
    min = i
    for j in range(i + 1, n):
        if lst[min] > lst[j]:
            min = j
    lst[i], lst[min] = lst[min], lst[i]
print(lst)
许可协议

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

分享文章