两种最基本的排序算法: 冒泡和选择 | 隔叶黄莺 Yanbin Blog

2020-04-14 | 阅读(367)

因 COVID-19 漫延各自居家，也更有闲时，便拣起一本关于算法的书籍来研究。本不是科班出身，算法方面自然是自己的薄弱环节。平时用各种 SDK，只大概听说了些算法，仅能就自己如何选择哪种实现而作为参考。

如今阅读的是一本入门的书籍，名为《算法图解》，英文版书名是《Grokking Algorithms》。该书图文并茂，十分适合初学者，关于排序最基本莫过于冒泡与选择排序。该书并未提及冒泡，而是直接从选择排序切入，在阅读本书之前我就一直对这两咱排序方式傻傻不分。一直以为头脑中的选择排序就是冒泡排序，那就来看下什么是真正的冒泡排序。

冒泡排序

以 Python 代码为例：

items = [6, 5, 3, 1, 8, 7, 2, 4]
length = len(items)

for i in range(length):    #1
    for j in range(length - i - 1):
        if items[j] > items[j + 1]:
            items[j], items[j + 1] = items[j + 1], items[j]  #2

print(items)

items = [6, 5, 3, 1, 8, 7, 2, 4]

length = len(items)

for i in range(length): #1

for j in range(length - i - 1):

if items[j] > items[j + 1]:

items[j], items[j + 1] = items[j + 1], items[j] #2

print(items)

#1: range(length) 和 range(0, length) 是一样的
#2: 这是 Python 交换两个值的写法，相当于用临时变量的方式 tmp = items[j]; items[j] = items[j + 1]; items[j + 1] = tmp

网上找了一张非常直观的动态演示了整冒泡排序的过程该图来自于 Sorting Algorithms - Bubble Sort

下面可以看到的更生动现实的排序执行过程

前面代码中的数字列表也是基于这个图来选择的。对冒泡排序大意的理解可以这样的

冒泡排序的每一步只作相邻两元素的交换
交换后的右端元素继续与下一个元素比较
大循环每次向左收缩一个元素
每次大循环都能把当前子列表中最大的元素冒泡到最右端

冒泡排序的时间复杂度是 O(n²)

冒泡排序效率最低效，存在过多的比较与交换，但它却有一个其他排序算法没有的好处，当某轮大循环(比如第一轮大循环) 中没有发生一次交换，那么说明排序已完成，可以立即返回。比如说对于有序集合，扫一遍就能完成 "排序"，效率就是 O(n)。看下面冒泡排序也能处理 100 百有序集合的 "排序"

def bubble_sort(items):
    exchanges = True
    for i in range(len(items)):
        if not exchanges:
            return
        exchanges = False
        for j in range(len(items) - i - 1):
            if items[j] > items[j + 1]:
                exchanges = True
                items[j], items[j + 1] = items[j + 1], items[j]


bubble_sort(list(range(1000000)))

def bubble_sort(items):

exchanges = True

for i in range(len(items)):

if not exchanges:

return

exchanges = False

for j in range(len(items) - i - 1):

if items[j] > items[j + 1]:

exchanges = True

items[j], items[j + 1] = items[j + 1], items[j]

bubble_sort(list(range(1000000)))

选择排序

相对于冒泡排序，选择排序我认为是一种更好理解最直截了当的排序方式，下面用 Python 代码演示

items = [6, 8, 3, 5, 9, 10, 7, 2, 4, 1]

length = len(items)
for i in range(length):
    for j in range(i+1, length):
        if items[i] > items[j]:
            items[i], items[j] = items[j], items[i]

print(items)