数据结构学习笔记---经典排序

排序

Word count: 4.3kReading time: 16 min

 2020/03/29   Share

学习自极客时间的《数据结构与算法之美》作者：王争

排序

排序的内存消耗

原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。

排序算法的稳定性

仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，我们还有一个重要的度量指标，稳定性。
经过某种排序算法排序之后，如果两个相同元素的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。

1. 冒泡排序（Bubble Sort）

冒泡排序

def BubbleSort(arr):
    lenght = len(arr)
    # 这个循环负责设置冒泡排序进行的次数
    for i in range(lenght):
        # 这个循环负责控制比较的元素个数
        for j in range(lenght - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j + 1], arr[j] = arr[j], arr[j + 1]

    return arr

冒泡排序的优化

可以看到,数组中本来有一些元素已经是有序的, 但是还是进行了多余的比较,所以我们设置一个标志,如果没有数据交换,则证明数组已经有序,跳出循环。

def BubbleSort(arr):
    lenght = len(arr)
    # 有序标记，每一轮的初始是true，用于判断元素间是否需要交换
    isSorted = True
    # 这个循环负责设置冒泡排序进行的次数
    for i in range(lenght):
        # 这个循环负责控制比较的元素个数
        for j in range(lenght - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j + 1], arr[j] = arr[j], arr[j + 1]
                # 有交换行为设为 False
                isSorted = False
        # 无交换行为（isSorted = True），直接跳过本次循环
        if isSorted:
            break

    return arr

冒泡排序的分析

一. 冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

二. 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

三. 时间复杂度:
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。

那平均时间复杂度为多少? 这里要引进“有序度”和“逆序度”这两个概念来进行分析
有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样：
有序元素对：a[i] <= a[j], 如果i < j。

对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n*(n-1)/2，也就是 15。我们把这种完全有序的数组的有序度叫作满有序度。

逆序度的定义正好跟有序度相反（默认从小到大为有序）：
逆序元素对：a[i] > a[j], 如果i < j。

冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是n*(n-1)/2–初始有序度。此例中就是 15–3=12，要进行 12 次交换操作。

对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是 0，所以要进行 n(n-1)/2 次交换。最好情况下，初始状态的有序度是 n(n-1)/2，就不需要进行交换。我们可以取个中间值 n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。

换句话说，平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n^2)，所以平均情况下的时间复杂度就是 O(n^2)。

2. 插入排序（Insertion Sort)

我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。
插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。

from typing import List


def insertion_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return
    for i in range(1, length):
        # 选出要插入的数据
        current = a[i]
        j = i - 1
        # 在已经排好序的部分从后往前一一比较,如果大于出入的数据,则往后退一个单位
        while j >= 0 and a[j] > current:
            a[j + 1] = a[j]
            j -= 1
        # 当没有数据比插入的数据大时,则将该数据插入数组中
        a[j + 1] = current

插入排序的性能分析

一. 冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

二. 在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

三. 时间复杂度

如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为 O(n)。
如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n^2)。
在数组中插入一个数据的平均时间复杂度是O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n^2)。

3. 希尔排序(Shell’s Sort)

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

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

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

def shell_sort(lists):
    #希尔排序
    count = len(lists)
    step = 2
    group = count // step
    while group > 0:  #通过group增量分组循环
        for i in range(0, group):
            j = i + group
            while j < count:  #分组中key值的索引，通过增量自增
                k = j - group
                key = lists[j]
                while k >= 0:  #分组中进行插入排序
                    if lists[k] > key:
                        lists[k + group], lists[k] = lists[k], key
                    else: break
                    k -= group
                j += group
        group //= step
    return lists

4. 选择排序（Selection Sort）

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

选择排序

from typing import List


def selection_sort(a: List[int]):
    length = len(a)
    if length <= 1:
        return

    for i in range(length):
        # 选取排序区域的末尾
        min_index = i
        # 在未排序区域找到最小的元素
        for j in range(i, length):
            if a[j] < a[min_index]:
                min_index = j
        if i != min_index:
            a[i], a[min_index] = a[min_index], a[i]

选择排序的性能分析

一. 选择排序空间复杂度为 O(1)，是一种原地排序算法。

二. 选择排序是一种不稳定的排序算法。**选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

三. 选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n^2)。

5. 归并排序（Merge Sort）

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

归并排序的核心思想就是如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序的递推公式为:
递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件：
p >= r 不用再继续分解

from typing import List


def merge_sort(a: List[int]):
    length = len(a)
    _merge_sort_between(a, 0, length - 1)


def _merge_sort_between(a: List[int], low: int, high: int):
    if low < high:
        mid = low + (high - low) // 2
        # 分治思想
        _merge_sort_between(a, low, mid)
        _merge_sort_between(a, mid + 1, high)
        _merge(a, low, mid, high)


