open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  • 综述
  • 问题
  • 思路
  • 复杂度和运行时
  • 排序算法集锦
  • 冒泡排序(Bubble Sort)
  • 选择排序(Selection Sort)
  • 插入排序(Insertion Sort)
  • 快速排序(Quick Sort)
  • 堆排序(Heap Sort)
  • 归并排序(Merge Sort)
  • 计数排序(Counting Sort)
  • 基数排序(Radix Sort)
  • 现实中的排序算法
  • TimSort
  • 外排序算法
  • 参考
  1. MIT - 6.006

Sorting

总结排序算法,不局限于本课程所述的部分

综述

问题

假设要将一个大小为 NNN 的从小到大排序。

思路

1. 每次将一个元素移动到最终位置

一些排序算法,如选择排序 (selection sort),冒泡排序 (bubble sort) 以及堆排序 (heap sort),每次将一个元素移动到最终位置,这样就能将大小为 NNN 的问题转化成大小为 N−1N-1N−1 的问题。

2. 每次将每个元素放到更接近最终位置的地方

一些排序算法,如插入排序 (insertion sort),快速排序 (quick sort),计数排序 (counting sort) 以及基数排序 (radix sort),每次将每个元素放到更接近最终位置的地方,使得整体序列的逆序数量逐渐变少,并最终达到排序目的。

3. 分治

如归并排序 (merge sort)

复杂度和运行时

  • 排序至少要遍历一遍待排序列,因此排序算法的复杂度为 O(n)O(n)O(n)

  • 影响复杂度的因素包括:

    • 算法本身的流程复杂程度及启动开销:简单的算法虽然复杂度常为 O(n2)O(n^2)O(n2) ,但它的其它开销(常数项)可能很小,因此面对长度较小(如 < 10)的序列常常有更快的性能。因此实际运用中,常常会通过判断序列大小来选择所使用的排序算法

    • 多余的空间,如变量及递归的栈空间

    • 缓存:算法运行过程中的大部分比较操作如果都是发生在相邻元素之间,就容易利用数据的空间分布特点,获得更高的缓存命中率以及数据预取

    • 各种类型的输入考量:乱序、已经排好序、倒着排好序、接近排好序等

  • 基于比较的排序算法对待排序列没有任何假设,理想情况下,在任何输入面前都能够做到 θ(nlogn)\theta(nlogn)θ(nlogn) 的算法复杂度,如堆排序、归并排序等。

  • 如果我们可以对数据做一些额外的假设,就可能获得比 θ(nlogn)\theta(nlogn)θ(nlogn) 更好的算法复杂度,如在计数排序中,我们假设数据分布在一定范围内。

排序算法集锦

冒泡排序(Bubble Sort)

复杂度小结

Case

Time Complexity

Space Complexity

Best

Worst

Average

思路

从左往右冒泡,每次比较左右两个元素,如果前者大于后者,则交换位置,一共循环 N−1N-1N−1 次,第 i 次循环结束时,第 i 大的元素都会移动到正确的位置上。

bubble.py
def bubble(A):
    L = len(A)
    for i in range(L-1):
        flag = True
        for j in range(L-i-1):
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]
                flag = False
        if flag:
            break

选择排序(Selection Sort)

复杂度小结

Case

Time Complexity

Space Complexity

All

思路

选择排序是所有排序中最直观的排序,从左开始,每次从剩余元素中选择最大(小)的元素,放到剩余序列的最右(左)边。

selection.py
def selection(A):
    L = len(A)
    for i in range(L-1):
        mi = 0
        for j in range(1, L-i):
            if A[j] > A[mi]:
                mi = j
        A[mi], A[L-i-1] = A[L-i-1], A[mi]

插入排序(Insertion Sort)

复杂度小结

Case

Time Complexity

Space Complexity

Best

Worst

Average

思路

插入排序与打扑克时整理牌的方法类似,从左向右开始,第 i 轮结束保证前 i 个元素已经排好序。

