掌握了排序算法就不会失业.jpg

1. 前言

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的八大排序算法，他们之间关系如下：

avatar

它们的性能比较：

avatar

下面，利用 Python 分别将他们进行实现。

2. 直接插入排序

2.1. 算法思想

插入排序示意图

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

2.2. 算法步骤

  1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

2.3. 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# -------------- 直接插入排序 ------------------
def insert_sort(L):
    # 遍历数组中的所有元素，其中 0 号元素默认已排序，因此从 1 开始
    for x in range(1, len(L)):
        # 将该元素与已排序好的前序数组依次比较，如果该元素小，则交换
        # range(x-1, -1, -1): 从 x-1 倒序循环到 0
        for i in range(x-1, -1, -1):
            # 判断：如果符合条件则交换
            if L[i] > L[i+1]:
                L[i], L[i+1] = L[i+1], L[i]

3. 希尔排序

3.1. 算法思想

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序是基于直接插入排序的以下两点性质而提出改进方法的：

  • 直接插入排序在对几乎已经排好序的数据操作时，效率高，可以达到线性排序的效率
  • 但直接插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

3.2. 算法步骤

  1. 选择一个增量序列 $t_1, t_2, \dots , t_k$, 其中 $t_i > t_{i+1}, t_k = 1$；
  2. 按增量序列个数 $k$，对序列进行 $k$ 趟排序；
  3. 每趟排序，根据对应的增量 $t_i$，将待排序列分割成若干长度为 $m$ 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

avatar

3.3. 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# -------------- 希尔排序 ---------------
def insert_shell(L):
    # 初始化gap值，此处利用序列长度的一半为其赋值
    gap = (int)(len(L)/2)
    # 第一层循环：依次改变gap值对列表进行分组
    while (gap >= 1):
        # 下面，利用直接插入排序的思想对分组数据进行排序
        # range(gap, len(L)): 从gap开始
        for x in range(gap, len(L)):
            # range(x-gap, -1, -gap)：从x-gap开始与选定元素开始倒序比较，每个比较元素之间间隔gap
            for i in range(x-gap, -1, -gap):
                # 如果该组当中两个元素满足交换条件，则进行交换
                if L[i] > L[i+gap]:
                    L[i], L[i+gap] = L[i+gap], L[i]
        # gap折半
        gap = (int)(gap/2)

4. 简单选择排序

4.1. 算法思想

简单选择排序的基本思想：比较 + 交换。

4.2. 算法步骤

  1. 从待排序序列中，找到关键字最小的元素，存放在待排序序列的起始位置；
  2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
  3. 从余下的 $N - 1$ 个元素中，找出关键字最小的元素，重复 1、2 步，直到排序结束。

4.3. 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# -------------- 简单选择排序 ----------------
def select_sort(L):
    # 依次遍历序列中的每一个元素
    for x in range(0, len(L)):
        # 将当前位置的元素定义为比伦循环当中的最小值
        minmum = L[x]
        # 将该元素与剩下的元素依次比较寻找最小元素
        for i in range(x+1, len(L)):
            if L[i] < minmum:
                L[i], minmum = minmum, L[i]
        L[x] = minmum

5. 堆排序

5.1. 堆的概念

堆：本质是一种数组对象。特别重要的一点性质：任意的叶子节点小于 (或大于) 它所有的父节点。对此，又分为大顶堆和小顶堆，大顶堆要求节点的元素都要大于其孩子，小顶堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求。 利用堆排序，就是基于大顶堆或者小顶堆的一种排序方法。下面，我们通过大顶堆来实现。

5.2. 基本思想

堆排序可以按照以下步骤来完成：

  1. 首先将序列构建称为大顶堆；这样，位于根节点的元素一定是当前序列的最大值 avatar

  2. 取出当前大顶堆的根节点，将其与序列末尾元素进行交换；此时：序列末尾的元素为已排序的最大值；由于交换了元素，当前位于根节点的堆并不一定满足大顶堆的性质

  3. 对交换后的前 $n-1$ 个序列元素进行调整，使其满足大顶堆的性质； avatar

  4. 重复 2、3 步骤，直至堆中只有 1 个元素为止

5.3. 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#--------------------- 堆排序 ----------------------
#************* 获取左右叶子结点 ***************
def LEFT(i):
    return 2*i + 1
def RIGHT(i):
    return 2*i + 2
