简单排序算法

直接插入排序

时间: O(n**2)

空间: O(1)

稳定: True

直接插入排序是从头到尾遍历一遍序列, 每次将当前元素插入到前方到已经排列好到序列中 . 具体插入方法是,从后向前遍历排序好到序列, 如果待排元素和当前元素符合条件, 则交换位置. 如果不符合, 说明已经排列成功,待排点就插入完毕.

def insert_sort(arr, func=lambda x, y: x < y):
    length = len(arr)
    if length <= 1:
        return
    for i in range(1, len(arr)):
        tem = arr[i]
        for j in range(i - 1, -1, -1):
            if func(tem, arr[j]):
                arr[j + 1], arr[j] = arr[j], tem
            else:
                break

    return arr

选择排序

时间: O(n**2)

空间: O(1)

稳定: False

选择排序是从头到尾遍历一遍序列, 每次选择最左侧未排序的下标作为待选择下标, 然后在未排序的序列中找到一个最符合条件的元素, 然后交换到待选择下标中.

def select_sort(arr, func=lambda x, y: x < y):
    length = len(arr)
    for i in range(length):
        min_index = i
        for j in range(i + 1, length):
            if func(arr[j], arr[min_index]):
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

冒泡排序

时间: O(n**2)

空间: O(1)

稳定: True

冒泡排序是每次比较下标相邻的元素, 然后逐步向后遍历. 每次可以将最大的那个数放置到未排序序列的末尾, 因此最多需要循环 n 次. 但是在每次冒泡过程中, 也将其他元素进行了排序. 所以可以通过一个变量来监测当前循环中有无变化. 如果没有变化, 就不用继续进入下一个循环了.

def buble_sort(arr, func=lambda x, y: x < y):
    length = len(arr)
    for i in range(length - 1, -1, -1):
        has_change = False
        for j in range(1, i + 1):
            if func(arr[j], arr[j - 1]):
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
                has_change = True
        if not has_change:
            break

    return arr

复杂排序算法

希尔排序

时间: O(n*[log(n)]**2)

空间: O(1)

稳定: False

希尔排序是直接插入排序的进阶版, 它由多个(一般为 log[len(arr)])直接插入排序构成. 在每次直接插入排序中, 原本只是比较相邻的两个数, 但在希尔排序中, 每次会比较步长个间距的两个数.

希尔排序之所以比直接插入排序更加高效, 可以通过一个例子来认识: arr= [321565, 56540, 132, 1651, 132,1651, 1], 要想将这个序列排序为从小到大. 直接插入排序在加入 ‘1’ 这个元素时, 需要将这个元素一步一步地向前移动, 直到到达最左侧. 这样涉及到了 len(arr) 次的元素交换. 但在希尔排序中, 由于每次可以跨越一个步长个单位 . 因此只需要移动 log[len(arr)] 个单位. 因此希尔排序比直接插入排序更高效一些.

def shell_sort(arr, func=lambda x, y: x < y):
    length = len(arr)
    path_l = length // 2
    while path_l > 0:
        for i in range(path_l, length):
            idx = arr[i]
            j = i - path_l
            while j >= 0 and func(idx, arr[j]):
                arr[j + path_l] = arr[j]
                j -= path_l
            else:
                arr[j + path_l] = idx
        path_l //= 2

    return arr

堆排序

时间: O(n*[log(n)]**2)

空间: O(1)

稳定: False

堆排序是使用一个名为堆的结构, 这个结构类似于一个完全二叉树. 因此可以使用一个顺序结构存储每个节点. 对于每一个节点, 如果它有子节点, 则左子节点为 2*idx+1 右子节点为 2*idx+2. 且对于大顶堆来说, 父节点一定大于等于子节点.

那么如何使用堆来进行排序呢, 首先我们可以将一个数组大顶堆化, 然后依次取出第一个节点值依次放入堆的尾端, 然后再维护堆的稳定就可以了(调整时需要忽略尾端已经排序好的序列).

以下是维护堆的代码. 我们设置这样的一个函数 heap_fit(target_idx, size) 其中 target_idx 表示目前需要调整的元素下标, size 表示堆的最大下标.

  • 循环中, 每次都比较 target_idx 的左右节点是否大于 arr[target_idx].
    • 如果大于, 则用子节点的值更新 target_idx 位置. 并将子节点设置为父节点, 再次比较.
    • 如果不大于或左子节点的下标超过最大范围, 则退出循环
  • 将目前父节点的值更新为最初 target_idx 的值
