排序算法 | Python 实现

使用 Python 语言实现常见的几个排序算法，并且给出时间复杂度和空间复杂度，记录学习。

参考：极客时间：数据结构与算法之美

冒泡排序

每次都与相邻的两个元素进行比较，看是否满足大小关系，将不满足大小关系的两者进行交换顺序。

def bubble(arr: list):
    n = len(arr)

    for i in range(n):
        # 在每一轮下来，都可以把最大的元素移动到最后去
        for j in range(0, n-i-1):
            # 每次比较相邻的两个元素，把大的元素交换到后面去
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

每进行一轮排序，就会将其中最大（或最小）的元素移动到顶部，之后进行n轮之后，就可以将所有的元素排序，也正因为如此，算法所需的时间复杂度为 ，最好时间复杂度就是原本的数据就已经排序完成，只要扫描一边就是，也就是 ，并且没有使用别的内存空间来保存临时变量，所以空间复杂度为 ，是原地排序算法。在排序的时候，对于相同的元素不进行交换，也就是相同元素在排序之后先后顺序不变，所以是稳定的排序算法。

插入排序

插入排序分为已排序区间和未排序区间，首先，遍历未排序区间的元素，依次与排序区间的元素进行比较，直到遇到比该元素小的元素，将其插入到后面。每次都需要进行数组的移动操作。

def insertionSort(arr):
    for i in range(1, len(arr)):
        # 选择当前的位置，左边的部分是已经排序完成的，右边的是未排序的
        key = arr[i]
        # 从后面的元素开始
        j = i - 1
        # 判断选择的元素是否比前面排好的元素小
        while j >= 0 and key < arr[j]:
            # 如果当前的元素j比前面排序好的元素小，就一直往前移动
            arr[j + 1] = arr[j]
            j -= 1
        # 插入到相应的已经排序完成的队列上
        arr[j + 1] = key

首先，在排序的过程中，没有识别额外的空间，空间复杂度为 ，属于原地排序算法。如果遇到相同的元素，可以将后面的元素放到后面去，这样就不改变排序前后相同元素的位置，所以是稳定的排序算法。如果数组是有序的，只需要循环遍历一遍，不需要进行插入操作的话，时间复杂度就为 ，最坏情况时间复杂度与冒泡排序类似，每次都需要比较移动数组元素，所以最坏时间复杂度为 。

选择排序

选择排序与插入排序很像，一样有已排序区间和未排序区间，与插入排序不同的是，选择排序在未排序区间选择一个最小（或最大）的元素，与已排序区间的后一个元素交换，实现排序。

def selectionSort(arr: list):
    for i in range(len(arr)):
        # 每次以当前位置为基准
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[min_index] > arr[j]:
                # 每次都找到后面最小的那个元素
                min_index = j
        # 与基准交换位置
        arr[i], arr[min_index] = arr[min_index], arr[i]

没有使用额外的空间，空间复杂度为 ，属于原地排序算法。因为每次都需要进行两轮的判断，所有最好最坏的时间复杂度都为 。不过在每次进行交换的时候，有可能会打乱相同元素的先后顺序，属于不稳定算法，例如：5，3，5，2 进行排序，首先算到最小的元素 2 ，与第一个元素 5 交换顺序，此时就已经打乱了相同元素 5 的先后顺序了。

归并排序

归并排序采用分治的思想，每次都将要排序的数组分成两部分，之后对这两部分进行排序，获得已排序好的两个子数组，最后对这两个已经排序好的子数组再进行排序，最后完成排序操作。

def mergeSort(arr, l, r):
    if l < r:
        m = int((l + (r - 1)) / 2)
        # 分治的思想，划分为两部分
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        # # 递归到这里表示两边的已经排序完成，接下来对两边的元素进行合并
        merge(arr, l, m, r)

在排序好的两个子数组中每次都拿出较小（较大）的一个元素，最后组合在一起完成排序操作。

