浅谈排序算法与优化（仅部分，Updating）
欢迎查阅与 star 的源码 写在最前面，此文章少了各排序算法的对比，但多了一份由浅入深的个人理解，以及代码、及算法的优化的思路 阅读文章约 需 5min
列表排序
排序
将一组 “无序” 的记录序列调整为 “有序” 的记录序列
列表排序
将无序的列表变为有序列表 输入：列表； 输出：有序列表
升序与降序 内置排序函数：sort（），基于 timsort 排序算法
Timsort 是一种混合稳定排序算法，源自归并排序（merge sort）和插入排序（insertion sort）
有兴趣的伙计可以看看这两篇文章 sort 算法运用原理 1 sort 算法运用原理 2 
常见排序算法
LOW：
冒泡：
列表每两个相邻的数，如果前面比后面大，则交换这两个数 一趟排序完成后，则无序区减少一个数，有序区增加一个数
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
def bubble_sort(li: List[List]) -> List:
print('初始列表', li)
print('初始列表长度：', len(li))
for i in range(len(li) - 1): # 第i躺,总次数
i += 1
for j in range(len(li) - i - 1): # 指针
if li[j] > li[j + 1]: # 如果指针所对应的值大于对比的值，则二者交换位置
li[j], li[j + 1] = li[j + 1], li[j]
else:
break
print(f'冒泡排序第{i}次', li)
li = [np.random.randint(0, 1000) for i in range(5)]
bubble_sort(li)
数据来源于numpy.randmo.randint()随机取数，运行流程：
冒泡排序第1次 [257, 620, 136, 379, 392, 118, 312, 892, 647, 655]
冒泡排序第2次 [257, 620, 136, 379, 392, 118, 312, 892, 647, 655]
冒泡排序第3次 [257, 620, 136, 379, 392, 118, 312, 892, 647, 655]
冒泡排序第4次 [257, 620, 136, 379, 392, 118, 312, 892, 647, 655]
冒泡排序第5次 [257, 620, 136, 379, 392, 118, 312, 892, 647, 655]
冒泡排序第6次 [257, 620, 136, 379, 392, 118, 312, 892, 647, 655]
冒泡排序第7次 [257, 620, 136, 379, 392, 118, 312, 892, 647, 655]
冒泡排序第8次 [257, 620, 136, 379, 392, 118, 312, 892, 647, 655]
冒泡排序第9次 [257, 620, 136, 379, 392, 118, 312, 892, 647, 655]
# 排序次数：列表长度-1,
# 缘由将无序区转化为有序区：(再看一遍以下这段代码， 如果li[j]>li[j+1],则二者交换位置）
if li[j] > li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]
# 当一维数组长度为10000的时候所需时间为：
优化： 在一次回头看看冒泡排序具体实现思路，将列表每两个相邻的数，如果前面比后面大，则交换这两个数 , 一趟排序完成后，则无序区减少一个数，有序区增加一个数。 如果无序区已经是有序的呢？按照代码执行流程可知， 如果前者比后者大，那么则两个交换位置。（假设为降序，前面为无序区，后面为有序区） 否则不执行任何交换操作，但会执行便利（也可以理解为此运算” 不执行任何交换操作，无实际意义”） 优化目标：(将 “不执行任何交换的操作去掉”)，咱们在回头看看，具体实际的运算是在第二层 for 循环里面的，也就说所谓的 “无用功” 也是在这里产生的 无用功体现为：无论是否进行了位置交换，都会在往有序区在遍历检查一遍 思路如下： 主要优化的地方在跳出循环，在它不交换位置的时候，直接跳出此次的循环 假设它全部都是有序的，并设个标记 True， 当如果循环内发生了位置交换，则改变标记为 False。 流程控制，if。当 if True 的时则会执行 if 内部代码（设立 return，或者 break）主要跳出循环。避免对有序区进行有一次的排序操作 具体代码实现如下：
2
3
4
5
6
7
8
9
10
11
print("The len of List:", len(li)) # 输入数组长度
for i in range(len(li) - 1): # 保证输入的数组在计算范围类，此处的“-1”是因为索引=长度-1
flag = True
for j in range(len(li) - i - 1):
if li[j] > li[j + 1]:
li[j + 1], li[j] = li[j], li[j + 1]
flag = False
print("Sorting times:%d， Status：%s" % (i + 1, li))
if flag:
break
选择: 插入:
Stronger
快速排序： 堆排序 归并排序
其他排序：
希尔排序 计数排序 基数排序
1 |
break |
选择: 插入:
Stronger
快速排序： 堆排序 归并排序
其他排序：
希尔排序 计数排序 基数排序
文章来源: cuiqingcai.com，作者：Payne，版权归原作者所有，如需转载，请联系作者。
原文链接：cuiqingcai.com/9511.html