排序（上）- 冒泡、插入和选择

冒泡、插入和选择

排序

最经典的、最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

分为三类

冒泡排序、插入排序、选择排序

时间复杂度O(n^2), 基于比较

归并排序、快速排序

时间复杂度O(nlogn), 基于比较

计数排序、基数排序、桶排序

时间复杂度O(n), 不基于比较

如何分析一个“排序算法”？

排序算法的执行效率

最好情况、最坏情况、平均情况时间复杂度
时间复杂度的系数、常数 、低阶
比较次数和交换（或移动）次数

排序算法的内存消耗

我们前面讲过，算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。

排序算法的稳定性

这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

冒泡排序（Bubble Sort）

1
2
3
4
5
6
7
8
9
10
11
12
arrays = [4, 5, 6, 3, 2, 1]
def bubble_sort(arrays):
    length = len(arrays)
    if length < 2:
        return arrays

    for i in range(length):
        for j in range(length-i-1):
            if arrays[j+1] < arrays[j]:
                arrays[j+1], arrays[j] = arrays[j], arrays[j+1]

    print(arrays)
冒泡排序是原地排序，空间复杂度为O(1)
当相邻两元素相等时不做交换时为稳定排序

时间复杂度分析

最好时间复杂度为O(n), 最坏时间复杂度为O(n^2)

平均时间复杂度

又称加权平均期望复杂度。

如果用概率论方法定量分析平均时间复杂度，涉及的数学推理和计算就会很复杂。我这里还有一种思路，通过“有序度”和“逆序度”这两个概念来进行分析。

有序度是数组中具有有序关系的元素对的个数。其数学表达式为：

1
有序元素对：a[i] <= a[j], 如果i < j。

完全有序的数组，其有序度为:

1
n(n-1) / 2

完全有序的数组的有序度叫作满有序度

逆序度的定义正好跟有序度相反。

三者的关系

满有序度 = 有序度 + 逆序度

我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。

所以冒泡排序的平均时间复杂度为O(n^2)

插入排序（Insertion Sort）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
arrays = [4, 5, 6, 3, 2, 1]

# 插入排序
def insertionsort(arrays):
    length = len(arrays)

    if length < 2:
        return arrays

    for i in range(1, length):
        j = i - 1
        val = arrays[i]

        while j >= 0 and arrays[j] > val:
            arrays[j+1] = arrays[j]
            j -= 1

        arrays[j+1] = val

    print(arrays)
冒泡排序是原地排序，空间复杂度为O(1)
当相邻两元素相等时不做交换时为稳定排序
最好时间复杂度O(n), 最坏时间复杂度O(n^2), 平均时间复杂度O(n^2)

选择排序（Selection Sort）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 选择排序
def selectionsort(arrays):
    length = len(arrays)

    if len(arrays) < 2:
        return arrays

    for i in range(length):
        min_val = arrays[i]
        min_idx = i
        for j in range(i+1, length):
            if arrays[j] < min_val:
                min_val = arrays[j]
                min_idx = j

        if min_idx != i:
            arrays[i], arrays[min_idx] = arrays[min_idx], arrays[i]

    print(arrays)
空间复杂度 O(1)
不稳定排序
最好时间复杂度O(n^2), 最坏时间复杂度O(n^2)，平均时间复杂度O(n^2)

为什么插入排序要比冒泡排序更受欢迎呢

因为冒泡排序需要两个位置进行数据交换，对于C语言这种就需要三个变量进行操作；但插入排序，只需要将数据后移，可以省略交换的操作。假设赋值语句时时间是K，那么冒泡排序需要的就是3K，而插入排序就是K，差距显而易见。

另外，希尔排序 是对插入排序的优化。

内容小结

冒泡、插入和选择对于小规模数据非常高效，但当数据规模很大时，就不再适用了。

思考

数据存储在链表中，这三种排序算法还能工作吗？如果能，那相应的时间、空间复杂度又是多少呢？

考虑只能改变节点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；选择排序比较次数一致，交换操作同样比较麻烦。综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会变大，插入排序系数会减小，选择排序无明显变化。