def heap_sort(arr, func=lambda x, y: x < y):
    length = len(arr)

    def heap_fit(target_idx: int, size: int):
        idx_i, idx_j = target_idx, 2 * target_idx + 1
        index_val = arr[idx_i]
        while idx_j <= size:
            if idx_j < size and func(arr[idx_j], arr[idx_j + 1]):
                idx_j += 1
            if func(index_val, arr[idx_j]):
                arr[idx_i] = arr[idx_j]
                idx_i, idx_j = idx_j, 2 * idx_j + 1
            else:
                break
        arr[idx_i] = index_val

    for i in range(length // 2 - 1, -1, -1):
        heap_fit(i, length - 1)
    for i in range(length - 1, -1, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heap_fit(0, i - 1)

    return arr

归并排序

时间: O(n*[log(n)]**2)

空间: O(n)

稳定: True

归并排序使用了分治思想来进行排序, 首先将元素一一分为一个单独的序列, 然后两两组合起来. 只不过在组合起来的时候保持组合后的序列也是一个有序序列.

def merge_sort(arr, le=None, ri=None, func=lambda x, y: x < y):
    def merge(lo: int, mi: int, hi: int):
        lo_length = mi - lo
        hi_length = hi - mi
        lo_list = arr[lo: mi]
        hi_list = arr[mi:hi]
        i, j, k = 0, 0, lo
        while i != lo_length and j != hi_length:
            if func(lo_list[i], hi_list[j]):
                arr[k], i = lo_list[i], i + 1
            else:
                arr[k], j = hi_list[j], j + 1
            k += 1
        while i != lo_length:
            arr[k] = lo_list[i]
            i, k = i + 1, k + 1
        while j != hi_length:
            arr[k], j, k = hi_list[j], j + 1, k + 1

    if (le and ri) is None:
        le, ri = 0, len(arr)

    if le < ri:
        mid = (le + ri) // 2
        merge_sort(arr, le, mid)
        merge_sort(arr, mid + 1, ri)
        merge(le, mid, ri)

    return arr

快速排序

时间: O(n*[log(n)]**2)

空间: O(log(n))

稳定: False

不多做介绍, 这个相信程序员都知道.

def quick_sort(arr, lo=None, hi=None, func=lambda x, y: x < y):
    if (lo and hi) is None:
        lo, hi = 0, len(arr) - 1

    if lo >= hi:
        return arr

    left, right = lo, hi
    key = arr[lo]
    while lo < hi:
        while lo < hi and func(key, arr[hi]):
            hi -= 1
        arr[lo] = arr[hi]
        while lo < hi and not func(key, arr[lo]):
            lo += 1
        arr[hi] = arr[lo]

    arr[hi] = key
    quick_sort(arr, left, lo - 1)
    quick_sort(arr, lo + 1, right)

    return arr

基数排序

时间: O(n*log(n))

空间: O(log[max(arr)])

稳定: True

基数排序是用一个一个桶对序列中每个数字进行分类, 从个位开始分类. 将序列一次输出, 直到最高位分类完成.此时其他位置上对数也完成了排序.

def radix_sort(arr):
    max_num = max(arr)
    max_index = len(str(max_num))
    for i in range(max_index):
        bucket_list = [[] for _ in range(10)]
        for x in arr:
            bucket_list[int(x / (10 ** i)) % 10].append(x)
        arr.clear()
        for bucket in bucket_list:
            for item in bucket:
                arr.append(item)
        i += 1

    return arr

外部排序算法

外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序 整个文件的目的。

外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行多路归并排序。

以下是对基础的多路归并排序算法的优化算法.

置换-选择排序

置换-选择排序算法是用来帮助归并排序分割归并段的算法.

以下是它的工作原理:

  1. 从待排文件 FI 输入 W 个记录到工作区 WA.

  2. 从内存工作区 WA 中选出其中关键字最小的记录,记为 MINIMAX.(以后再选出关键字比它大的记录纳入本归并段,比它小的归入下一归并段)

  3. 将 MINIMAX 记录输出到 FO 中去。

  4. 若 FI 未读完,则从 FI 输入下一个记录到 WA 中。

  5. 从 WA 中所有关键字比 MINIMAX 记录的关键字大的记录中选出最小的关键字记录,作为新的 MINIMAX。

  6. 重复 3)~5)直到在 WA 中选不出新的 MINMAX 记录为止,由此得到一个初始归并段,输出一个归并段的结束标志到 FO 中去。

  7. 重复 2)~6)直到 WA 为空,由此得到全部初始归并段。

最佳归并树

类似于哈夫曼树的构建原理, 用来构建最佳 I/O 操作的归并树.

败者树

败者树


正是你花费在玫瑰上的时间才使得你的玫瑰花珍贵无比