insertion.py
def insertion(A):
    for i in range(1, len(A)):
        for j in range(i, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
            else:
                break

快速排序(Quick Sort)

复杂度小结

Case

Time Complexity

Space Complexity

Best

Worst

Average

思路

有点像二分,每次选取一个 pivot,将所有小于 pivot 的数和所有大于 pivot 的数,分别作为两个子序列,递归地排序。其中 pivot 的选择决定了最终排序的复杂度。

def quicksort(A):
    _quicksort(A, 0, len(A))

def _quicksort(A, l, h):
    if l < h:
        pi = _partition(A, l, h)
        _quicksort(A, l, pi)
        _quicksort(A, pi+1, h)

def _partition(A, l, h):
    # 任何 pivot 选择策略都可以,这里选择最后一个
    pi = h-1
    # 将 pivot 交换到最后
    A[pi], A[h-1] = A[h-1], A[pi]
    pi, p = h-1, p[h-1]
    
    i = l-1
    for j in range(l, h-1):
        if A[j] < p:
            i += 1
            A[i], A[j] = A[j], A[i]
    i += 1
    A[h-1], A[i] = A[i], A[h-1]
    return i

快速排序快的原因在于:

  1. pivot 选择得好时,能够获得 θ(nlogn)\theta(nlogn)θ(nlogn) 的时间复杂度

  2. 它利用了 spatial locality,总是比较相邻的元素,因此很好地利用 cache

堆排序(Heap Sort)

复杂度小结

Case

Time Complexity

Space Complexity

All

使用堆(具体参考 Priority Queue Interface & Implementation 一节),先对原序列建堆(原地建堆可以获得 O(1)O(1) O(1) 的空间复杂度),后每次从堆中 pop 出最大值,放到序列末尾即可。

归并排序(Merge Sort)

复杂度小结

Case

Time Complexity

Space Complexity

All

思路

每次将序列二等分,各部分排好序后,再合并。

def mergesort(A):
    _mergesort(A, 0, len(A))

def _mergesort(A, l, h):
    # 区间内只有小于 2 个元素,直接返回,无需排序
    if l+1 >= h:
        return
    m = (l+h)//2
    _mergesort(A, l, m)
    _mergesort(A, m, h)
    _merge(A, l, m, h)

def _merge(A, l, m, h):
    tmp = []
    i, j = l, m
    while i < m and j < h:
        if A[i] < A[j]:
            tmp.append(A[i])
            i += 1
        elif A[i] > A[j]:
            tmp.append(A[j])
            j += 1
        else:
            tmp.append(A[i])
            tmp.append(A[j])
            i += 1
            j += 1
    while i < m:
        tmp.append(A[i])
        i += 1
    while j < h:
        tmp.append(A[j])
        j += 1
    A[l:h] = tmp
def mergesort(A):
    step = 1
    ll = len(A)
    while step <= ll:
        h = 0
        for h in range(0, ll, step*2):
            l, m, r = h, h+step, min(ll, h+2*step)
            p, q = l, m
            while p < m and q < r:
                if A[p] < A[q]:
                    p += 1
                else:
                    tmp = A[q]
                    A[p+1: q+1] = A[p:q]
                    A[p] = tmp
                    p, m, q = p+1, m+1, q+1
        step *= 2
    return A

计数排序(Counting Sort)

复杂度小结

Case

Time Complexity

Space Complexity

All

其中 n 表述序列大小,k 表示元素的范围大小

思路

统计元素所处范围内中每个元素的数量,然后从小到大遍历生成新序列即可

counting.py
def counting_sort(A, k, fn=lambda ele: ele):
    ll = len(A)
    
    counting_table = [0]*k
    for ele in A:
        counting_table[fn(ele)] += 1
    
    position_table = counting_table
    count = ll
    for i in reversed(range(len(position_table))):
        count -= position_table[i]
        position_table[i] = count
    ret = [0]*ll    
    for i, ele in enumerate(A):
        key = fn(ele)
        ret[position_table[key]] = ele
        position_table[key] = position_table[key] + 1
    return ret

基数排序(Radix Sort)

复杂度小结

Case

Time Complexity

Space Complexity

All

其中,d 表示最大数的位数,k 表示元素基数大小(如二进制,k = 2;十进制,k = 10)

思路

从最小的位数开始,如十进制中的个位,每轮对所有元素的该位数进行一次计数排序。

radix_sort.py
def radix_sort(A, d, k):
    def ele_to_key_gen(pos):
        def ele_to_key(ele):
            count = d - pos - 1
            while count > 0:
                ele = ele // k
                count -= 1
            return ele % k
        return ele_to_key
    
    for pos in reversed(range(d)):
        ele_to_key = ele_to_key_gen(pos)
        A = counting_sort(A, k, ele_to_key)
    return A

现实中的排序算法

TimSort

复杂度小结

Case

Time Complexity

Space Complexity

All

思路

当序列较小时,使用插入排序;当序列较大时,先将序列分成多组,每组先使用插入排序,后对不同组递归地使用归并排序中的归并步骤。

timsort.py
def insertion_sort(A):
    for i in range(1, len(A)):
        for j in range(i, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
            else:
                break
    return A

def merge(A, B):
    li, lj = len(A), len(B)

    R = []

    i, j = 0, 0
    while i < li and j < lj:
        if A[i] < B[j]:
            R.append(A[i])
            i += 1
        elif A[i] > B[j]:
            R.append(B[j])
            j += 1
        else:
            R.append(A[i])
            R.append(B[j])
            i += 1
            j += 1

    while i < li:
        R.append(A[i])
        i += 1
    while j < lj:
        R.append(B[j])
        j += 1
    return R


def timsort(A):
    ll = len(A)

    RUN = 32
    for i in range(0, ll, RUN):
        A[i:i+RUN] = insertion_sort(A[i:i+RUN])

    RUNinc = RUN
    while RUNinc < ll:
        for i in range(0, ll, 2*RUNinc):
            A[i:i+2*RUNinc] = merge(A[i:i+RUNinc],
                                    A[i+RUNinc:i+2*RUNinc])
        RUNinc *= 2
    return A

外排序算法

TODO

参考

PreviousDictionary Problem & ImplementationNextDynamic Programming

Last updated 6 years ago

参考

O(n)O(n)O(n)
O(1)O(1)O(1)
O(n2)O(n^2)O(n2)
O(1)O(1)O(1)
O(n2)O(n^2)O(n2)
O(1)O(1)O(1)
O(n2)O(n^2)O(n2)
O(1)O(1)O(1)
O(n)O(n)O(n)
O(1)O(1)O(1)
O(n2)O(n^2)O(n2)
O(1)O(1)O(1)
O(n2)O(n^2)O(n2)
O(1)O(1)O(1)
O(nlogn)O(nlogn)O(nlogn)
O(1)O(1)O(1)
O(n2)O(n^2)O(n2)
O(1)O(1)O(1)
O(nlogn)O(nlogn)O(nlogn)
O(1)O(1)O(1)
O(nlogn)O(nlogn)O(nlogn)
O(1)O(1)O(1)
O(nlogn)O(nlogn)O(nlogn)
O(n)O(n)O(n)
O(n)O(n)O(n)
O(k)O(k)O(k)
O(d∗(n+k))O(d*(n+k))O(d∗(n+k))
O(k)O(k)O(k)
O(nlogn)O(nlogn)O(nlogn)
O(n)O(n)O(n)
https://github.com/melvilgit/external-Merge-Sort
Sorting Algorithms Better Explained
Graphoarty: TimSort