排序算法

排序算法太多了，有很多可能你连名字都没听说过，比如猴子排序、睡眠排序、面条排序等。我只讲众多排序算法中的一小撮，也是最经典的、最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、希尔排序

分析排序算法

在讲排序算法之前，可以先聊下如何分析排序算法。分析排序算法，要从几个方面入手呢？

这里不做详细描述，可以给大家列出几点作为参考：

排序算法的执行效率排序算法的内存消耗排序算法的稳定性冒泡排序

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。冒泡排序只会操作相邻的两个数据。每次比较都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换（升序就是小的元素在前面，降序反之）。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

冒泡排序算法的比较过程取列表前面两个元素进行比较，如果第一个比第二个大，就交换他们两个值的位置。然后向后移动一位，比较两个相邻的元素，从开始第一对到结尾的最后一对，这样做完，列表最后的元素就是整个列表最大的数字。针对所有的元素重复以上的步骤，除了最后一个。每次比较的元素会越来越少，直到没有任何一对数字需要比较。冒泡排序的演示

图片来自：冒泡排序

冒泡排序的分析

交换过程图示（第一次）：

接下来解释一下上面的比较过程。

54 与 26 比较，54 比 26 大，交换两个值的位置，经过交换后列表 [26, 54, 93, 17, 77, 31, 44, 55, 20]；继续向后比较，54 与 93 比较，54 比 93 小，不做处理，因为我们得到升序的列表；接下来 93 与 17 比较，93 比 17 大，交换两个值的位置，经过交换后的列表 [26, 54, 17, 93, 77, 31, 44, 55, 20]；接下来重复上面过程，最后 93 被交换到最后一个位置，得到列表的最大值。

这是第一次交换过程。

接下来将列表除了最后一个元素，重新比较大小，就会得到次大的元素。如果列表长度用 n 来表示，那么我们得到升序的列表就需要 n-1 次冒泡过程。

分析完冒泡排序的过程之后，我们用代码来实现一下。

冒泡排序代码实现

def bubble_sort1(li):    """冒泡排序"""    n = len(li) # n = 9    # 外层循环控制趟数    for j in range(n-1):        # 内层循环为当前 i 趟数,所需要比较的次数        for i in range(0, n-1-j):            if li[i] > li[i + 1]:                li[i], li[i + 1] = li[i + 1], li[i]        # 每一趟的变化        print(li)li = [54,26,93,17,77,31,44,55,20]bubble_sort(li)print(li)

实现起来还是比较简单的，接下来我们思考一下这个代码有没有优化的空间。

如果我传入的列表是 li = [9, 8, 7, 1, 2, 3, 4, 5, 6]，经过 3 次冒泡排序后，这个列表已经是一个有序的了。我们就不需要后续的比较了，想要实现这个效果我们可以优化一下代码。

def bubble_sort1(li):    """冒泡排序"""    n = len(li) # n = 9    # 外层循环控制趟数    for j in range(n-1):        # 加上一个 exchange，来控制内层循环        exchange = False        # 内层循环为当前 i 趟数,所需要比较的次数        for i in range(0, n-1-j):            # 9-1-0 = 8 i = 0            if li[i] > li[i + 1]:                li[i], li[i + 1] = li[i + 1], li[i]                exchange = True        # 每一趟的变化        print(li)        if not exchange:            return 

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

选择排序分析

第一次在列表中选出最大元素 93，将最大元素排到列表最后一个位置，在遍历循环找到次大的元素，如果列表长度用 N 表示，那么次大的元素将排到 n-2 的位置上，因为 n-1 是最大的元素的下标。

当然咱们也可以选出最小的元素放到列表的起始位置。

li = [54, 26, 93, 17, 77, 31, 44, 55, 20]        # 初始列表，可以把列表想象成两部分，前面是排序好的部分  后面是未排序的部分li = [17,      26, 93, 54, 77, 31, 44, 55, 20]        # 选出最小的元素放到列表起始位置li = [17, 20,     93, 54, 77, 31, 44, 55, 26]        # 接下来选出次小的元素放到列表的第二个位置

接下来可以实现一个简单版选择排序。

简单版选择排序

