1. 数据结构

数据结构（英语： data structure ）是计算机中存储、组织数据的方式。

数据结构 (data structure) 是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带 “结构” 的数据元素的集合。“结构” 就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

数据结构

常用的数据结构：

数组 (Array)
栈 (Stack)
队列 (Queue)
链表 (Linked List)
树 (Tree)
图 (Graph)
堆 (Heap)
散列表 (Hash)

1.1 链表、栈和队列的 Swift 实现

1.1.1 链表 (Linked List)

链表是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。链表可分为单向链表，双向链表以及循环链表。下文以双向链表为例。

1.1.1.1 节点的抽象数据类型

抽象数据类型 (ADT，Abstract Data Type) 是指一个数学模型以及定义在此数学模型上的一组操作。它通常是对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。

ADT 节点(node)

Data
  value: 持有的数据

Operation
  init: 初始化
  previous: 指向上一节点的指针
  next: 指向下一节点的指针

endADT

1.1.1.2 节点的实现

public class LinkedListNode<T> {
  public var value: T
  
  public var previous: LinkedListNode?
  
  public var next: LinkedListNode?
  
  public init(value: T) {
    self.value = value
  }
}

1.1.1.3 双向链表的抽象数据类型

ADT 链表（linked list）

Data
  linked list: 持有的线性表

Operation
  init: 初始化
  count: 持有节点总个数
  isEmpty: 是否为空
  first: 头节点
  last: 尾节点
  node: 传入 index 返回节点
  insert: 插入 node 到指定 index
  insertToHead: 插入节点到表头
  appendToTail: 插入节点到表尾
  removeAll: 移除所有节点
  remove: 移除传入的节点
  removeAt: 移除传入 index 的节点

endADT

1.1.1.4 双向链表的实现

public class LinkedList<T> {
  public typealias Node = LinkedListNode<T>
  
  /// first node pointer
  private var head: Node?
  
  /// first node pointer
  public var first: Node? { return head }
  
  /// last node pointer
  public var last: Node? {
    guard var node = head else { return nil }
    
    while let next = node.next {
      node = next
    }
    
    return node
  }
  
  public var isEmpty: Bool { return head == nil }
  
  /// total count of nodes
  public var count: Int {
    guard var node = head else { return 0 }
    
    var count = 1
    while let next = node.next {
      node = next
      count += 1
    }
    
    return count
  }
}

// MARK: - insert node
extension LinkedList {
  /// get node of index
  public func node(atIndex index: Int) -> Node? {
    guard index < count else { return nil }
    
    var node = head
    
    for _ in 0..<index {
      node = node?.next
    }
    
    return node
  }
  
  /// insert node to tail
  public func appendToTail(node: Node) {
    let newNode = node
    
    if let lastNode = last {
      newNode.previous = lastNode
      lastNode.next = newNode
    } else {
      head = newNode
    }
  }
  
  /// insert node to head
  public func insertToFirst(node: Node) {
    let newHead = node
    
    if head == nil {
      head = newHead
    } else {
      newHead.next = head
      head?.previous = newHead
      head = newHead
    }
  }
  
  /// insert node to specific index
  public func insert(_ node: Node, atIndex index: Int) {
    guard index >= 0 else {
      print("invalid input index")
      return
    }
    
    let newNode = node
    
    if count == 0 || index == 0 {
      insertToFirst(node: newNode)
    } else {
      guard index < count else {
        print("out of range")
        return
      }
      
      let prev = self.node(atIndex: index - 1)
      let next = prev?.next
      
      newNode.previous = prev
      newNode.next = next
      prev?.next = newNode
      next?.previous = newNode
    }
  }
}

// MARK: - remove node
extension LinkedList {
  /// removing all nodes
  public func removeAll() {
    head = nil
  }
  
  /// remove a node
  public func remove(node: Node) -> T? {
    guard head != nil else {
      print("linked list is empty")
      return nil
    }
    
    let prev = node.previous
    let next = node.next
    next?.previous = prev
    
    if let prev = prev {
      prev.next = next
    } else {
      head = next
    }
    
    node.previous = nil
    node.next = nil
    
    return node.value
  }
  
  /// remove a node by it's index
  public func remove(_ index: Int) -> T? {
    guard !isEmpty else {
      print("linked list is empty")
      return nil
    }
    
    guard let node = self.node(atIndex: index) else {
      return nil
    }
    
    return remove(node: node)
  }
  
  /// remove last node
  public func removeLast() -> T? {
    guard let last = last else {
      return nil
    }
    
    return remove(node: last)
  }
}

// MARK: - print all nodes
extension LinkedList {
  /// print all nodes
  public func printAllNodes() {
    var node = head
    
    for index in 0..<count {
      if node == nil { break }
      
      print("[\(index)]\(node!.value)")
      
      node = node?.next
    }
  }
}

1.1.2 栈 (Stack)

堆叠（英语： stack）又称为栈或堆迭，是计算机科学中的一种抽象资料型別，只允许在有序的线性资料集合的一端（称为堆叠顶端，英语： top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。

1.1.2.1 栈的抽象数据模型

ADT 栈（Stack）

Data
  linked list:持有的线性表

Operation
  init:初始化
  count:栈的元素个数
  isEmpty:是否为空
  push:入栈
  pop:出栈
  top:返回顶部元素

endADT

1.1.2.2 栈的实现

将数组（顺序存储）作为栈的线性表的实现。

public struct Stack<T> {
  private var stackArray = [T]()
  
