排序算法

发表于 | 更新于 | 分类于 Major

选择排序

选排的思想

找出每一轮的最值并放在该轮次位置处
核心思想是每轮选最值
外层循环确定轮次，内层循环确定最值。

def selectionSort(nums):
    for i in range(len(nums)):
        pos = i
        for j in range(i + 1, len(nums)):
            if nums[pos] > nums[j]:
                pos = j
        nums[i], nums[pos] = nums[pos], nums[i]
    return nums

时间复杂度

选择排序的比较次数 = (n - 1) + (n - 2) + … + 2 + 1 = n * (n - 1) / 2，因此时间复杂度为：O(n²)。

冒泡排序

基本思路

每一轮通过不断对比交换位置来将该轮最大（小）值上浮（下沉）到对应轮位置
核心思想是每轮换位置
外层循环确定轮次，内层循环交换位置。

def bubbleSort(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] > nums[j]:
                nums[i], nums[j] = nums[j], nums[i]

    return nums

每一轮都进行了多次交换，故相较于选择排序耗时

时间复杂度

冒泡排序的比较次数 = (n - 1) + (n - 2) + … + 2 + 1，即：n * (n - 1) / 2，所以冒泡排序的时间复杂度为：O(n²)
冒泡排序最优情况的时间复杂度是：O(n) 要达到这个复杂度，上述代码需要进一步优化

交换判定优化

对于已经有序的数列，进行了冗余的循环操作，通过在每轮进行交换标记来进行优化

# 冒泡交换判定优化
def optimizeBubbleSort(nums):
    for i in range(len(nums)):
        swap = False
        for j in range(i + 1, len(nums)):
            if nums[i] > nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
                swap = True
        if not swap:
            return nums
    return nums

插入排序

插排的思想

将 list 分为两部分，前部分作为已排序部分并向其中插入值，注意插入值之后值的移动
外层循环确定插入值，内层循环确定插入位置

