排序算法（1）- 冒泡、插入、选择

有一些最经典的、最常用的算法，按照时间复杂度可以分为三类

排序算法	时间复杂度	是否基于比较
冒泡、插入、选择	O(n^2)	是
快排、归并	O(nlogn)	是
桶、计数、基数	O(n)	否

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

排序算法的执行效率

一般从以下几个方面来衡量：

1. 最好情况、最坏情况、平均情况时间复杂度
2. 时间复杂度的系数、常数、低阶
   日常情况下，我们业务中的数据规模也不过是几百上千，这时候在比较算法的时候也要把这些考虑进来
3. 比较次数和交换（或移动）次数

排序算法的内存消耗

通过空间复杂度来衡量，这里引入一个新概念，原地排序（Sorted in place）。原地排序算法，就是空间复杂度为 O(1) 的排序算法

排序算法的稳定性

数据中往往会有相等的数据，稳定性是指经过比较后，相等的数据的先后顺序是否不变。实际应用中，稳定性往往能简化一些操作，提升效率。

冒泡排序

冒泡排序每次只会交换两个相邻的元素。遍历数组，将遍历到的元素和它后面的所有元素比较，满足条件就互换元素。

bubble_sort.gif

def bubble_sort(array):
    """
    冒泡排序
    :param array:
    :return:
    """
    count = len(array)
    if count <= 1:
        return
    
    for i in range(count):
        flag = False    # 这里优化一下，如果已经达到完全有序，则不需要再比较
        for j in range(count-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
                flag = True
        if not flag:
            break

这里要说一下有序度：对于一个倒序排列的数组，比如6, 5, 4, 3, 2, 1, 有序度是0；对于一个完全有序的数组，比如1, 2, 3, 4, 5, 6，有序度是 n*(n-1)/2，也就是15。这种有序度叫做满有序度。逆序度的定义跟有序度相反。逆序度=满有序度-有序度。数组排序的操作就是一个增加有序度，减少逆序度的过程，最后达到满有序度

冒泡排序每次最多交换一个元素，也就是说每次有序度都会+1，所以要交换的次数就是逆序度数。对于数组[4, 5, 6, 3, 2, 1]，初始有序度是(4, 5), (4, 6), (5, 6)，则要进行15-3=12次交换操作。

分析：

1. 冒泡排序每次只交换相邻数据，只需要常量级的临时空间，所以空间复杂度是O(1)，是一个原地排序算法
2. 每次只改变相邻元素，如果相等则不交换，所以是稳定的排序算法
3. 数据是有序的，则进行一次冒泡就结束了，最好时间复杂度为O(n)，数据是倒序的，则需要进行n此冒泡，最坏时间复杂度为O(n^2)， 平均时间复杂度为O(n^2)

插入排序

想象一下，把一个待排序的数组分为有序区和无序区，遍历数组，每次从无序区取出第一个元素，和有序区从后往前比较，找到要替换的地方插入，这就是插入排序

insertion_sort.gif

def insertion_sort(array):
    """
    插入排序
    :param array:
    :return:
    """
    count = len(array)
    if count <= 1:
        return
    for i in range(count):
        value = array[i]
        j = i - 1
        while j >= 0:
            if array[j] > value:
                array[j+1] = array[j]   # 数据移动
            else:
                break
            j -= 1
        array[j+1] = value  # 插入数据

分析：

1. 插入排序不需要额外的存储空间，是一个原地排序算法。
2. 对于值相同的元素，可以选择将后面出现的元素，插入到前面出现的元素后面，这样就可以保持前后顺序不变，所以是一个稳定的排序算法。
3. 如果是一个有序数据，则每次比较都不需要往前继续遍历有序区交换数据，只会一直拿无序区的数据，所以最好时间复杂度为O(n)，如果完全倒序，每次拿无序区的数据都要和有序区的完全比较一遍，最坏时间复杂度为O(n^2)。 在数组中插入一个数据的平均复杂度为O(n)，插入排序每次操作都是相当于在数组中插入一个数据，循环执行n次，所以平均时间复杂度为O(n^2)。

选择排序

选择排序和插入排序有些类似，都是分为有序区和无序区，只不过选择排序是从无序区找到最小的那个元素，把它直接放在有序区的末尾

selection_sort.gif

def selection_sort(array):
    """
    选择排序
    :param array:
    :return:
    """
    count = len(array)
    if count <= 1:
        return
    for i in range(count):
        min_idx = i
        for j in range(i+1, count):
            if array[min_idx] > array[j]:
                min_idx = j
        array[i], array[min_idx] = array[min_idx], array[i]

分析：

1. 是一种原地排序算法
2. 它不是稳定的。举个例子，[5, 8, 5, 2, 9]，第一次会找到最小元素2，然后和5交换位置，这样第一个5和后面的5顺序就改变了，所以它不是稳定的排序算法
3. 最好、最坏、平均时间复杂度都为O(n^2)。因为它每次都要从未排序区找出最小的一个元素，即使是一个有序数据。

插入比冒泡更好

我们可以看一下两个排序的交换部分的关键代码

# 冒泡
if array[j] > array[j+1]:
    array[j], array[j+1] = array[j+1], array[j]
    
# 插入
if array[j] > value:
    array[j+1] = array[j]

上面冒泡排序交换两个元素，因为我是用Python写的原因，所以直接用元祖的方式交换，但是本质上还是会设置一个临时变量来存储元素，和C的交换一样

temp c = a;
a = b;
b = c;

所以冒泡排序实际是有三个操作步骤的，设置临时变量，赋值，赋值，而插入排序呢，只需要一个基于数组下标的交换而已。假设每个操作的时间复杂度为K，则冒泡每次交换需要 3K个时间，而插入只需要 1K个时间，当数据规模足够大时，就会看到明显的差别。
下面我创建了一个数组，包含200个数组，每个数组包含400个随机的元素，分别对它们进行排序。

items = []
for _ in range(200):
    sub_items = []
    for _ in range(400):
        sub_items.append(random.randint(1, 1000))
    items.append(sub_items)

start_time = time.time()
for sub_items in items:
    bubble_sort(sub_items)
end_time = time.time()
print("冒泡排序耗时：{0}".format(end_time - start_time))

start_time = time.time()
for sub_items in items:
    insertion_sort(sub_items)
end_time = time.time()
print("插入排序耗时：{0}".format(end_time - start_time))

"""
冒泡排序耗时：4.031335115432739
插入排序耗时：0.021035194396972656
"""

在当前的数据规模和系统环境下，冒泡排序的耗时已经是插入排序的200倍。所以在性能优化的选择上，首选插入排序

总结

	是否原地排序	是否稳定	最好	最坏	平均
冒泡排序	是	是	O(n)	O(n^2)	O(n^2)
插入排序	是	是	O(n)	O(n^2)	O(n^2)
选择排序	是	否	O(n^2)	O(n^2)	O(n^2)