Swift 算法与数据结构：完整指南

Swift算法与数据结构：从新手到专家

Swift是Apple推出的强大且直观的编程语言，用于开发iOS、macOS、watchOS和tvOS应用。理解算法与数据结构是区分经验丰富的开发者和新手的基石。本文将通过Swift的实际示例，解析关键概念。

1. Swift中的基本数据结构

Swift标准库提供了几种内置结构，它们是任何应用的基础。

数组 (Array)

相同类型元素的有序集合。支持通过索引进行随机访问。

var numbers: [Int] = [10, 20, 30, 40, 50]numbers.append(60)numbers.insert(5, at: 0)print(numbers[2]) // 输出: 30

字典 (Dictionary)

键值对集合，用于通过唯一键快速查找数据。

var userScores: [String: Int] = ["Alice": 95, "Bob": 87]userScores["Charlie"] = 92if let score = userScores["Alice"] {    print("Alice's score: \\(score)")}

集合 (Set)

无序的唯一元素集合。非常适合检查存在性或删除重复项。

let fruits: Set = ["Apple", "Banana", "Orange", "Apple"]print(fruits.count) // 输出: 3 (重复项已删除)

2. 在Swift中实现栈和队列

栈和队列是经典的数据结构，通常基于数组实现。

栈 (Stack) — LIFO (后进先出)

元素从同一端添加和移除。

struct Stack<T> {    private var elements: [T] = []        mutating func push(_ value: T) {        elements.append(value)    }        mutating func pop() -> T? {        return elements.popLast()    }        func peek() -> T? {        return elements.last    }}

var stack = Stack<Int>()stack.push(1)stack.push(2)stack.push(3)print(stack.pop()!) // 输出: 3

队列 (Queue) — FIFO (先进先出)

元素从尾部添加，从头部移除。

struct Queue<T> {    private var elements: [T] = []        mutating func enqueue(_ value: T) {        elements.append(value)    }        mutating func dequeue() -> T? {        return elements.isEmpty ? nil : elements.removeFirst()    }}

var queue = Queue<String>()queue.enqueue("First")queue.enqueue("Second")print(queue.dequeue()!) // 输出: First

3. 排序和搜索算法

让我们看看两种基础算法，它们在实际项目中非常有用。

快速排序 (Quick Sort)

高效的"分而治之"算法，平均复杂度为O(n log n)。

func quickSort(_ array: [Int]) -> [Int] {    guard array.count > 1 else { return array }        let pivot = array[array.count / 2]    let less = array.filter { $0 < pivot }    let equal = array.filter { $0 == pivot }    let greater = array.filter { $0 > pivot }        return quickSort(less) + equal + quickSort(greater)}

let unsorted = [3, 6, 8, 10, 1, 2, 1]print(quickSort(unsorted)) // 输出: [1, 1, 2, 3, 6, 8, 10]

二分搜索 (Binary Search)

仅适用于已排序数组。复杂度为O(log n)。

func binarySearch(_ array: [Int], target: Int) -> Int? {    var low = 0    var high = array.count - 1        while low <= high {        let mid = (low + high) / 2        if array[mid] == target {            return mid        } else if array[mid] < target {            low = mid + 1        } else {            high = mid - 1        }    }    return nil}

let sortedArray = [1, 3, 5, 7, 9, 11]if let index = binarySearch(sortedArray, target: 7) {    p