有一些最经典的、最常用的算法，按照时间复杂度可以分为三类
| 排序算法 | 时间复杂度 | 是否基于比较 |
|---|---|---|
| 冒泡、插入、选择 | O(n^2) | 是 |
| 快排、归并 | O(nlogn) | 是 |
| 桶、计数、基数 | O(n) | 否 |
如何分析一个“排序算法”
排序算法的执行效率
一般从以下几个方面来衡量：
- 最好情况、最坏情况、平均情况时间复杂度
- 时间复杂度的系数、常数、低阶
日常情况下，我们业务中的数据规模也不过是几百上千，这时候在比较算法的时候也要把这些考虑进来 - 比较次数和交换（或移动）次数
排序算法的内存消耗
通过空间复杂度来衡量，这里引入一个新概念，原地排序（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次交换操作。
分析：
- 冒泡排序每次只交换相邻数据，只需要常量级的临时空间，所以空间复杂度是O(1)，是一个原地排序算法
- 每次只改变相邻元素，如果相等则不交换，所以是稳定的排序算法
- 数据是有序的，则进行一次冒泡就结束了，最好时间复杂度为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 # 插入数据
分析：
- 插入排序不需要额外的存储空间，是一个原地排序算法。
- 对于值相同的元素，可以选择将后面出现的元素，插入到前面出现的元素后面，这样就可以保持前后顺序不变，所以是一个稳定的排序算法。
- 如果是一个有序数据，则每次比较都不需要往前继续遍历有序区交换数据，只会一直拿无序区的数据，所以最好时间复杂度为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]
分析：
- 是一种原地排序算法
- 它不是稳定的。举个例子，[5, 8, 5, 2, 9]，第一次会找到最小元素2，然后和5交换位置，这样第一个5和后面的5顺序就改变了，所以它不是稳定的排序算法
- 最好、最坏、平均时间复杂度都为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) |
网友评论