浅谈排序算法与优化（仅部分，Updating）

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

列表排序

排序

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

列表排序

将无序的列表变为有序列表输入：列表；输出：有序列表

升序与降序内置排序函数：sort（），基于timsort排序算法

Timsort是一种混合稳定排序算法，源自归并排序（merge sort）和插入排序（insertion sort）

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

常见排序算法

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的时候所需时间为：
优化： 在一次回头看看冒泡排序具体实现思路，将列表每两个相邻的数，如果前面比后面大，则交换这两个数,一趟排序完成后，则无序区减少一个数，有序区增加一个数。如果无序区已经是有序的呢？按照代码执行流程可知，如果前者比后者大，那么则两个交换位置。（假设为降序，前面为无序区，后面为有序区）否则不执行任何交换操作，但会执行便利（也可以理解为此运算”不执行任何交换操作，无实际意义”）优化目标：(将“不执行任何交换的操作去掉”)，咱们在回头看看，具体实际的运算是在第二层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