#************ 调整大顶堆 ***************
# L：待调整序列
# length：序列长度
# i: 需要调整的结点
def adjust_max_heap(L, length, i):
    # 定义一个int值保存当前序列最大值的下标
    largest = i
    # 执行循环: 1.寻找最大值的下标；
    #           2.最大值与父节点交换
    while(1):
        # 获得序列左右叶子结点的下标
        left, right = LEFT(i),RIGHT(i)
        # 当左叶子节点的下标小于序列长度并且左叶子节点的值大于父节点时，将左叶子节点的下标赋值给largest
        if (left < length) and (L[left] > L[i]):
            largest = left
            print('左叶子节点')
        else:
            largest = i
        # 当右叶子节点的下标小于序列长度并且右叶子节点的值大于父节点时，将右叶子节点的下标赋值给largest
        if (right < length) and (L[right] > L[largest]):
            largest = right
            print('右边子节点')
        # 如果 largest 不等于 i，说明当前的父节点不是最大值，需要交换值
        if (largest != i):
            L[i], L[largest] = L[largest], L[i]
            i = largest
            print(largest)
            continue
        else:
            break
#************* 建立大顶堆 *************
def build_max_heap(L):
    length = len(L)
    for x in range((int)((length-1)/2), -1, -1):
        adjust_max_heap(L, length, x)
#************* 堆排序 *************
def heap_sort(L):
    # 先建立大顶堆，保证最大值位于根节点，并且父节点的值大于叶子节点
    build_max_heap(L)
    # i：当前堆中序列的长度，初始化为序列的长度
    print(L)
    i = len(L)
    # 执行循环：1.每次取出堆顶元素置于序列的最后(len-1, len-2, len-3...)
    #           2.调整堆，使其继续满足大顶堆的性质，注意实时修改堆中序列的长度
    while(i > 0):
        L[i-1], L[0] = L[0], L[i-1]
        # 堆中序列长度减 1
        i = i - 1   # Python没有自加自减运算符！
        # 调整大顶堆
        adjust_max_heap(L, i, 0)

6. 冒泡排序

6.1. 基本思想

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

6.2. 算法步骤

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

6.3. 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#---------------- 冒泡排序 -------------------
def bubble_sort(L):
    length = len(L)
    # 序列长度为 length 时，需要执行 length-1 轮交换
    for x in range(1, length):
    # 对于每一轮交换，都将序列当中的左右元素进行比较
    # 每轮交换中，由于序列最后的元素一定是最大的，因此每轮循环到序列未排序的位置即可
        for i in range(0, length - x):
            if L[i] > L[i+1]:
                L[i], L[i+1] = L[i+1], L[i]

7. 快速排序

7.1. 算法思想

快速排序的基本思想：

  1. 从序列当中选择一个基准数 (pivot)，在这里我们选择序列当中第一个数最为基准数
  2. 将序列当中的所有数依次遍历，比基准数大的位于其右侧，比基准数小的位于其左侧
  3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序，重复步骤 1、2，直到所有子集当中只有一个元素为止。

7.2. 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#--------------- 快速排序 -------------------
# L: 待排序的序列
# start：序列起始 index
# end：序列末尾 index
def quick_sort(L, start, end):
    if start < end:
        i, j, pivot = start, end, L[start]
        while (i < j):
            # 从右向左找第一个小于pivot的值
            while (i < j) and (L[j] >= pivot):
                j = j - 1
            # 将小于pivot的值移到左边
            if(i < j):
                L[i] = L[j]
                i = i + 1
            # 从左到右找第一个大于pivot的值
            while (i < j) and (L[i] < pivot):
                i = i + 1
            # 将大于pivot的值移到右边
            if (i < j):
                L[j] = L[i]
                j = j - 1
        # 循环结束后，说明 i=j，此时左边的值全都小于pivot,右边的值全都大于pivot
        # pivot的位置移动正确，那么此时只需对左右两侧的序列调用此函数进一步排序即可
        # 递归调用函数：依次对左侧序列：从 start 到 i-1
        #                     右侧序列：从 i+1 到 end
        L[i] = pivot
        # 左侧序列继续排序
        quick_sort(L, start, i-1)
        # 右侧序列继续排序
        quick_sort(L, i+1, end)

8. 归并排序

8.1. 算法思想

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型的应用。它的基本操作是：将已有的有序子序列合并，达到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

归并排序其实要做两件事：

  • 分解—-将序列每次折半拆分
  • 合并—-将划分后的序列段两两排序合并

因此，归并排序实际上就是两个操作，拆分+合并

如何分解？

