经典排序算法的解析和Python实现

十二月 06, 2019  /  Pp

并整理排序算法的资料。如有错误,请多包涵,我会继续进步的。

常见排序算法可以分为两大类:

比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。

非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

算法复杂度

image.png

上述内容引用自这篇文章:十大经典排序算法(动图演示)


本文中的排序均按照“左小右大”的顺序进行排列:
  1. 冒泡排序
  2. 选择排序
  3. 插入排序
  4. 快速排序
  5. ......(待更新)

1. 冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

原理
  • 一直把相邻的两个数比大小,大的那个移到右边。
  • 从左往右遍历,若发现所在点大于右边,则交换两点,相当于把较大值放在右边;
  • 容易发现,每完成一次遍历,则被遍历的点中的最大值会被多次移动,最终到达左右侧;
  • 每次遍历完成,都有一个目前的最大值移动到右侧,这些位置也是它们最终的位置,故下次遍历碰到它们即停止;
  • 所以可以分为“未排序组”(淡蓝色)和“已排序组”(橙色);
  • 重复遍历,知道排序完成。

冒泡排序

代码:
def bubble_sort(arr):
    for i in range(len(arr)-1):   # i表示遍历的次数,总共需要n-1次
        for j in range(len(arr)-1-i):   # j表示“未排序组”中需要比较的次数,需要n-1-i次
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

for i in range(len(arr)-1):假设有n个数字,已知每次遍历都会为一个最大值排好序,因此共需要遍历n-1次即可全部排好。

for j in range(len(arr)-1-i):单次遍历任务中,假设还有m个数字未排好序,即“未排序组”数量为m,则需要比较多少次呢?m-1次。联系上i,i可表示已执行完毕的遍历次数,也等于已排序完成的数字个数,那么未排序的数量m == n - i,即m == len(arr) - i。

arr[j], arr[j+1] = arr[j+1], arr[j]:所在点与右侧点交换值,要注意这是Python的语法糖,实际上进行了多次赋值操作*,在插入排序**中这个理解挺重要的。

*通常两个变量交换需要3步赋值操作,我用Python表示如下:

a = 1
b = 2

tem = b
b = a
a = tem

但Python有个相关的语法糖,只要a, b = b, a即可交换。并且二者背后的操作并非完全相同。

在这篇文章中“Python面试之交换变量值”,可以看出Python对这语法糖进行了优化,其字节码稍有改动。

image.png

经我实际测试,a, b = b, a的速度更快,但差距不大:

import time
import random

n = 10**7

data = [random.randint(1, 1000) for i in range(n)]
start = time.time()
for i in range(len(data)-1):
    data[i], data[i+1] = data[i+1], data[i]
print(f'>> 01: {time.time()-start}')

data = [random.randint(1, 1000) for i in range(n)]
start = time.time()
for i in range(len(data)-1):
    tem = data[i+1]
    data[i+1] = data[i]
    data[i] = tem
print(f'>> 02: {time.time()-start}')

---
>> 01: 2.7299811840057373
>> 02: 3.0289833545684814

2. 选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

原理:
  • 每次把最小的数移动到左边。
  • 取第一个数作为参考,对其右边的数进行遍历,如果存在小于参考数的,就先将其索引记录下来;
  • 继续往右,若发现存在一个数比刚才记录的数字还小的,就用更小的索引替代记录值;
  • 直到向右的遍历完成,此时把记录的最小数与第一个参考数交换;
  • 此时索引一的数必然是数组中最小的,下面从索引二开始作为参考,遍历其右边的数,步骤方法同上,直到完成倒数第二个参考数,即完成排序。

选择排序

代码:
def selection_sort(arr):
    for i in range(len(arr)-1):   # i表示参考数位置
        min_index = i
        for j in range(i+1, len(arr)):   # j表示寻找小于参考数的数的位置
            if arr[min_index] > arr[j]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

for i in range(len(arr)-1):i表示参考数索引。

min_index = i:min_index这个变量是用来存储“比参考数小的最小值”的索引,初始值为i。

for j in range(i+1, len(arr)):i表示参考数,则j表示向右寻找比i更小数的索引。

if min_index != i:这个判断可加可不加,反正for loop执行完,此时min_index里存的必然是小于或等于arr[i]的最小值,if语句表示,如果等于i就不进行互换了,省掉一步。


这里也给出另一版的选择排序,区别在于不存储min_index、不判断哪个才是小于arr[i]的最小值,而是j遍历到哪个位置,只要比arr[j] < arr[i],就执行互换。

最终结果是一样的,只是a, b = b, a互换操作比if判断更费时,效率更低一些。(优点在于好记)

def selection_sort_bad(arr):
    for i in range(len(arr)-1):
        for j in range(i+1, len(arr)):
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]
    return arr

3. 插入排序

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

原理:
  • 跟打扑克抽牌一样,左边是已经排好顺序的,从右边选一张,看它比哪张大,就放那张右边。
  • 第一个数认为是排好的,从第二个数开始往其中“插牌”;
  • 比如如果第三个数小于第二个数,大于第一个数,就放第一数右边,依此类推;
  • 如果已经有m个数排好顺序了,取第m+1数,从右往左比较大小,发现它“比第k+1数小,比第k数大”,则应把它放在第k+1位;
  • 有点像加塞,得先把后面的人都挪一位,才能挤进去;

插入排序

代码:
def insertion_sort(arr):
    for i in range(1, len(arr)):   # i表示准备“插入”有序牌组中的牌
        tem = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > tem:   # j表示往前搜索比arr[i]小的数的索引
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = tem
    return arr

for i in range(1, len(arr)):从第二项开始“理牌”。

