我们不能失去信仰

我们在这个世界上不停地奔跑...

0%

冒泡排序和插入排序的性能分析

发表于 更新于 分类于

分析一个排序算法的执行效率

  • 最好情况、最坏情况、平均情况时间复杂度

排序算法在面对排序数组的原始情况时，会出现不同的复杂度。有的接近有序，有的完全无序，有序程度不同的数据，对于排序的执行时间肯定是有影响的。

  • 时间复杂度的系数、常数、低阶

时间复杂度反应的是数据规模n很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能是10个、100个、1000个这丫昂规模很小的数据，所以在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

  • 比较次数和交换（或移动）次数

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

  • 排序算法的内存消耗

针对排序算法的空间复杂度，我们使用“原地排序”来特指空间复杂度是O（1）的排序算法。

  • 排序算法稳定性

针对排序算法，有一个重要的指标，排序算法的稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。比如一个班级成绩单，我们想先按照语文成绩排序，然后再按照数学成绩排序，如果两个同学的数学成绩相等，但是语文成绩同学乙比同学甲高， 还没有进行数学排序前，同学乙的排名比同学甲靠前，排序后，可能由于排序算法不稳定，将甲与乙交换了位置，最终破坏了语文排序的正确性，这样的排序算法就不稳定。

简单分析冒泡排序和插入排序

对于冒泡排序可以稍作优化，即在某次冒泡过程中，如果没有发生数据交换，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

大家应该对这俩排序都非常熟悉，那么就直接说结论，冒泡排序和插入排序的时间复杂度都是O（n方），空间复杂度都是O（1），但是插入排序会比冒泡排序更加受欢迎。

涉及到推理的，就直接说结论，冒泡排序和插入排序不管怎么优化，元素的交换次数是一个固定的值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也是等于原始数据的逆序度。

但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的移动数据要复杂，冒泡排序需要1个以上赋值操作，而插入排序只需要1个

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
# 冒泡排序
def bubble_sort(arr):
    for i in range(len(arr)):
        switch = False
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                switch = True
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        if switch is False:
            break

    return arr
# 插入排序

def insert_sort(arr):

    for i in range(1, len(arr)):
        value = arr[i]
        j = i - 1
        while j >= 0:
            if value < arr[j]:
                arr[j+1] = arr[j]
            else:
                break
            j -= 1
        arr[j+1] = value
    return arr
  
# 测试耗时语句

import random
import time
arr = [[random.randint(-199, 199) for _ in range(100)] for _ in range(10000)]
start = time.time()
for li in arr:
    # insert_sort(li)
    # bubble_sort(li)
    li.sort()
cost_time = time.time() - start

print('耗时:', cost_time)

插入排序对应的优化排序时希尔排序。

我们通过测试语句对10000个长度为100的数组进行排序，使用Python 的出来的结论如下。

冒泡排序花费时间： 7.165948152542114 s

插入排序花费时间： 3.3916192054748535 s

差距还是很大的，然后我们再使用 Python 自带的库函数进行排序，看看花费的时间

list.sort() 花费时间： 0.0537569522857666 s