Python十大排序算法（亲自实现代码超详细描述）_python列表排序算法

前言

你好，我是Dr.叶子，用心写最优美的博客，弹最好听的钢琴！

背景

• 最近整理知识点，发现在数据结构方面不是很扎实，所以自己重新学习排序算法，结合网上资料，自己深度理解，再利用Python3来实现，与大家分享，也提升自己的知识水平！
• 本文包含冒泡排序、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、计数排序、桶排序、基数排序，每一段代码都有详细的注释。

---

 

排序分类

---

 

一、冒泡排序（交换类）

 
1. 算法步骤：

    ① 从头开始，依次两两比较待排序列表中的相邻元素，若前者比后者大，则交换位置，直到最大的元素排在最后位置，一轮排序完成，重复本步骤；

    ② 每一轮排序完成，将产生 1 个最大元素排在最后，该元素不再参与下一轮比较；

    ③ 待排序列表的长度每轮 -1，即去掉最后一个已经完成排序的元素；

 
2. 演示：

 
3. 代码实现：

def bubble_sort(List):
    # 1.原列表长度
    n = len(List)
    # 2.依次两两比较
    for i in range(1, n):
        for j in range(0, n - i):
            # 3.前者比后者大，则交换位置
            if List[j] > List[j + 1]:
                List[j], List[j + 1] = List[j + 1], List[j]
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = bubble_sort(List)
    print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

 

二、快速排序（交换类）

 
1. 算法步骤：

    ① 从原列表中选一个元素，作为"基准值"；

    ② 以这个"基准值"为原则，划分成左、右 2 个子列表，大于“基准值”的元素放右列表，小于“基准值”的元素放左列表（等于的可左可右）；

    ③ 重复步骤 ① ，继续分别在 2 个子列表中，各自选取"基准值"来划分出新的、各自的左、右子列表；

详细流程，请看静态演示部分图示；

 
2. 演示：

 
【 静态演示 】：

 
3. 代码实现：

# 6快速排序
def quick_sort(List):
    # 1.原列表长度
    n = len(List)
    # 2.若列表少于2个元素，返回当前列表（递归的结束条件）
    if n < 2:
        return List
    # 3.选取基准值，这里选择首位元素，并将其从原列表中移除（因为要将剩下的元素分组）
    base = List[0]
    List.remove(base)
    # 3.预先定义空列表，即基准值的左右两个列表
    left, right = [], []
    # 4.遍历剩下的元素
    for value in List:
        if value >= base:
            # 大于等于基准值放右边
            right.append(value)
        else:
            # 小于基准值放左边
            left.append(value)
    # 5.递归，将基准值放中间组合成已完成的有序列表
    return quick_sort(left) + [base] + quick_sort(right)


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = quick_sort(List)
    print(result)
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
28

---

 

三、插入排序（插入类）

 
1. 算法步骤：

    ① 将原列表第一个元素固定，当成是已排序列表，剩下的所有元素组成待排序列表；

    ② 从头开始，依次遍历待排序列表，同时从后往前遍历已排序列表进行比较，插入到合适位置，重复上一步骤；

注意： 待排序列表的元素与已排序列表中的某个元素相等时，则插入到相等元素的后面位置。

 
2. 演示：

 
3. 代码实现：

def insert_sort(List):
    # 1.原列表长度
    n = len(List)
    # 2.依次遍历“待排序列表”（即原列表第2个元素开始）
    for i in range(1, n):
        # 当前待排序元素的值 
        current = List[i]
        # “已排序列表”中最后一个元素的位置索引（相较于原列表）
        index = i - 1
        # 3.从后往前遍历“已排序列表”
        while index >= 0 and current < List[index]:
            # 若小于，则交换值，继续往前遍历
            List[index + 1], List[index] = List[index], current
            index -= 1
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = insert_sort(List)
    print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

 

四、希尔排序（插入类）

 
1. 算法步骤：

    ① 将原列表相隔某个增量 h 的元素构成一个子列表，分别进行插入排序；

    ② 排序过程中，逐次减小 h 的值来进行新一轮的分割；

    ③ 最后当 h 减到1时，再全部元素进行一次插入排序，排序完成；

基本思想： 将原列表分割成多个子列表，分别进行插入排序。
增量 h 一般取值： h = n / 2 ，n为待排序列表长度。

 
2. 演示：

 
3. 代码实现：