def select_sort_simple(li):    li_new = []    for i in range(len(li)):        min_val = min(li)       # min 操作时间复杂度 O(n)        li_new.append(min_val)        li.remove(min_val)      # remove 时间复杂度也是 O(n)    return li_newli = [54, 26, 93, 17, 77, 31, 44, 55, 20]print(select_sort_simple(li))

这种排序的缺点是：生成了一个新的列表，占用内存更多。

优化后的选择排序

循环找到最小位置，然后交换值：

li = [54, 26, 93, 17, 77, 31, 44, 55, 20]#      0   1   2   3  4    5   6   7   8# 循环一次,min = 3min = 0li[0], li[3] = li[3], li[0]li = [17,    26, 93, 54, 77, 31, 44, 55, 20]# 循环一次,min = 8min = 1li[1], li[8] = li[8], li[1]li = [17, 20,      93, 54, 77, 31, 44, 55,26]

代码实现：

def select_sort(li):    """选择排序"""    n = len(li)    # 需要进行 n-1 次选择操作    for i in range(n-1):         # 记录最小位置        min_index = i              # 从 min_index 位置到末尾选择出最小数据        for j in range(min_index, n):               if li[j] < li[min_index]:                   min_index = j                   # 循环结束,根据找到的 min_index 交换值        li[i], li[min_index] = li[min_index], li[i]        # 查看每次选择的结果        print(li)li = [54, 26, 93, 17, 77, 31, 44, 55, 20]select_sort(li)print(li)

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序过程分析

我们可以将列表中的元素分为两个区间，已排序和未排序，初始已排序的区间内只有一个元素，就是列表中的第一个元素。 插入排序大家可以想象成打牌过程中的摸牌，手里已经有了 2,4,5,10 这时候又摸到一张 7，你会放到哪里呢？是不是会把 7 这张牌，放到 5 和 10 之间（排除闭眼睛瞎摸的情况）。

如图所示，要排序的数据是 4,5,6,1,3,2，其中左侧为已排序区间，右侧是未排序区间。

插入排序演示

接下来，可以看下插入排序的演示：

图片来自：插入排序演示

插入排序代码实现

插入排序代码实现也有两种方式，两种实现方式思路都是一样的，只是在循环的方式不同。

第一种实现方式：

def insert_sort(li):    # 从第二个位置，即下标为 1 的元素开始向前插入    for i in range(1, len(li)):         # 从第 i 个元素开始向前比较，如果小于前一个元素，交换位置        for j in range(i, 0, -1):                   if li[j] < li[j - 1]:                      li[j], li[j - 1] = li[j - 1], li[j]        print(li)li = [54, 26, 93, 17, 77, 31, 44, 55, 20]insert_sort(li)print(li)

第二种实现方式：

def insert_sort(li):    n = len(li)    # 从右边的无序序列中取出多少个元素, 执行这样的过程    for j in range(1, n):        # j = [1, 2, 3, n-1]        # i 代表内层循环起始值        i = j        # 执行从右边的无序序列中取出第一个元素,即 i 位置的元素,将其插入到前面的正确位置中        while i > 0:            if li[i] < li[i-1]:                li[i], li[i - 1] = li[i - 1], li[i]                i -= 1            else:                break        print(li)li = [54, 26, 93, 17, 77, 31, 44, 55, 20]insert_sort(li)print(li)

希尔排序（Shell Sort）是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 DL.Shell 于 1959 年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

希尔排序过程

待排序的列表为

li = [54, 26, 93, 17, 77, 31, 44, 55, 20]

第一次选取 gap(就是步长) = 4，整个列表可以被分为下图这个样子：

第二次选取 gap = 2，整个列表可以被分为下图这个样子：

第三次选取 gap = 1，对整个列表直接进行插入排序。

希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序,最后一趟排序使得所有数据有序。

希尔排序代码实现

def shell_sort(li):    n = len(li)    gap = n // 2    while gap > 0:        # 插入算法,与普通的插入算法的区别就是 gap 步长        for j in range(gap, n):            i = j            while i > 0:                if li[i] < li[i-gap]:                    li[i], li[i-gap] = li[i-gap], li[i]                    i -= gap                else:                    break        # 缩短 gap 步长        gap = gap // 2