def merge(arr, l, m, r):
    # 创建临时数组
    # 拷贝数据到临时数组 arrays L[] 和 R[]
    L = arr[l:m+1]
    R = arr[m+1:r+1]

    # 归并临时数组到 arr[l..r]
    i = 0  # 初始化第一个子数组的索引
    j = 0  # 初始化第二个子数组的索引
    k = l  # 初始归并子数组的索引

    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            # 左边小就赋值左边的元素
            arr[k] = L[i]
            i += 1
        else:
            # 否则就添加右边的元素
            arr[k] = R[j]
            j += 1
        k += 1

    # 拷贝 L[] 的保留元素
    if i < len(L):
        arr[k:r+1] = L[i:]

    # 拷贝 R[] 的保留元素
    if j < len(R):
        arr[k:r+1] = R[j:]

因为算法采用的写法是在原来的数组上进行修改的方式来写的，首先的操作就是拷贝数组两边的数据，之后循环对比两个子数组的首位的大小，依次添加到原来的数组 arr 上，最后，如果有剩余的子数组未添加的话，就直接添加在 arr 数组的末尾。

首先来说，在排序的过程中即使两个相同的元素在两个子数组中，或者在同一侧的子数组进行排序操作，因为先判断左半边的关系，没有改变相同元素的先后顺序，所以归并排序是一个稳定的排序算法。不过在排序的过程中，申请了额外的空间来保存两个子数组的关系，空间复杂度为 ，所以不是原地排序算法。

对于时间复杂度来说，不管是最好还是最坏，他们进行的操作是一样的，也就是最好和最坏时间复杂度是相同的。对于时间复杂度的计算方式可以采用递归的思想。首先，merge 函数因为只是对两个已排序的子数组的进行选择排序，所以该函数的时间复杂度为 量级。那总的时间复杂度：T(n) 就可以看作是两个子数组的时间复杂度加上最后进行合并的时间复杂度： ，并且当 n = 1 时，T(1) = C （常数时间）。

一层层展开可以得到：

在一步步进行分解的时候，最终会对 T(1) 进行计算，当计算到 T(1) 的时候，即 得到 ，也就是 ，将这个 k 值带入公式得： ，所以最终得到的时间复杂度为 。

参考：

• 排序算法之 快速排序 及其时间复杂度和空间复杂度

快速排序

有点类似于归并排序，同样使用分治的思想。首先，选取一个分区点，将剩余元素依据分区点的大小放在分区点两侧，例如：5，1，4，9，7，3 中选取 4 作为分区点，对于第一轮来说，将小于 4 的元素放到分区点的左边，将大于 4 的元素放到分区点的右边，最终第一轮结束变成：1，3，4，5，9，7 。以分区点 4 为划分，之后分别对左半边的元素和右半边的元素进行同样的操作，最后就实现了排序。

def quickSort(arr, l, r):
      if l < r:
        # 获取分区点的位置，并且依据分区点将数组划分
        pi = partition(arr, l, r)
        # 分治的思想，分开左右两边
        quickSort(arr, l, pi - 1)
        quickSort(arr, pi + 1, r)

而对于查找分区点的位置并且划分的话，可以以最右边的元素为分区点，首先定义一个起始点索引，之后遍历一遍元素，将小于分区点的元素与索引下标的元素交换顺序，同时索引向后移动一位，最后再将分区点与起始点后面的一个元素交换顺序，这样就不会使用额外的空间实现分区操作。

def partition(arr, l, r):
    i = l - 1  # 最小元素索引
    pivot = arr[r]

    for j in range(l, r):

        # 当前元素小于或等于 pivot
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[r] = arr[r], arr[i + 1]
    return i + 1

正如上面所说，在进行分区的时候没有使用额外的空间，所以空间复杂度为 ，是原地排序算法。不过在进行分区操作交换顺序的时候会改变相同元素的先后顺序，例如：4，3，4，1，2 中，在以 2 为分区点的时候，元素 1 会与第一个 4 交换顺序，所以就改变了 4 的先后顺序，所以不是一个稳定的排序算法。

快速排序的时间复杂度和归并排序一样，平均时间复杂度都是 ，不过最大时间复杂度会因为分区的关系上升到 级，例如每次选择的分区点都是当前分区中最大的元素，这样就会每次都遍历 n/2 个元素，并且进行 n 次。所以对于找分区点也是一个重点，可以采用随机选择的方式来平摊。

总结