def shell_sort(List):
    # 1.原列表长度
    n = len(List)
    # 2.首轮排序设置的间隔增量
    h = int(n / 2)

    # 3.循环分组
    while h >= 1:
        # 4.循环每一组子列表
        for i in range(h, n):
            # 当前待排序元素的值
            current = List[i]
            # “已排序列表”中最后一个元素的位置索引（相较于原列表）
            index = i
            # 5.每一组子列表分别进行插入排序
            while index >= h and current < List[index - h]:
                # 若小于，则交换值，继续往前遍历
                List[index], List[index - h] = List[index - h], current
                index -= h
        # 6.间隔增量缩小一半，继续循环，直到 h=1 再整体进行最后一次插入排序
        h = int(h / 2)
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = shell_sort(List)
    print(result)
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
28

---

 

五、选择排序（选择类）

 
1. 算法步骤：

    ① 从头开始，依次扫描列表，选出最小元素，将它交换到待排序列表的最前面，一轮结束；

    ② 每一轮排序完成，将产生 1 个最小元素排在最前，该元素不再参与下一轮比较，相应剩余的元素作为新的待排序列表，重复上一步骤；

 
2. 演示：

 
3. 代码实现：

def select_sort(List):
    # 1.原列表长度
    n = len(List)
    # 2.循环（n-1）轮排序
    for i in range(n - 1):
        # 3.记下最小元素的位置索引，默认为每轮新的待排序列表的首位i
        min_index = i
        # 4.循环寻找待排序列表中的最小元素的位置索引，并更新min_index
        for j in range(i + 1, n):
            if List[j] < List[min_index]:
                min_index = j
        # 5.循环完元素后判断，若最小元素的位置索引min_index不是首位i，则交换元素
        if min_index != i:
            List[i], List[min_index] = List[min_index], List[i]
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = select_sort(List)
    print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

 

六、堆排序（选择类）

 
1. 算法步骤：

    ① 将原列按顺序从上往下、从左往右原则，一个个元素插入，构建出一个堆；

    ② 在每个元素插入的过程（也就是创建堆的过程），每次都与父节点比较，若大于父节点，则与父节点元素交换位置；

    ③ 每一轮筛选出最大值（堆顶），与堆尾元素交换，同时堆尾元素交换到堆顶位置后，继续与子节点比较，即重复步骤 ②；

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

• 大顶堆： 每个节点的值都大于或等于其左、右子节点的值；
• 小顶堆： 每个节点的值都小于或等于其左、右子节点的值；
  一般升序采用大顶堆，降序采用小顶堆

 
2. 演示：

视频参考： 数据结构排序算法之堆排序演示（这个比较形象点，不明白的可以参观下）

 
3. 代码实现：

def heapify(List, n, i):
    """
    判断程序：与父节点比较，判断最大值，转移到父节点
    """
    max_index = i   # 默认传入的节点为最大值节点（父节点）位置索引
    left_index = 2 * i + 1  # 左节点位置索引 = 2 * i + 1
    right_index = 2 * i + 2  # 右节点位置索引 = 2 * i + 2

    # 1.判断左节点，若大于父节点值，则改变 max_index = 该左节点的索引
    if left_index < n and List[i] < List[left_index]:
        max_index = left_index

    # 2.判断右节点，若大于父节点值，则改变 max_index = 该右节点的索引
    if right_index < n and List[max_index] < List[right_index]:
        max_index = right_index

    # 3.若最大值节点的索引发生变化，则交换值
    if max_index != i:
        List[i], List[max_index] = List[max_index], List[i]  # 交换
        # 4.递归继续寻找最大值节点索引
        heapify(List, n, max_index)


def heap_sort(List):
    """
    主程序
    """
    # 1.原列表长度
    n = len(List)

    # 2.建立大顶堆，同时调用判断程序与父节点比较
    for i in range(n, -1, -1):
        heapify(List, n, i)

    # 3.将顶堆元素交换到堆尾，同时调用判断程序与父节点比较
    for i in range(n - 1, 0, -1):
        List[i], List[0] = List[0], List[i]  # 交换
        heapify(List, i, 0)
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = heap_sort(List)
    print(result)
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---

 

七、归并排序

 
1. 算法步骤：

    ① 将原列表平均拆分成 2 个子列表，每个子列表继续分别拆分成 2 个子列表…直到每个子列表元素个数为 1 不能继续拆分为止；

    ② 依次合并，完成排序；

这里表述可能不清楚，建议看静态演示~

3. 演示：

【静态演示】

 
3. 代码实现：

def merge(left, right):
    """
    副程序：合并排序
    """
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))  # 每次消掉首位元素
        else:
            result.append(right.pop(0)) # 每次消掉首位元素
    while left:
        result.append(left.pop(0))  # 每次消掉首位元素
    while right:
        result.append(right.pop(0)) # 每次消掉首位元素
    return result