tem = arr[i]:用tem把arr[i]的值存起来,因为后面arr[i]会被别的值替换掉。

while j >= 0 and arr[j] > tem:在i之前的项中逐个比较,一旦找到了比tem小与或等于的,就把tem值插到其后面,并且原先的值都往后移一位。但是这里用的while是反向操作,如果找到了比tem大的,则表明这个值迟早得向后平移,索性现在就移了。

arr[j+1] = tem:这一步是当while结束才执行的,while何时结束呢,两种情况:找到比tem小的值arr[j],于是把tem赋值给arr[j+1],而其他移位工作在while中已经完成了;或者从头到尾,直到j == -1,仍不满足比tem小(或相等),意味着tem是目前最小的数,当然得排第一咯,把tem赋值给arr[j+1]即arr[0]。


上述是标准写法,我再提供多个版本的插入排序供参考。(但愿不要存在bug)

04版本是改写,for+while改为for+for,是等效的。经简单测试,执行赋值操作的步数相同,效率也差不多。

def insertion_sort_04(arr):
    for i in range(1, len(arr)):
        tem = arr[i]
        for j in range(i-1, -1, -1):
            if tem < arr[j]:
                arr[j+1] = arr[j]   # 还没找到小于tem的,arr[j]往后移
            else:
                arr[j+1] = tem   # 找到了小于等于tem的数!!tem插入到arr[j+1],终止for
                break
        else:
            arr[0] = tem   # 如果for顺利执行完,意味着没有比tem小的数,tem应该排在最前面
    return arr


01版本的语意更易理解,用到了Python中的list的内建方法(暂时还没研究源码,留个坑..),比较好理解。 奇怪的是,这个的效率竟然比标准的高!

def insertion_sort_01(arr):
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[i] < arr[j]:   # j是已排序部分的序号,从左往右找,如果找到比arr[i]大的...
                arr.insert(j, arr[i])   # ...则把arr[i]插入到这里,其他值后移一位...
                arr.pop(i+1)   # ...并删除原i位数字
                break
    return arr

03版本跟上面相仿,用list的切片特性,取代上述的insert/pop方法,效率中等,也比标准的高。

def insertion_sort_03(arr):
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[i] < arr[j]:
                arr = arr[:j] + [arr[i]] + arr[j:i] + arr[i+1:]
                break
    return arr

4. 快速排序

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

原理:
  • 属于分治法的一种实现,递归地对将数列分为子串,每个子串都排列正确,再合并一起即完成排序。
  • 分串依据:归并排序是将数列的长度二分为子串;快速排序则是通过与基准数比大小,分为大、小两个子串;
  • 基准数的选择可以是任意的,比如选择串或子串中的第一个元素;

快速排序

代码:
def quick_sort(data):
    stone = data[0]
    i = 1
    j = len(data)-1
    if len(data) > 1:
        while j > i:
            if data[j] <= stone:
                if data[i] > stone:
                    data[j], data[i] = data[i], data[j]
                else:
                    i += 1
            else:
                j -= 1
        if data[j] <= stone:
            data[0], data[j] = data[j], data[0]
        return quick_sort_02(data[:j]) + quick_sort_02(data[j:])
    else:
        return data

大家可以在这里看到详细解释: 理解快速排序算法

02版本是另一种解法,我觉得写起来顺手一些,但会更浪费空间(一直在创建新的数组),效率略低于上面这种:

def quick_sort_02(arr):
    pivot = 0
    if len(arr) > 1:
        small_arr = []
        big_arr = []
        for i in range(pivot+1, len(arr)):
            if arr[i] <= arr[pivot]:
                small_arr.append(arr[i])
            elif arr[i] > arr[pivot]:
                big_arr.append(arr[i])
        return quick_sort_01(small_arr) + [arr[pivot]] + quick_sort_01(big_arr)
    else:
        return arr

效率比较:

import time
import random

n = 10**7   # 数组规模
data = [random.randint(1, 10000) for i in range(n)]

data01 = copy.deepcopy(data)
start = time.time()
quick_sort(data01)
print(f'>> 01: {time.time()-start}')

data02 = copy.deepcopy(data)
start = time.time()
quick_sort_01(data02)
print(f'>> 02: {time.time()-start}')

---
# n == 10**7
>> 01: 916.2235355377197
>> 02: 1072.9130353927612

# n == 10**6
>> 01: 11.828999280929565 
>> 02: 13.462998151779175

# n == 10**5
>> 01: 0.4830021858215332
>> 02: 0.4949791431427002

copy.deepcopy(data):这里深拷贝的目的是希望公平竞争,对同一个随机数组进行排序比赛。

那为啥不直接都代入data呢?比如quick_sort(data)quick_sort_01(data)呢?

这是因为Python的一个坑:函数传参传递的是对象的引用(或说指针),如果是可变对象(如list、dict),那可变对象内存储的元素对象(的指针)是与外部实参共享的。若外部data改变了内部元素,则函数内元素的引用也会改变,反之亦然。

打个比方,函数传参就像浅复制,如果实参是一个旧篮子(list),函数内的形参就是一个长得一样的新篮子,但新篮子里装的东西却是外面旧篮子的!新、旧篮子里的东西是共享的!你说气不气。

举个栗子,quick_sort(data)中传递了一个data,结构是list。但list中的值是与外部共享的,等quick_sort函数一通排序后,发现外部data里的值都被排序了,等quick_sort_01再调用时data已发生改变,比赛就不太公平了。

这里的解决方案就是copy.deepcopy,可以把data包括内部的元素都复制一份(如data01),这一份复制是与data完全无关联的,改变data01不会影响data,反之亦然。

未完待续...咕咕咕