def _merge(a: List[int], low: int, mid: int, high: int):
    # 申请一个大小跟A[p...r]一样的临时数组
    temp = []
    i, j = low, mid + 1
    while i <= mid and j <= high:
        if a[i] <= a[j]:
            temp.append(a[i])
            i += 1
        else:
            temp.append(a[j])
            j += 1
    # 判断哪个子数组中有剩余的数据
    start = i if i <= mid else j
    end = mid if i <= mid else high
    # 将剩余的数据拷贝到临时数组tmp
    temp.extend(a[start:end + 1])
    # 将tmp中的数组拷贝回A[p...r]
    a[low:high + 1] = temp

归并排序的性能分析

一. 归并排序稳不稳定关键要看 merge() 函数，也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中，如果 A[p…q]和 A[q+1…r]之间有值相同的元素，先把 A[p…q]中的元素放入 tmp 数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。

二. 时间复杂度
我们假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。我们知道，merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：

T(1) = C；   n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n； n>1
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

通过这样一步一步分解推导，我们可以得到 T(n) = 2^kT(n/2^k)+kn。当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=log2n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。

归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。

三. 空间复杂度
归并排序不是原地排序算法。这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。
尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

6. 快速排序（Quicksort）

快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。

归并排序中有一个 merge() 合并函数，我们这里有一个 partition() 分区函数。partition() 分区函数实际上我们前面已经讲过了，就是随机选择一个元素作为 pivot（一般情况下，可以选择 p 到 r 区间的最后一个元素），然后对 A[p…r]分区，函数返回 pivot 的下标。

如果我们不考虑空间消耗的话，partition() 分区函数可以写得非常简单。我们申请两个临时数组 X 和 Y，遍历 A[p…r]，将小于 pivot 的元素都拷贝到临时数组 X，将大于 pivot 的元素都拷贝到临时数组 Y，最后再将数组 X 和数组 Y 中数据顺序拷贝到 A[p…r]。但是这就会消耗过多的空间。

我们通过游标 i 把 A[p…r-1]分成两部分。A[p…i-1]的元素都是小于 pivot 的，我们暂且叫它“已处理区间”，A[i…r-1]是“未处理区间”。我们每次都从未处理的区间 A[i…r-1]中取一个元素 A[j]，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A[i]的位置。只需要将 A[i]与 A[j]交换，就可以在 O(1) 时间复杂度内将 A[j]放到下标为 i 的位置。

from typing import List
import random


def quick_sort(a: List[int]):
    _quick_sort_between(a, 0, len(a) - 1)


def _quick_sort_between(a: List[int], low: int, high: int):
    if low < high:
        # 随机找一个数字作为开始的分区点
        k = random.randint(low, high)
        # 设置哨兵
        a[low], a[k] = a[k], a[low]
        # 找到分区点
        m = _partition(a, low, high)
        _quick_sort_between(a, low, m - 1)
        _quick_sort_between(a, m + 1, high)


def _partition(a: List[int], low, high):
    pivot, j = a[low], low
    for i in range(low + 1, high + 1):
        if a[i] <= pivot:
            j += 1
            a[i], a[j] = a[j], a[i]
    # 当没有小于基准数的时候,就是基准数的位置
    a[low], a[j] = a[j], a[low]
    return j

快速排序的性能分析

一. 快排是一种原地、不稳定的排序算法。

二. 时间复杂度: O(logn)

归并排序和快排的区别

快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。
归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。
快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/03/29/data-structure-05/

发表日期：March 29th 2020, 8:23:26 pm

更新日期：March 30th 2020, 5:20:21 pm

Next Post

《趣谈网络协议》学习笔记之--陌生的数据中心(上)
Previous Post

每日一道算法之--单词的压缩编码

CATALOG

1. 排序
1. 1.0.1. 排序的内存消耗
2. 1.0.2. 排序算法的稳定性
1.1. 1. 冒泡排序（Bubble Sort）
1. 1.1.1. 冒泡排序的优化
2. 1.1.2. 冒泡排序的分析
1.2. 2. 插入排序（Insertion Sort)
1. 1.2.1. 插入排序的性能分析
1.3. 3. 希尔排序(Shell’s Sort)
1.4. 4. 选择排序（Selection Sort）
1. 1.4.1. 选择排序的性能分析
1.5. 5. 归并排序（Merge Sort）
1. 1.5.1. 归并排序的性能分析
1.6. 6. 快速排序（Quicksort）
1. 1.6.1. 快速排序的性能分析
1.7. 归并排序和快排的区别