在这里，我们采用递归的方法，首先将待排序列分成 A、B 两组；然后重复对 A、B 序列分组；直到分组后组内只有一个元素，此时我们认为组内所有元素有序，则分组结束。

如何合并？

$L[first \dots mid]$ 为第一段，$L[mid+1 \dots last]$ 为第二段，并且两端已经有序，现在我们要将两端合成达到 $[first \dots last]$ 并且也有序。

  1. 首先依次从第一段与第二段中取出元素比较，将较小的元素赋值给 $temp[]$
  2. 重复执行上一步，当某一段赋值结束，则将另一段剩下的元素赋值给 $temp[]$
  3. 此时将 $temp[]$ 中的元素复制给 $L[]$，则得到的 $L[first \dots last]$ 有序

8.2. 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#---------------- 归并排序 -------------------
#*********** 合并函数 **************
def mergearray(L, first, mid, last, temp):
    i, j, k = first, mid+1, 0
    # 当左右两边都有数时进行比较，取较小的数
    while (i <= mid) and (j <= last):
        if L[i] <= L[j]:
            temp[k] = L[i]
            i = i + 1
            k = k + 1
        else:
            temp[k] = L[j]
            j = j + 1
            k = k + 1
    # 如果左边序列还有数
    while(i <= mid):
        temp[k] = L[i]
        i = i + 1
        k = k + 1
    # 如果右边序列还有数
    while(j <= last):
        temp[k] = L[j]
        j = j + 1
        k = k + 1
    # 将temp当中该段有序元素赋值给 L 待排序序列使之部分有序
    for x in range(0, k):
        L[first + x] = temp[x]

#************ 分组函数 *************
def merge_sort(L, first, last, temp):
    if first < last:
        mid = (int)(first + (last - first)/2)
        # 使左边序列有序
        merge_sort(L, first, mid, temp)
        # 使右边序列有序
        merge_sort(L, mid+1, last, temp)
        # 将两个有序序列合并
        mergearray(L, first, mid, last, temp)

#************ 归并排序 **************
def merge_sort_array(L):
    # 声明一个长度为len(L)的空列表
    temp = len(L)*[None]
    merge_sort(L, 0, len(L)-1, temp)

9. 基数排序

9.1. 算法思想

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串 (比如名字或日期) 和特定格式的浮点数，所以基数排序也不是只能使用于整数。

通过序列中各个元素的值，对排序的 $N$ 个元素进行若干趟的分配与收集来实现排序。

  • 分配：我们将 $L[i]$ 中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中
  • 收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列 $L[]$
  • 对新形成的序列 $L[]$ 重复执行分配和收集元素中的十位、百位…直到分配完该序列中的最高位，则排序结束

9.2. 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#------------------- 基数排序 --------------------
# 确定排序的趟数
# 排序的顺序跟序列中最大数的位数相关
def radix_sort_nums(L):
    maxNum = L[0]
    # 寻找序列中的最大数
    for x in L:
        if maxNum < x:
            maxNum = x
    # 确定序列中最大元素的位数
    times = 0
    while(maxNum > 0):
        maxNum = (int)(maxNum/10)
        times = times + 1
    return times

# 找到num从低到高第 pos 位的数据
def get_num_pos(num, pos):
    return ((int)(num/(10**(pos-1))))%10

# 基数排序
def radix_sort(L):
    # 存放各个桶的数据统计值
    count = 10*[None]
    # 暂时存放排序结果
    bucket = len(L)*[None]
    # 从低位到高位依次循环
    for pos in range(1, radix_sort_nums(L)+1):
        # 置空各个桶的数据统计值
        for x in range(0, 10):
            count[x] = 0
        # 统计当前位数（个位，十位，百位...）的元素数目
        for x in range(0, len(L)):
            # 统计各个桶将要装进去的元素个数
            j = get_num_pos(int(L[x]), pos)
            count[j] = count[j] + 1
        # count[i] 表示第 i 个桶的右边界索引
        for x in range(1, 10):
            count[x] = count[x] + count[x-1]
        # 将数据依次装入桶中
        for x in range(len(L)-1, -1, -1):
            # 求出元素第 k 位的数字
            j = get_num_pos(L[x], pos)
            # 放入对应的桶中，count[j]-1 是第 j 个桶的右边界索引
            bucket[count[j]-1] = L[x]
            # 对应桶的装入数据索引 -1
            count[j] = count[j] - 1
        # 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表
        for x in range(0, len(L)):
            L[x] = bucket[x]