大家可以看到，这个代码与插入排序的区别就是 gap 的值。所以说希尔排序也是插入排序的演变。

快速排序

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

首先设定一个分界值，通过该分界值将数组分成左右两部分。将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

快速排序流程引用自：快速排序流程。

快速排序的分析

待排序的列表为：

li = [54, 26, 93, 17, 77, 31, 44, 55, 20]

初始状态，将列表第一个元素选出来，当做一个基准值，然后借助两个指针，low 和 high，low 指向基准元素，high 指向最后一个元素。来比较 low 和 high 两个指针所指向的元素大小。

如果 low 指向的元素比 mid 小，则继续往后移动 low。如果 high 指向的元素比 mid 小，则将 high 指向的元素，交换到 low 所指向的位置。如果 low 指向的元素比 mid 大，则将 low 指向的元素，交换到 high 所指向的位置。如果 high 指向的元素比 mid 大，则继续往前移动 high。

经过多次移动，在这个基准值的右侧都是比基准值大的，在基准值的左侧都是比基准值小的。

然后在基准值左侧的值则继续上述过程。右侧也是同样的过程。这里大家不难想到，方法都是一样的，只是数据规模变小了，这里肯定会用到递归。

快速排序代码实现

def quick_sort(li, start, end):    """快速排序"""    # 递归的退出条件    if start >= end:        return    # 设定起始元素为要寻找位置的基准元素    mid = li[start]    # low 为序列左边的由左向右移动的游标    low = start  # 0    # high 为序列右边的由右向左移动的游标    high = end  # len(li)-1    while low < high:        # 如果 low 与 high 未重合，high 指向的元素不比基准元素小，则 high 向左移动        while low < high and li[high] >= mid:            high -= 1        # 将 high 指向的元素放到 low 的位置上        li[low] = li[high]        # 如果 low 与 high 未重合，low 指向的元素比基准元素小，则 low 向右移动        while low < high and li[low] < mid:            low += 1        # 将 low 指向的元素放到 high 的位置上        li[high] = li[low]    # [20, 26, 44, 17, 31, 54, 77, 55, 93]    # 退出循环后，low 与 high 重合，此时所指位置为基准元素的正确位置    # 将基准元素放到该位置    li[low] = mid    # 对基准元素左边的子序列进行快速排序    quick_sort(li, start, low - 1)    # 对基准元素右边的子序列进行快速排序    quick_sort(li, low + 1, end)li = [54, 26, 93, 17, 77, 31, 44, 55, 20]quick_sort(li, 0, len(li) - 1)print(li)

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并列表。

将数组（在其他语言里面叫数组,但是在 Python 里面叫列表）分解到不可分割（列表长度为 1），然后合并两个有序数组，合并的基本思路是比较两个数组的最前面的数，用两个指针分别指向比较的两个的数组最前面，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

归并排序分析

待排序的列表为

li = [54, 26, 93, 17, 77, 31, 44, 55, 20]

首先将列表拆分为最小。

第一次拆分将列表分为两部分，拆分方式为 len(li) // 2；第二次将上面拆分为两部分的列表，继续拆分。直到不能拆分为止。

这里也是拆分的方式一样，数据规模在变小，同样可以用递归的方式来做。

拆分为不可拆分的列表之后，就要进行合并。

合并会借助到两个指针 left 与 right，将 left 与 right 所指的元素做比较，取出较小的值，将列表进行合并。

归并排序的演示

图片来自：归并排序

归并排序的代码实现

def merge_sort(li):    # 如果列表长度小于 1,不在继续拆分    if len(li) <= 1:        return li    # 二分分解    mid_index = len(li) // 2    left = merge_sort(li[:mid_index])    right = merge_sort(li[mid_index:])    # 将两个有序的子序列合并为一个新的整体：合并    # return merge(left, right)    l_index, r_index = 0, 0    result = []    while l_index < len(left) and r_index < len(right):        if left[l_index] < right[r_index]:            result.append(left[l_index])            l_index += 1        else:            result.append(right[r_index])            r_index += 1    # 左右两边走到头,将剩下的元素拼接到一起    result += left[l_index:]    result += right[r_index:]    return result