def merge_sort(List):
    """
    主程序
    """
    # 1.原列表长度
    n = len(List)
    # 2.若列表少于2个元素，返回当前列表（递归的结束条件）
    if n < 2:
        return List
    # 3.拆分成左、右2个列表
    middle = n // 2
    left, right = List[0:middle], List[middle:]
    # 4.返回递归结果
    return merge(merge_sort(left), merge_sort(right))


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = merge_sort(List)
    print(result)
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
28
29
30
31
32
33
34
35
36
37

---

 

八、计数排序（桶相关）

 
1. 算法步骤：

    ① 找出原列表中最大值、最小值，初始化一个计数列表记录各个元素出现次数；

    ②在原列表中， 统计各个元素前比自己小的数的个数，然后输出；

计数排序要求输入的数据必须是有确定范围的整数。

 
2. 演示：

 
3. 代码实现：

def count_sort(List):
    # 1.原列表长度
    n = len(List)
    # 2.初始化一个尽量大长度的“计数列表”，用来统计原列表各个元素出现次数
    max_value = max(List)
    min_value = min(List)
    count_len = max_value - min_value + 1
    count_list = [0 for i in range(count_len)]
    # 3.初始化一个最终“结果列表”
    res = [0 for i in range(n)]
    # 4.遍历“原列表”，统计各元素出现次数，并记录在“计数列表”（只要是同一个元素就会出现在同一位置）
    for value in List:
        # 【该元素与最小值的距离】
        distance = value - min_value
        count_list[distance] += 1
    # 5.遍历“计数列表”，每个元素前一位，增加到本元素中，“计数列表”即刻更新
    for j in range(1, count_len):
        count_list[j] = count_list[j] + count_list[j - 1]
    # 6.遍历“原列表”，统计各个元素前比自己小的数的个数，然后输出
    for value in List:
        # 【该元素与最小值的距离】
        distance = value - min_value
        res[count_list[distance] - 1] = value
        count_list[distance] -= 1
    return res


if __name__ == '__main__':
	List = [2, 2, 7, 7, 7, 5, 5, 5, -1, -1]
    result = count_sort(List)
    print(result)
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
28
29
30
31

---

 

九、桶排序（桶相关）

 
1. 算法步骤：

    ① 初始化一个空的 [ ] 桶列表；

    ② 把数据放到对应的桶中；

    ③ 对每个不为空的桶中数据进行排序，拼接得到结果；

类似“计数排序”。

 
2. 演示：

• 视频参考： 数据结构排序算法之桶排序演示（找了很多动图，感觉还是这个视频形象，就不贴其他图了，代码也很详细描述）
• 不明白的再分享一篇博文：五分钟看懂一个有意思的排序：桶排序.

 
3. 代码实现：

def bucket_sort(List):
    # 1.原列表长度
    n = len(List)
    # 2.初始化一个空的[]“桶列表”
    min_value = min(List)
    max_value = max(List)
    bucket_len = (max_value - min_value) / n
    bucket_list = [[] for i in range(n + 1)]
    # 3.遍历“原列表”，向“桶列表”压入元素
    for value in List:
        bucket_list[int((value - min_value) // bucket_len)].append(value)
    # 4.声明一个返回的“结果列表”
    res = []
    # 5.遍历“桶列表”，直接sorted排序，压入“结果列表”
    for i in bucket_list:
        for j in sorted(i):
            res.append(j)
    return res


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = bucket_sort(List)
    print(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

 

十、基数排序（桶相关）

 
1. 算法步骤：

• 其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
• 由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序不限于整数。

 
2. 演示：

 
3. 代码实现：

def radix_sort(List):
    # 1.记录初始排序的位置，为个位数
    index = 0
    # 2.“原列表”最大值
    max_value = max(List)
    # 3.最大值的长度
    max_value_len = len(str(max_value))
    # 4.循环按位数排序
    while index < max_value_len:
        # 5.初始化一个空的[]“桶列表”
        bucket_list = [[] for i in range(10)]
        for value in List:
            # 6.放入“桶列表”
            bucket_list[int(value / (10 ** index)) % 10].append(value)
        # 7.清空“原列表”
        List.clear()
        # 8.遍历“桶列表”元素，将元素放入“原列表”
        for x in bucket_list:
            for y in x:
                List.append(y)
        # 9.位数+1
        index += 1
    return List


if __name__ == '__main__':
    List = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    result = radix_sort(List)
    print(result)
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
28
29

---

参考来源

【1】动图来源： Python版十大经典排序算法（动图演示）.
【2】原理参考： 十大经典排序算法.
【3】关于递归的理解： 知乎：对于递归有没有什么好的理解方法？.

---

后语

1. 原创内容，转载说明出处哦！
2. 以上内容本人整理，亲测可行，如有任何问题，敬请指正，谢谢~~
3. 点赞、收藏、也欢迎打赏，我弹钢琴你听呀~~哈哈！