# 插入排序
# 外层循环确定插入值，内层循环确定插入位置
# 将list分为两部分，前部分作为已排序部分并向其中插入值，注意值的移动
def insertionSort(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            j = i - 1
            aim = nums[i]
            while aim < nums[j] and j > -1:
                nums[j + 1] = nums[j]
                j -= 1

            nums[j + 1] = aim
    return nums

时间复杂度分析

最坏的情况下，即整个数组是倒序的，比较次数 = 1 + 2 + 3 + … + (n - 2) + (n - 1) = n * (n - 1) / 2，此时的时间复杂度为：O(n²)。
在最好的情况下，即整个数组是正序的，比较次数 = n - 1，此时的时间复杂度为：O(n)

哨兵优化

在插入排序循环判定中，aim < nums[j] and j > -1，即既要保证不越界又要判断数据是否符合条件，用哨兵代替上述两个条件，每次循环只需一次比较，可以减少一半的比较次数。

哨兵的作用

  • 暂时存放待插入的元素
  • 监视数组下标越界
def sentryInsertionSort(nums):
    nums.append(nums[0])
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            j = i - 1
            nums[0] = nums[i]
            while nums[0] < nums[j]:
                nums[j + 1] = nums[j]
                j -= 1
            nums[j + 1] = nums[0]
    return nums[1:]

折半优化

前半部分由于已经排序，故可通过二分查找找出插入位置

# 插入排序折半优化
def binaryInsertionSort(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            aim = nums[i]
            s,m,e = 0, 0, i - 1
            while s < e:
                m = s + e >> 1
                if aim > nums[m]:
                    s = m + 1
                else:
                    e = m
            j = i
            while j > e:
                nums[j] = nums[j - 1]
                j -= 1
            nums[e] = aim
    return nums

归并排序（Merge Sort）

归并排序思路

归并排序是一种分治算法。
其思想是将原始数组切分成较小的数组，直到每个小数组只有一个元素，接着将小数组归并成有序的较大的数组，最后变成一个排序完成的大数组。
归并排序中，归是指递归，并即合并
递归进行拆分，合并进行排序（两个有序数组合为新的有序数组）
归并排序与快排最大的不同在于重合并不重划分，归并需要合并两个有序数列，在划分时，无脑取中位即可。

# 归并排序
# 归并排序的主要思想是分治
# 将n个元素从中间切开，分成两部分。（左右可能长度差1）
# 递归分解，直到所有部分的元素个数都为1
# 从最底层开始逐步向上合并两个排好序的数列

# 并
# 合并两个有序数组为新的有序数组
def mergeSorted(nums1, nums2):
    nums = []
    i, j = 0, 0
    l = len(nums2)
    while i < len(nums1):
        if nums1[i] <= nums2[j]: #判定条件为 nums1[i] < nums2[j]时不稳定
            nums.append(nums1[i])
            i += 1
        else:
            nums.append(nums2[j])
            j += 1
        if (j == l):
            break
    return nums + nums1[i:] + nums2[j:]

# 归
def recursionMergeSort(nums):
    l = len(nums)
    if l < 2:
        return nums
    else:
        # 整除
        m = l // 2
        return mergeSorted(recursionMergeSort(nums[:m]), recursionMergeSort(nums[m:]))

mergeSorted 方法里面的 nums1[i] <= nums2[j] ，保证了值相同的元素，在合并前后的先后顺序不变。归并排序是一种稳定的排序方法

合并

如何将两个有序数组合并成一个新的有序数组?
轮番比较两个数列的最低位，直到一方全部比较完毕

def mergeSorted(nums1, nums2):
    nums = []
    i, j = 0, 0
    l = len(nums2)
    while i < len(nums1):
        if nums1[i] < nums2[j]:
            nums.append(nums1[i])
            i += 1
        else:
            nums.append(nums2[j])
            j += 1
        if (j == l):
            break
    return nums + nums1[i:] + nums2[j:]

由于合并函数需要另开内存空间存储新的数组，归并排序不是原地排序算法。

时间复杂度分析

递归中的时间复杂度为 logn，合并数组最多循环 n 次
归并排序的时间复杂度为 O(nlogn)

快速排序

快排思路

采用分治的思想，选取一个值为基准值，假设其放在正确顺序位置 pos，将比其小的放在其前面，比其大的放在其后面，从 pos 处将数列砍成两半，对子序列递归执行前述操作
递归进行拆分，双指针进行排序
快排重划分，不需要合并，在划分时，可以随意选择一个值，但选值得大小将影响排序的效率
通过双指针找到选择值在数列中的正确位置

  • 取中位

取中位，在将中位交换到对应位置时，对比取边界，需要做比较多的处理，容易出错

def quickSort(nums, start, end):
    if end - start < 1:
        return
    # m可取数列中任意数，此处取中位
    s, m, e = start, start + end >> 1, end
        # 通过双指针找到nums[m]正确位置
    while s <= e:
        # 取值判定加等号，防止nums[m]值被交换
        while s <= e and  nums[s] <= nums[m]:
            s += 1
                # 取值判定加等号，防止nums[m]值被交换，针对中位取值
        while s <= e and nums[e] >= nums[m]:
            e -= 1
        if s < e:
            nums[s], nums[e] = nums[e], nums[s]
        # 通过交换将nums[m]放在正确的位置
    if m > s:
        nums[s], nums[m] = nums[m], nums[s]
        # 移动位置，缩减nums[m]位置，防止某些情况死循环（如所有值一致）
        s += 1
    else:
        nums[e], nums[m] = nums[m], nums[e]
        e -= 1

    if start < e:
        quickSort(nums, start, e)
    if s < end:
        quickSort(nums, s, end)
  • 取边界
def quickSort(nums, start, end):
    if end - start < 1:
        return
    s, m, e = start + 1, start, end # 选取第一个值为基准值
    while s <= e:
        while s <= e and  nums[s] < nums[m]: # 找出左边以一个比基准大的数的位置
            s += 1
        while s <= e and nums[e] >= nums[m]: # 找出右边以一个比基准小的数的位置
            e -= 1
        if s < e: # 交换双方位置，并进入中间尚未比较位置继续对比交换
            nums[s], nums[e] = nums[e], nums[s]

    nums[e], nums[m] = nums[m], nums[e]
    if start < e:
        quickSort(nums, start, e - 1)
    if s < end:
        quickSort(nums, s, end)

选值优化

  • 随机选值
    基准值随机地选取，而不是每次都取第一个数。这样就不会受正序或逆序的数组的干扰
  • 三数取中
    前中后选三个值选取三数的中位数，以降低取到最大或最小值的概率。三数取中时，比较的同时应将三个元素按中间，小，大的顺序重新排好位置

多路快排

在遍历数列时选用指针的数量

  • 单路
    基准值 base 左边的都比 base 小，而 base 右边的都大于等于 base。等于 base 的这些会聚集到右侧(或者稍微改改大小关系就会聚集到左侧)。总之就会聚集到一边。这样在数组中重复数字很多的时候，就又会导致两边子递归规模差距悬殊的情况
  • 双路
    上述代码采用的就是双路
  • 三路
    对于大于小于等于分别选用一个指针
    在当前值小于目标值时，s 与 c 齐头并进，直到等于出现时，s 停留在第一个相等的位置，c 开始往后移动，通过 c 做中介来交换 s 与 e 位置的值
def quickSort(nums, start, end):
    if end - start < 1:
        return
    s, c, m, e = start + 1, start + 1, start, end
    while c <= e:
        if nums[c] == nums[m]:
            c += 1
        elif nums[c] < nums[m]:
            nums[s], nums[c] = nums[c], nums[s]
            s += 1
            c += 1
        else:
            nums[e], nums[c] = nums[c], nums[e]
            e -= 1
    nums[e], nums[m] = nums[m], nums[e]
    if start < e:
        quickSort(nums, start, e - 1)
    if s < end:
        quickSort(nums, s, end)
  • 时间复杂度分析
    待排序为正序或逆序，取值也为最值，这样每次分割后的子序列一个之比上一次序列少一个元素,最终 O(n²)
    平均为 O(nlogn)

希尔排序（缩小增量排序）

关键思路

希尔排序又叫缩小增量排序
希尔排序是插入排序的优化版本，在插入排序中，将数列分为有序与无序部分，若无序部分的头部每次都需要插入到有序部分的头部，那么最终的总复杂度会到 n²
希尔排序将数列每一轮分为多个子数列，对每个子数列进行插入排序，直至整体基本有序时（增量为 1 前），再对全体记录进行插入排序（增量为 1）起来就容易了(由于最后一次基本有序无须多次移位或交换)

def shellSort(nums):
    span = len(nums)
    while span > 1:
        span //= 2  # span取数跨度，先将整个待排序的记录序列分割成为若干子序列，每轮缩小取数跨度，子数列长度
        insertionSort(nums, span)
    return nums


def insertionSort(nums, span):
    for pos in range(span, len(nums), 1):  # 由span位置开始，到len(nums) - 1位置结束， 循环步长为1
        if nums[pos] < nums[pos - span]:
            pre = pos - span
            aim = nums[pos]
            while aim < nums[pre] and pre > -1:
                nums[pos] = nums[pre]  # 数后移
                pre -= span
            nums[pre + span] = aim

时间复杂度

希尔排序的时间复杂度最佳情况：O(n logn)。 最差情况：O(n (log(n))²)。 平均情况：取决于间隙序列

计数排序

关键思路

对于一个自然数数组 A，选取数组中的最大值 m，然后初始化一个长度为 m + 1 的备用数组 B。
对于数组 B
B 的索引对应数组 A 的值
B 的值对应数组 A 中相应值的个数
C 的值记录 A 顺序后前面出现值的个数
例如

A = [3, 3, 9, 2, 2, 2, 0]
# B = [1, 0, 3, 2, 0, 0, 0, 0, 0, 1]
# C = [1, 1, 4, 6, 6, 6, 6, 6, 6, 7]
# 以3为例
# B: 3有两个
# C: 如果有3，最后一个3位于第6位，即索引为5

def countingSort(nums):
    counts = [0] * (max(nums) + 1)
    for i in nums:
        counts[i] += 1

    accumulation = 0
    for index, value in enumerate(counts):
        accumulation += value
        counts[index] = accumulation

    rets = [0] * len(nums)
    for v in nums:
        rets[counts[v] - 1] = v
        counts[v] -= 1  # 下一个相同值索引减1

    return rets

时间复杂度分析

计数排序利用了空间换时间，对于不同的实现（比如最大值判定循环等），其内部始终是遍历两个定长的数组。
O(max)+O(len)+… = O(max+len)
即其时间复杂度为 O(n + k)

堆排序

完全二叉树

二叉树是指最多只存在两个子节点的树形数据结构。
完全二叉树是指除了最后一层的叶子节点，每一层节点都存在，且最后一层的叶子节点由左起依次排列不能留空。

数组可以表示一个典型的完全二叉树。
i（索引） 为 0 的节点为根节点。
所有左子节点的索引为 2i+1，右子节点的索引为 2i+2。
同时，可以通过(i-1)/2 获取其父节点的值

堆

堆是一颗完全二叉树，且对于所有节点，都要满足父节点的值大于等于（或小于等于）子节点的值。
父节点大于等于子节点时，称为大顶堆
父节点小于等于子节点时，称为小顶堆

构造堆

当跟节点的左子树和右子树已经为堆时，加入父节点构造堆。

# 当跟节点的左子树和右子树已经为堆时，加入父节点构造堆
def heapify(nums, pos):
    length = len(nums)
    mark = pos
    left = 2 * pos + 1
    right = 2 * pos + 2

    if(left < length and nums[pos] < nums[left]):
        pos = left

    if(right < length and nums[pos] < nums[right]):
        pos = right

    if(mark != pos):
        nums[mark], nums[pos] = nums[pos], nums[mark]
        heapify(nums, pos) # 交换位置后，子树需要重新构造堆
    return nums

对于任意完全二叉树（数组）构造堆

# 对于任意完全二叉树（数组）构造堆
def heapifyArr(nums):
    start = (len(nums) - 1) // 2 # 大于此索引的其他节点是叶子节点
    while (start > -1):
        heapify(nums, start) #所有非叶子节点，由下到上，从右到左依次遍历构造堆
        start -= 1
    return nums

排序

对于任意数组，当调用上述方法构造堆后，可得其最值位于根节点（索引为 0）
利用该特性，堆排序思路如下

  1. 将数组构造成堆
  2. 交换堆的首节点与尾节点，移除此时处于最后的根节点（或记录偏移位置）。
  3. 对于剩下的完全二叉树，根节点的左右子树仍为堆，采用 heapify 来将剩下的完全二叉树构造成堆。
  4. 重复 2、3 步，直到移除完所有节点

# 堆排序
def heapSort(nums):
    pos = len(nums) - 1
    heapifyArr(nums)
    ret = []
    arr = nums
    while pos > -1:
        arr = heapify(arr[:pos + 1], 0)
        ret.append(arr[0])
        arr[0], arr[pos] = arr[pos], arr[0]
        pos -= 1
    return ret

上述排序引入了多余的数组来最后存储与中间存储相关结果，通过对偏移量的记录，所有操作可以源数组进行（原地排序）
进一步优化

# 当跟节点的左子树和右子树已经为堆时，加入父节点构造堆
def heapify(nums, offset, pos):
    # length = len(nums)
    mark = pos
    left = 2 * pos + 1
    right = 2 * pos + 2

    if(left < offset and nums[pos] < nums[left]):
        pos = left

    if(right < offset and nums[pos] < nums[right]):
        pos = right

    if(mark != pos):
        nums[mark], nums[pos] = nums[pos], nums[mark]
        heapify(nums, offset, pos)  # 交换位置后，子树需要重新构造堆
    # return nums


# 对于任意完全二叉树（数组）构造堆
def heapifyArr(nums):
    start = (len(nums) - 1) // 2  # 大于此索引的其他节点是叶子节点
    while (start > -1):
        heapify(nums, len(nums), start)  # 所有非叶子节点，由下到上，从右到左依次遍历构造堆
        start -= 1
    # return nums

# 堆排序
def heapSort(nums):
    offset = len(nums) - 1
    heapifyArr(nums)
    # ret = []
    # arr = nums
    while offset > -1:
        heapify(nums, offset, 0)
        nums[0], nums[offset] = nums[offset], nums[0]
        offset -= 1
    return nums

nums = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
# nums = [1, 12, 9, 5, 6, 10]
heapSort(nums)
print(nums)

BMW WARNING

  • Bulletin

本文首发于 skyline.show 欢迎访问。

I am a bucolic migrant worker but I never walk backwards.

  • Material

参考资料如下列出，部分引用可能遗漏或不可考，侵删。

https://zhuanlan.zhihu.com/p/36075856

  • Warrant

本文作者： Skyline(lty)
授权声明： 本博客所有文章除特别声明外， 均采用 CC BY - NC - SA 3.0 协议。 转载请注明出处！

[CC BY - NC - SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/deed.zh

Copyright © 2017 - 2024 鹧鸪天 All Rights Reserved.

skyline 保留所有权利