Swift算法与数据结构：初学者完整课程

Swift算法与数据结构入门

Swift是Apple为开发iOS、macOS、watchOS和tvOS应用程序而创建的强大且直观的编程语言。然而，要编写高效且快速的代码，仅仅了解语法是不够的。理解算法与数据结构是将新手转变为专业开发人员的基础。

在本文中，我们将介绍Swift中的基本数据结构（数组、字典、集合）和关键算法（排序、搜索）。所有代码示例均可在Xcode Playground中直接运行。

Swift中的主要数据结构

Swift提供了内置的数据结构，这些结构在内存和性能方面都经过了优化。让我们来看看三个最重要的数据结构。

数组（Array）

数组是相同类型元素的有序集合。在Swift中，数组是强类型的，并且具有固定的顺序。

// 创建数组var numbers: [Int] = [1, 2, 3, 4, 5]

// 添加元素numbers.append(6)

// 通过索引访问let first = numbers[0] // 1

// 迭代for number in numbers {    print(number)}

// 原地排序numbers.sort() // [1, 2, 3, 4, 5, 6]

当元素的顺序很重要且需要快速按索引访问（O(1)）时，数组是理想的选择。然而，在数组开头插入或删除元素需要O(n)时间。

字典（Dictionary）

字典存储“键-值”对。键必须是唯一的并且是可哈希的（例如String、Int）。

// 创建字典var scores: [String: Int] = ["Alice": 95, "Bob": 87]

// 添加或更新scores["Charlie"] = 92

// 获取值（可选）if let aliceScore = scores["Alice"] {    print("Alice's score: \\(aliceScore)")}

// 删除scores.removeValue(forKey: "Bob")

字典平均提供O(1)时间复杂度的按键访问。当数据自然地按唯一键分组时，请使用字典。

集合（Set）

集合是唯一元素的无序集合。它对于检查成员资格和删除重复项非常有用。

// 创建集合var fruits: Set<String> = ["Apple", "Banana", "Orange"]

// 添加fruits.insert("Mango")

// 检查是否存在if fruits.contains("Apple") {    print("Apple is in the set")}

// 从数组中删除重复项let arrayWithDuplicates = [1, 1, 2, 3, 3, 4]let uniqueSet = Set(arrayWithDuplicates) // {1, 2, 3, 4}

Swift中的基本算法

现在，让我们应用数据结构来解决典型问题。我们将介绍排序和搜索。

排序算法

Swift有内置的sort()函数，但为了理解原理，我们编写经典的快速排序（Quick Sort）算法。

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, 1, 8, 2, 9, 4]let sorted = quickSort(unsorted)print(sorted) // [1, 2, 3, 4, 6, 8, 9]

快速排序是最有效的算法之一，平均时间复杂度为O(n log n)。对于小型数组，可以使用内置的sorted()方法。

搜索算法

线性搜索简单但速度慢（O(n)）。对于已排序的数据，请使用二分搜索（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)