  public var count: Int {
    return stackArray.count
  }
  
  public var isEmpty: Bool {
    return stackArray.isEmpty
  }
  
  public var top: T? {
    return stackArray.last
  }
}

extension Stack {
  /// push operation
  public mutating func push(_ element: T) {
    stackArray.append(element)
  }
  
  /// pop operation
  public mutating func pop() -> T? {
    guard !stackArray.isEmpty else {
      print("stack is empty")
      return nil
    }
    
    return stackArray.removeLast()
  }
  
  /// print all elements
  public mutating func printAllElements() {
    for (index, value) in stackArray.enumerated() {
      print("[\(index)]\(value)")
    }
  }
}

1.1.3 队列 (Queue)

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

1.1.3.1 队列的抽象数据模型

ADT 队列（Queue）

Data
  linked list:持有的线性表

Operation
  init:初始化
  count:栈的元素个数
  isEmpty:是否为空
  front:获取队列头元素
  enqueue:插入到队尾
  dequeue:删除队列头元素并返回

endADT

1.1.3.2 队列的实现

public struct Queue<T> {
  private var queueArray = [T]()
  
  public var count: Int {
    return queueArray.count
  }
  
  public var isEmpty: Bool {
    return queueArray.isEmpty
  }
  
  public var front: T? {
    return queueArray.first
  }
}

extension Queue {
  /// add element
  public mutating func enqueue(_ element: T) {
    queueArray.append(element)
  }
  
  /// remove element
  public mutating func dequeue() -> T? {
    if queueArray.isEmpty {
      return nil
    }
    return queueArray.removeFirst()
  }
  
  public mutating func printAllElements() {
    for (index, value) in queueArray.enumerated() {
      print("[\(index)]\(value)")
    }
  }
}

2. 排序算法

算法复杂度分为时间复杂度和空间复杂度。

| 排序算法 | 平均情况 | 最好情况 | 最坏情况 | 稳定性 | 空间复杂度 |
| :—: | :—: | :—: | :—: | :—: | :—: | :—: |
| 冒泡 | O(n²) | O(n) | O(n²) | 稳定 | O(1) |
| 选择排序 | O(n²) | O(n²) | O(n²) | 不稳定 | O(1) |
| 插入排序 | O(n²) | O(n) | O(n²) | 稳定 | O(1) |
| 希尔排序 | O(nlogn) | 依赖步长 | 依赖步长 | 稳定 | O(1) |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | 稳定 | O(1) |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | 稳定 | O(n) |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | 不稳定 | O(logn) |

2.1 冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

public func sort(_ array: inout [Int]) {
  var isSorted = true
  
  for i in 0..<array.count - 1 {
    for j in 0..<array.count - 1 - i {
      if array[j] > array[j + 1] {
        array.swapAt(j, j + 1)
        
        isSorted = false
      }
    }
    
    if isSorted { break }
  }
}

2.2 选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

public func sort(_ array: inout [Int]) {
  for i in 0..<array.count {
    var min = i
    for j in i + 1..<array.count {
      if array[j] < array[min] {
        min = j
      }
    }
    array.swapAt(i, min)
  }
}

2.3 插入排序

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

public func sort(_ array: inout [Int]) {
  for i in 1..<array.count {
    var j = i
    while j > 0, array[j] < array [j - 1] {
      array.swapAt(j, j - 1)
      j -= 1
    }
  }
}

2.4 归并排序

采用分治法:
分割：递归地把当前序列平均分割成两半。
整合：在保持元素顺序的同时将上一步得到的子序列整合到一起（归并）。

public func sort(_ array: [Int]) -> [Int] {
  guard array.count > 1 else { return array }
  
  let middleIndex = array.count / 2
  let leftArray = sort(Array(array[0..<middleIndex]))
  let rightArray = sort(Array(array[middleIndex..<array.count]))
  return _merge(leftArray: leftArray, rightArray: rightArray)
}

private func _merge(leftArray: [Int], rightArray: [Int]) -> [Int] {
  var leftIndex = 0, rightIndex = 0, sortedArray = [Int]()
  
  while leftIndex < leftArray.count, rightIndex < rightArray.count {
    if leftArray[leftIndex] < rightArray[rightIndex] {
      sortedArray.append(leftArray[leftIndex])
      leftIndex += 1
    } else if leftArray[leftIndex] > rightArray[rightIndex] {
      sortedArray.append(rightArray[rightIndex])
      rightIndex += 1
    } else {
      sortedArray.append(leftArray[leftIndex])
      leftIndex += 1
      sortedArray.append(rightArray[rightIndex])
      rightIndex += 1
    }
  }
  
  // leftArray is not empty
  while leftIndex < leftArray.count {
    sortedArray.append(leftArray[leftIndex])
    leftIndex += 1
  }
  
  // right array is not empty
  while rightIndex < rightArray.count {
    sortedArray.append(rightArray[rightIndex])
    rightIndex += 1
  }
  
  return sortedArray
}

2.5 快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的 2 个子序列，然后递归地排序两个子序列。

public func sort(_ array: [Int]) -> [Int] {
  guard array.count > 1 else { return array }
  
  let pivot = array[array.count / 2]
  let leftArray = array.filter { $0 < pivot }
  let equalArray = array.filter { $0 == pivot }
  let rightArray = array.filter { $0 > pivot }
  
  return sort(leftArray) + equalArray + sort(rightArray)
}

数据结构和排序算法 in Swift