数据结构与算法基础

发表于 | 分类于

算法数据结构

数组

1
// Todo

字典

1
// Todo

集合

1
// Todo

链表

参考文献

链表是一个集合，它的值是线性排列的序列。链表相比一些连续存储策略，例如 Swift Array，有这么几个理论上的优势：

  • 固定时间插入和顶端移除
  • 可靠的特征表现

由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

参考文献

双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

Node 节点

链表是一个节点的链条，节点拥有两个职责：

  • 持有一个值
  • 持有一个对下一节点的引用，一个 nil 代表了链表的结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Node<Value> {
    public var value: Value
    public var next: Node?
    
    public init(value: Value, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

extension Node: CustomStringConvertible {
    public var description: String {
        guard let next = next else { return "\(value)" }
        return "\(value) -> " + String(describing: next) + " "
    }
}

链表增加值

链表有一个头尾的改变，头指代了第一个节点，尾指代第二个节点。

有三种方式给一个链表添加值：

  1. push：在链表前端添加值
  2. append：在链表末尾添加值
  3. insert(after:)：在一个特定的节点后添加值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public struct LinkedList<Value> {
    public var head: Node<Value>?
    public var tail: Node<Value>?
    
    public init() {}
    
    public var isEmpty: Bool {
        return head == nil
    }
    
    // Push
    public mutating func push(_ value: Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
    
    // Append
    public mutating func append(_ value: Value) {
        guard !isEmpty else {
            push(value)
            return
        }
        
        tail!.next = Node(value: value)
        
        tail = tail!.next
    }
    
    public func node(at index: Int) -> Node<Value>? {
        var currentNode = head
        var currentIndex = 0
        
        // 向下遍历直到找到相应的 index, 返回 Node
        while currentNode != nil && currentIndex < index {
            currentNode = currentNode!.next
            currentIndex += 1
        }
        
        return currentNode
    }
    
    @discardableResult
    public mutating func insert(_ value: Value,
                                after node: Node<Value>) -> Node<Value> {
        
        // 如果尾部节点和 node 不是同一个节点
        guard tail !== node else {
            // 是同一个节点
            return tail!
        }
        
        node.next = Node(value: value, next: node.next)
        return node.next!
    }
}

extension LinkedList: CustomStringConvertible {
    public var description: String {
        guard let head = head else { return "Empty list" }
        return String(describing: head)
    }
}

性能

push append insert(after:) node(at:)
Behavior insert at head insert at tail insert after a node returns a node at given index
Time complexity O(1) O(1) O(1) O(i) where i is the given index

移除值

有三种操作移除链表中的节点：

  1. pop：移除最前端节点
  2. removeLast：移除尾部节点
  3. remove(after:)：移除链表中节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
extension LinkedList {
    /// Removes the value at the front of the list
    public mutating func pop() -> Value? {
        defer {
            head = head?.next
            print("defer head: \(head!)")
            if isEmpty {
                tail = nil
            }
        }
        print("head: \(head!)")
        return head?.value
    }
    
    public mutating func removeLast() -> Value? {
        
        guard let head = head else { return nil }
        
        // 如果这个链表只有一个节点, removeLast 就等价于 pop
        guard head.next != nil else {
            return pop()
        }
        
        // 一直搜索, 直到 current.next == nil
        // 这表明 current 是链表最后一个节点
        var prev = head
        var current = head
        
        while let next = current.next {
            prev = current
            // 第一次循环 prev === head -> true
            // 第二次循环 prev === head -> false
            // 此时 prev 的引用切换到 head.next
            current = next
        }
        
        // 这时 current 是最后一个节点
        // prev.next === current
        // 移除 prev.next 相当于移除 head.next 的 next, 更新 tail
        prev.next = nil
        tail = prev
        
        return current.value
    }
    
    @discardableResult
    public mutating func remove(after node: Node<Value>) -> Value? {
        defer {
            if node.next === tail {
                tail = node
            }
            node.next = node.next?.next
        }
        return node.next?.value
    }
}

Perform analysis

pop removeLast Remove(after:)
Time complexity O(1) O(n) O(1)

栈

参考文献

栈（英语：stack）又称为栈或堆叠，是计算机科学中一种特殊的串列形式的抽象数据类型，其特殊之处在于只能允许在链表或数组的一端（称为堆栈顶端指针，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。另外栈也可以用一维数组或链表的形式来完成。堆栈的另外一个相对的操作方式称为队列。

由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

对于栈，只有两个必要的操作：

  1. push：在栈顶添加一个元素
  2. pop：移除栈顶元素
  • 在 iOS 开发中，如果你要在你的 App 中添加撤销操作（比如删除图片，恢复删除图片），那么栈是首选数据结构
  • 无论在面试还是写 App 中，只关注栈的这几个基本操作：push, pop, isEmpty, peek, size。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public struct Stack<Element> {
    private var storage: [Element] = []
    public init() {}
    
    public init(_ elements: [Element]) {
        storage = elements
    }
    
    public mutating func push(_ element: Element) {
        storage.append(element)
    }
    
    // 忽略警告
    @discardableResult
    public mutating func pop() -> Element? {
        return storage.popLast()
    }
    
    public func peek() -> Element? {
        return storage.last
    }
    
    public var isEmpty: Bool {
        return peek() == nil
    }
}

extension Stack: CustomStringConvertible {
    public var description: String {
        let topDivider = "----top----\n"
        let bottomDivider = "\n----Bot----"
        
        let stackElements = storage
            .map { "\($0)" }
            .reversed()
            .joined(separator: "\n")
        
        return topDivider + stackElements + bottomDivider
    }
}

/// 用数组字面量初始化
extension Stack: ExpressibleByArrayLiteral {
    public init(arrayLiteral elements: Element...) {
        storage = elements
    }
}

队列

参考文献

队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。

队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

队列所关心的操作：

  • enqueue：在队列末尾插入一个元素
  • dequeue：移除队列头部元素
  • isEmpty：队列是否为空
  • peek：返回队列最开头的元素，不移除
1
2
3
4
5
6
7
8
public protocol Queue {
  
  associatedtype Element
  mutating func enqueue(_ element: Element) -> Bool
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get }
  var peek: Element? { get }
}

基于数组的队列

操作 最好情况 最差情况
enqueue O(1) O(1)
dequeue O(n) O(n)
空间复杂度 O(n) O(n)

基于双向链表队列

操作 最好情况 最差情况
enqueue O(1) O(1)
dequeue O(1) O(1)
空间复杂度 O(n) O(n)

环形缓冲区队列

操作 最好情况 最差情况
enqueue O(1) O(1)
dequeue O(1) O(1)
空间复杂度 O(n) O(n)

双栈队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public struct QueueStack<T> : Queue {
    
    private var leftStack: [T] = []
    private var rightStack: [T] = []
    public init() {}
    
    public var isEmpty: Bool {
        return leftStack.isEmpty && rightStack.isEmpty
    }
    
    public var peek: T? {
        return !leftStack.isEmpty ? leftStack.last : rightStack.first
    }
    
    /// 右栈用来插入, 左栈用来放右栈拿出来的数据
    public mutating func enqueue(_ element: T) -> Bool {
        rightStack.append(element)
        return true
    }
    
    public mutating func dequeue() -> T? {
        if leftStack.isEmpty {
            
            // 如果此时左栈是空的, 右栈是 [3, 2, 1]
            // 进栈顺序为 3 -> 2 -> 1
            // 把右栈反向填充到左栈, 此时左栈为 [1, 2, 3]
            leftStack = rightStack.reversed()
            rightStack.removeAll()
        }
        // 出队列操作, 左栈移除最后一个元素, 3, 先进先出
        return leftStack.popLast()
    }
}
操作 最好情况 最差情况
enqueue O(1) O(1)
dequeue O(1) O(1)
空间复杂度 O(n) O(n)

树

参考文献)

树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

  • 每个节点有零个或多个子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树；

树结构主要用来：

  • 代表层级关系
  • 管理排序数据
  • 促进快速查找操作

术语

节点

树是由节点构成，每个节点封装一些数据并跟踪其子节点。

每个节点负责一个值，并且用数组持有对子节点的引用。

父节点和子节点

每个节点，除了根节点，上面都连接了一个节点，这个节点叫父节点。直接连接在父节点下方的节点叫子节点。
每个子节点只有一个父节点。

根节点

树最顶端的叫根节点

叶节点

没有子节点的节点叫叶节点或者终端节点。

实现

1
2
3
4
5
6
7
8
9
10
11
12
public class TreeNode<T> {
    public var value: T
    public var children: [TreeNode] = []
    
    public init(_ value: T) {
        self.value = value
    }
    
    public func add(_ child: TreeNode) {
        children.append(child)
    }
}

二叉树

参考文献

二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

与普通树不同，普通树的节点个数至少为1，而二叉树的节点个数可以为0；普通树节点的最大分支度没有限制，而二叉树节点的最大分支度为2；普通树的节点无左、右次序之分，而二叉树的节点有左、右次序之分。

二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆，并应用于高效率的搜索和排序。

二叉树的子节点，通常被称为左右子节点。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class BinaryNode<Element> {
    public var value: Element
    public var leftChild: BinaryNode? = nil
    public var rightChild: BinaryNode? = nil
    
    public init(value: Element) {
        self.value = value
    }
}

extension BinaryNode: CustomStringConvertible {
    
    public var description: String {
        return diagram(for: self)
    }
    
    private func diagram(for node: BinaryNode?,
                         _ top: String = "",
                         _ root: String = "",
                         _ bottom: String = "") -> String {
        guard let node = node else {
            return root + "nil\n"
        }
        if node.leftChild == nil && node.rightChild == nil {
            return root + "\(node.value)\n"
        }
        return diagram(for: node.rightChild, top + " ", top + "┌──", top + "│ ")
            + root + "\(node.value)\n"
            + diagram(for: node.leftChild, bottom + "│ ", bottom + "└──", bottom + " ")
    }
}

遍历算法

In-order traversal 中序遍历

从根节点开始：

  1. 如果当前节点有左子节点，先递归访问这个子节点
  2. 然后访问当前节点本身
  3. 如果当前节点有一个右子节点，递归访问这个子节点
1
2
3
4
5
6
7
8
9
10
11
extension BinaryNode {
    
    public func traverseInOrder(visit: (Element) -> Void) {
        // 如果当前节点有左子节点，先递归访问这个子节点
        leftChild?.traverseInOrder(visit: visit)
        // 然后访问当前节点本身
        visit(value)
        // 如果当前节点有一个右子节点，递归访问这个子节点
        rightChild?.traverseInOrder(visit: visit)
    }
}

Pre-order traversal 前序遍历

  1. 首先访问当前节点自身值
  2. 如果当前节点有左子节点，递归访问这个子节点
  3. 如果当前节点有右子节点，递归访问这个子节点
1
2
3
4
5
6
7
extension BinaryNode {
    public func traversePreOrder(visit: (Element) -> ()) {
        visit(value)
        leftChild?.traversePreOrder(visit: visit)
        rightChild?.traversePreOrder(visit: visit)
    }
}

Post-order traversal 后序遍历

  1. 如果当前节点有左子节点，递归访问这个子节点
  2. 如果当前节点有右子节点，递归访问这个子节点
  3. 最后访问当前节点自身值
1
2
3
4
5
6
7
extension BinaryNode {
    public func traversePostOrder(visit: (Element) -> ()) {
        leftChild?.traversePostOrder(visit: visit)
        rightChild?.traversePostOrder(visit: visit)
        visit(value)
    }
}

二叉搜索树

参考文献

堆

一个堆是一个完整的二叉树, 也叫做二叉堆, 可以用一个数组构成

堆有两种形式:

  • Max heap - 高权重的元素有更大的值
  • Min heap - 高权重的元素有更小的值

堆属性

  • 在 Max heap 中, 父节点的值必须大于等于子节点的值, 根节点一定是最大值
  • 在 Min heap 中, 父节点的值必须小于等于子节点的值, 根节点一定是最小值
  • 一个堆一定是一个完整的二叉树, 这意味着, 每一层级必须被填上, 除了最后一级

堆的应用

  • 计算一个集合的最小或最大元素
  • 堆排
  • 生成一个优先队列 - priority queue
  • 生成图标算法, 例如 Prim's 或 Dijkstra's

不要混淆这些堆和内存堆
术语堆有时候在计算机科学中被用来只带一个内存池
内存堆是另一个不同的概念

常用操作

Basic Heap

1
2
3
4
5
6
7
8
struct Heap<Element: Equatable> {
    var elements: [Element] = []
    let sort: (Element, Element) -> Bool
    
    init(sort: @escaping (Element, Element) -> Bool) {
        self.sort = sort
    }
}

Heap Representation

用数组代表堆:

  • 左节点下标: 2i + 1
  • 右节点下标: 2i + 2
  • 父节点下标: (i - 1) / 2

向下筛选去获取左右子节点是 O(log n) 操作, 在数组中, 同样的操作为 O(1)

基本操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var isEmpty: Bool {
    return elements.isEmpty
}

var count: Int {
    return elements.count
}

func peek() -> Element? {
    return elements.first
}

func leftChildIndex(ofParentAt index: Int) -> Int {
    return (2 * index) + 1
}

func rightChildIndex(ofParentAt index: Int) -> Int {
    return (2 * index) + 2
}

func parentIndex(ofChildAt index: Int) -> Int {
    return (index - 1) / 2
}

Removing from a heap

最基本的移除操作就是移除根节点.

移除最大根节点, 你必须先交换根节点和最后一个元素

注意: max heap, 每个父节点必须必子节点的值要大, 在交换后必须向下筛选. 如果两个子节点的值, 都更大, 那就取最大的那个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/// 移除根节点
mutating func remove() -> Element? {
    
    // 如果 heap 是空的就返回 空
    guard !isEmpty else {
        return nil
    }
    
    // 交换根元素和最后一个元素
    elements.swapAt(0, count - 1)
    
    /**
     在错误处理方面，guard 和新的 throw 语法之间，Swift 2.0 也鼓励用尽早返回错误（这也是 NSHipster 最喜欢的方式）来代替嵌套 if 的处理方式。尽早返回让处理更清晰了，但是已经被初始化（可能也正在被使用）的资源必须在返回前被处理干净。
     
     新的 defer 关键字为此提供了安全又简单的处理方式：声明一个 block，当前代码执行的闭包退出时会执行该 block
     */
    defer {
        // 向下筛选以确保是一个 max heap 或者 min heap
        siftDown(from: 0)
    }
    
    // 移除最后一个元素, 并返回
    return elements.removeLast()
}

/// 向下筛选
mutating func siftDown(from index: Int) {
    
    // 记录父节点 index
    var parent = index
    
    // 不断向下筛选, 直到 return
    while true {
        
        // 得到左节点和右节点的 index
        let left = leftChildIndex(ofParentAt: parent)
        let right = rightChildIndex(ofParentAt: parent)
        
        // 记录候选节点 index
        var candidate = parent
        
        // 如果有左节点, 并且左节点的值高于父节点的值, 那么替换候选节点为左节点
        if left < count && sort(elements[left], elements[candidate]) {
            candidate = left
        }
        
        // 如果有右节点, 并且右节点比左节点的值更高, 那么替换候选节点为右节点
        if right < count && sort(elements[right], elements[candidate]) {
            candidate = right
        }
        
        // 如果候选节点和父节点是一样的, 直接 return 结束循环
        if candidate == parent {
            return
        }
        
        // 替换父节点和子节点的值
        elements.swapAt(parent, candidate)
        
        // 重新赋值父节点, 进入下一次向下筛选
        parent = candidate
    }
}

时间复杂度: remove()方法总体时间复杂度是 O(log n) - 数组中交换元素的复杂度是 O(1), 向下筛选的操作复杂度是 O(log n)

插入操作

首先, 在最后一个节点插入值, 然后检查这个完整二叉树还是不是一个最大堆或最小堆, 如果不是, 则要通过和父节点比较, 进行向上筛选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
mutating func insert(_ element: Element) {
    elements.append(element)
    siftUp(from: elements.count - 1)
}

mutating func siftUp(from index: Int) {
    var child = index
    var parent = parentIndex(ofChildAt: index)
    
    // 如果子节点不是根节点, 且子节点的值大于或小于父节点
    while child > 0 && sort(elements[child], elements[parent]) {
        
        // 交换两个节点的值
        elements.swapAt(child, parent)
        // 更换子节点下标
        child = parent
        // 重新查找父节点
        parent = parentIndex(ofChildAt: child)
    }
}

时间复杂度: 总共的 insert(_:) 复杂度是 O(log n), 给数组添加元素的操作是 O(1), 向上筛选的复杂度是 O(log n)

O(n2) 算法

Bubble sort

1
2
3
4
5
6
7
8
9
10
// Bubble sort
func bubbleSort(_ array: inout [Int]) {
    for i in (1 ..< array.count).reversed() {
        for j in 0 ..< i  {
            if array[j] > array[j+1] {
                array.swapAt(j, j + 1)
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
for (NSInteger i = 0; i < mutableArray.count; ++i) {
    for (NSInteger j = 0; j < mutableArray.count - 1; ++j) {
        if (mutableArray[j].integerValue > mutableArray[j+1].integerValue) {
            temp = [mutableArray[j] integerValue];
            mutableArray[j] = mutableArray[j+1];
            mutableArray[j + 1] = @(temp);
        }
    }
}

Selection sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Selection sort
func selectionSort(_ array: inout [Int]) {
    for current in 0 ..< array.count - 1 {
        var lowest = current
        for other in (current + 1) ..< array.count {
            if array[lowest] > array[other] {
                lowest = other
            }
        }
        if lowest != current {
            array.swapAt(lowest, current)
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
for (NSInteger current = 0; current < mutableArray.count - 1; current++) {
    NSInteger lowest = current;
    for (NSInteger other = current + 1; other < mutableArray.count; other++) {
        if (mutableArray[lowest].integerValue > mutableArray[other].integerValue) {
            lowest = other;
        }
    }
    
    if (lowest != current) {
        [mutableArray exchangeObjectAtIndex:current withObjectAtIndex:lowest];
    }
}

Insertion sort

1
2
3
4
5
6
7
8
9
10
11
12
// Insertion sort
func insertionSort(_ array: inout [Int]) {
    for current in 1 ..< array.count {
        for shifting in (1...current).reversed() {
            if array[shifting] < array[shifting - 1] {
                array.swapAt(shifting, shifting - 1)
            } else {
                break
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
for (NSInteger i = 1; i < mutableArray.count; i++) {
    for (NSInteger j = i; j > 0; j--) {
        if (mutableArray[j].integerValue < mutableArray[j - 1].integerValue) {
            [mutableArray exchangeObjectAtIndex:j withObjectAtIndex:j - 1];
        } else {
            break;
        }
    }
}

Merge sort (归并排序)

参考文献

归并排序是创建在归并操作上的一种有效的排序算法, 效率为 O(nlogn)
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func mergeSort<Element>(_ array: [Element]) -> [Element] where Element: Comparable {
    
    guard array.count > 1 else {
        return array
    }
    let middle = array.count / 2
    let left = mergeSort(Array(array[..<middle]))
    let right = mergeSort(Array(array[middle...]))
    let merged = merge(left, right)
    return merged
}

func merge<Element>(_ left: [Element], _ right: [Element]) -> [Element] where Element: Comparable {
    
    var leftIndex = 0
    var rightIndex = 0
    
    var result: [Element] = []
    
    while leftIndex < left.count && rightIndex < right.count {
        let leftElement = left[leftIndex]
        let rightElement = right[rightIndex]
        
        if leftElement < rightElement {
            result.append(leftElement)
            leftIndex += 1
        } else if rightElement < leftElement {
            result.append(rightElement)
            rightIndex += 1
        } else {
            result.append(leftElement)
            leftIndex += 1
            result.append(rightElement)
            rightIndex += 1
        }
    }
    
    if leftIndex < left.count {
        result.append(contentsOf: left[leftIndex...])
    }
    if rightIndex < right.count {
        result.append(contentsOf: right[rightIndex...])
    }
    
    return result
}

Quicksort (快速排序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Naive
func quicksortNaive<T: Comparable>(_ a: [T]) -> [T] {
    
    guard a.count > 1 else {
        return a
    }
    
    let pivot = a[a.count / 2]
    let less = a.filter { $0 < pivot }
    let equal = a.filter { $0 == pivot }
    let greater = a.filter { (num) -> Bool in
        return num > pivot
    }
    return quicksortNaive(less) + equal + quicksortNaive(greater)
}

// Lomuto
func partitionLomuto(_ a: inout [Int], low: Int, high: Int) -> Int {
    let pivot = a[high]
    var i = low
    for j in low..<high {
        if a[j] <= pivot {
            a.swapAt(i, j)
            i += 1
        }
    }
    a.swapAt(i, high)
    
    return i
}

func quicksort(_ a: inout [Int], low: Int, high: Int) {
    if low < high {
        let pivot = partitionLomuto(&a, low: low, high: high)
        quicksort(&a, low: low, high: pivot - 1)
        quicksort(&a, low: pivot + 1, high: high)
    }
}

Heap sort (堆排序)

参考文献