0%

浅谈排序算法与优化(仅部分,Updating)

浅谈排序算法与优化(仅部分,Updating)

欢迎查阅与star的源码 写在最前面,此文章少了各排序算法的对比,但多了一份由浅入深的个人理解,以及代码、及算法的优化的思路 阅读文章约 需 5min

列表排序

排序

将一组“无序”的记录序列调整为“有序”的记录序列

列表排序

将无序的列表变为有序列表 输入:列表; 输出:有序列表

升序与降序 内置排序函数:sort(),基于timsort排序算法

Timsort是一种混合稳定排序算法,源自归并排序(merge sort)和插入排序(insertion sort)

有兴趣的伙计可以看看这两篇文章 sort算法运用原理1 sort算法运用原理2 TimSort

常见排序算法

LOW:

冒泡:

列表每两个相邻的数,如果前面比后面大,则交换这两个数 一趟排序完成后,则无序区减少一个数,有序区增加一个数

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
@cal_time
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的时候所需时间为:

Runtime 优化: 在一次回头看看冒泡排序具体实现思路,将列表每两个相邻的数,如果前面比后面大,则交换这两个数,一趟排序完成后,则无序区减少一个数,有序区增加一个数。 如果无序区已经是有序的呢?按照代码执行流程可知, 如果前者比后者大,那么则两个交换位置。(假设为降序,前面为无序区,后面为有序区) 否则不执行任何交换操作,但会执行便利(也可以理解为此运算”不执行任何交换操作,无实际意义”) 优化目标:(将“不执行任何交换的操作去掉”),咱们在回头看看,具体实际的运算是在第二层for循环里面的,也就说所谓的“无用功”也是在这里产生的 无用功体现为:无论是否进行了位置交换,都会在往有序区在遍历检查一遍 思路如下: 主要优化的地方在跳出循环,在它不交换位置的时候,直接跳出此次的循环 假设它全部都是有序的,并设个标记True, 当如果循环内发生了位置交换,则改变标记为False。 流程控制,if。当if True的时则会执行if内部代码(设立return,或者break)主要跳出循环。避免对有序区进行有一次的排序操作 具体代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
def bubble_sort(li: List):
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

快速排序: 堆排序 归并排序

其他排序:

希尔排序 计数排序 基数排序