MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Swift算法实现与性能对比分析

2021-05-216.6k 阅读

一、排序算法

1.1 冒泡排序

冒泡排序是一种简单的比较排序算法。它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。

在Swift中实现冒泡排序如下：

func bubbleSort(_ array: inout [Int]) {
    let count = array.count
    for i in 0..<count - 1 {
        for j in 0..<count - 1 - i {
            if array[j] > array[j + 1] {
                array.swapAt(j, j + 1)
            }
        }
    }
}

冒泡排序的时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。这是因为在最坏情况下，即数组完全逆序时，需要进行$n(n - 1)/2$次比较和交换操作。而在整个排序过程中，除了输入数组本身，只需要常数级别的额外空间来进行临时变量的存储。

1.2 选择排序

选择排序是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

Swift代码实现如下：

func selectionSort(_ array: inout [Int]) {
    let count = array.count
    for i in 0..<count - 1 {
        var minIndex = i
        for j in i + 1..<count {
            if array[j] < array[minIndex] {
                minIndex = j
            }
        }
        if minIndex != i {
            array.swapAt(i, minIndex)
        }
    }
}

选择排序的时间复杂度也是$O(n^2)$，空间复杂度为$O(1)$。无论数组初始状态如何，选择排序都需要进行$n(n - 1)/2$次比较，所以时间复杂度相对稳定。同样，在排序过程中仅需要常数级别的额外空间。

1.3 插入排序

插入排序是一种简单的排序算法，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

Swift实现代码如下：

func insertionSort(_ array: inout [Int]) {
    let count = array.count
    for i in 1..<count {
        let key = array[i]
        var j = i - 1
        while j >= 0 && array[j] > key {
            array[j + 1] = array[j]
            j -= 1
        }
        array[j + 1] = key
    }
}

插入排序在最好情况下，即数组已经有序时，时间复杂度为$O(n)$，因为只需要进行$n - 1$次比较，不需要移动元素。而在最坏情况下，即数组完全逆序时，时间复杂度为$O(n^2)$，需要进行$n(n - 1)/2$次比较和移动操作。空间复杂度同样为$O(1)$。

1.4 快速排序

快速排序是一种高效的排序算法，采用分治思想。它选择一个基准元素，通过一趟排序将待排序列分成两部分，其中左边部分的元素都小于基准元素，右边部分的元素都大于基准元素，然后分别对左右两部分进行递归排序。

Swift代码实现如下：

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

快速排序的平均时间复杂度为$O(nlogn)$，这是因为每次划分大致能将数组分成两个规模相近的子数组，递归深度为$logn$，每层操作次数为$n$。但在最坏情况下，例如每次选择的基准元素都是数组中的最大或最小元素时，时间复杂度会退化为$O(n^2)$。空间复杂度在平均情况下为$O(logn)$，最坏情况下为$O(n)$，这是由于递归调用需要占用栈空间。

1.5 归并排序

归并排序同样是基于分治思想的排序算法。它将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将排序好的子数组合并成一个有序的数组。

Swift代码实现如下：

func mergeSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array }
    let mid = array.count / 2
    let left = mergeSort(Array(array[0..<mid]))
    let right = mergeSort(Array(array[mid..<array.count]))
    return merge(left, right)
}

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

归并排序的时间复杂度始终为$O(nlogn)$，这是因为无论数组初始状态如何，它都需要进行$logn$层的归并操作，每层操作次数为$n$。空间复杂度为$O(n)$，因为在合并过程中需要一个额外的数组来存储临时结果。

1.6 性能对比分析

为了对比这些排序算法的性能，我们可以使用DispatchTime来记录每个算法的执行时间。以下是一个简单的性能测试代码：

import Foundation

let testArray = Array(1...10000).shuffled()

let start1 = DispatchTime.now()
var array1 = testArray
bubbleSort(&array1)
let end1 = DispatchTime.now()
let time1 = end1.uptimeNanoseconds - start1.uptimeNanoseconds
print("冒泡排序时间: \(time1) 纳秒")

let start2 = DispatchTime.now()
var array2 = testArray
selectionSort(&array2)
let end2 = DispatchTime.now()
let time2 = end2.uptimeNanoseconds - start2.uptimeNanoseconds
print("选择排序时间: \(time2) 纳秒")

let start3 = DispatchTime.now()
var array3 = testArray
insertionSort(&array3)
let end3 = DispatchTime.now()
let time3 = end3.uptimeNanoseconds - start3.uptimeNanoseconds
print("插入排序时间: \(time3) 纳秒")

let start4 = DispatchTime.now()
let array4 = quickSort(testArray)
let end4 = DispatchTime.now()
let time4 = end4.uptimeNanoseconds - start4.uptimeNanoseconds
print("快速排序时间: \(time4) 纳秒")

let start5 = DispatchTime.now()
let array5 = mergeSort(testArray)
let end5 = DispatchTime.now()
let time5 = end5.uptimeNanoseconds - start5.uptimeNanoseconds
print("归并排序时间: \(time5) 纳秒")

在实际测试中，数据规模较小时，插入排序可能表现较好，因为它的常数因子相对较小。但随着数据规模的增大，快速排序和归并排序的优势就会体现出来，平均情况下快速排序性能最佳，但归并排序稳定性更好，即相同元素的相对顺序在排序前后保持不变。冒泡排序、选择排序和插入排序在大数据规模下性能较差，因为它们的时间复杂度为$O(n^2)$。

二、搜索算法

2.1 顺序搜索

顺序搜索是一种最简单的搜索算法。它从数组的第一个元素开始，逐个检查元素，直到找到目标元素或者遍历完整个数组。

Swift代码实现如下：

func sequentialSearch(_ array: [Int], target: Int) -> Int? {
    for (index, element) in array.enumerated() {
        if element == target {
            return index
        }
    }
    return nil
}

顺序搜索的时间复杂度为$O(n)$，在最坏情况下，需要遍历整个数组才能确定目标元素不存在。空间复杂度为$O(1)$，因为只需要常数级别的额外空间。

2.2 二分搜索

二分搜索是一种高效的搜索算法，适用于有序数组。它每次将数组分成两部分，通过比较目标元素与中间元素的大小，决定在左半部分还是右半部分继续搜索。

Swift代码实现如下：

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

二分搜索的时间复杂度为$O(logn)$，因为每次比较都能将搜索范围缩小一半。空间复杂度为$O(1)$，只需要几个变量来记录搜索范围。

2.3 性能对比分析

同样使用DispatchTime来对比顺序搜索和二分搜索的性能。

let sortedArray = Array(1...10000).sorted()
let target = 5000

let start1 = DispatchTime.now()
_ = sequentialSearch(sortedArray, target: target)
let end1 = DispatchTime.now()
let time1 = end1.uptimeNanoseconds - start1.uptimeNanoseconds
print("顺序搜索时间: \(time1) 纳秒")

let start2 = DispatchTime.now()
_ = binarySearch(sortedArray, target: target)
let end2 = DispatchTime.now()
let time2 = end2.uptimeNanoseconds - start2.uptimeNanoseconds
print("二分搜索时间: \(time2) 纳秒")

可以明显看出，在有序数组且数据规模较大时，二分搜索的性能远远优于顺序搜索。这是因为二分搜索利用了数组的有序性，大大减少了搜索次数。但如果数组无序，使用二分搜索前需要先进行排序，这会带来额外的时间开销。

三、字符串匹配算法

3.1 暴力匹配算法

暴力匹配算法是最简单的字符串匹配算法。它将模式串与主串的每一个可能位置进行比较，直到找到匹配的子串或者遍历完主串。

Swift代码实现如下：

func bruteForceSearch(_ text: String, _ pattern: String) -> Int? {
    let textChars = Array(text)
    let patternChars = Array(pattern)
    let textLength = textChars.count
    let patternLength = patternChars.count
    for i in 0..<textLength - patternLength + 1 {
        var match = true
        for j in 0..<patternLength {
            if textChars[i + j] != patternChars[j] {
                match = false
                break
            }
        }
        if match {
            return i
        }
    }
    return nil
}

暴力匹配算法的时间复杂度为$O(m * n)$，其中$m$是模式串的长度，$n$是主串的长度。在最坏情况下，需要对主串的每一个位置都进行模式串长度次比较。空间复杂度为$O(1)$，只需要常数级别的额外空间。

3.2 KMP算法

KMP（Knuth - Morris - Pratt）算法是一种高效的字符串匹配算法。它通过预处理模式串，构建部分匹配表（也称为next数组），从而在匹配过程中能够跳过一些不必要的比较。

Swift代码实现如下： func computeLPSArray(_ pattern: String) -> [Int] { let patternChars = Array(pattern) let m = patternChars.count var lps = [Int](repeating: 0, count: m) var len = 0 lps[0] = 0 var i = 1 while i < m { if patternChars[i] == patternChars[len] { len += 1 lps[i] = len i += 1 } else { if len != 0 { len = lps[len - 1] } else { lps[i] = 0 i += 1 } } } return lps }

func KMPSearch(_ text: String, _ pattern: String) -> Int? { let textChars = Array(text) let patternChars = Array(pattern) let n = textChars.count let m = patternChars.count let lps = computeLPSArray(pattern) var i = 0 var j = 0 while i < n { if patternChars[j] == textChars[i] { i += 1 j += 1 } if j == m { return i - j } else if i < n && patternChars[j] != textChars[i] { if j != 0 { j = lps[j - 1] } else { i += 1 } } } return nil }

KMP算法的时间复杂度为$O(m + n)$，其中$m$是模式串的长度，$n$是主串的长度。这是因为预处理模式串构建next数组的时间复杂度为$O(m)$，匹配过程的时间复杂度为$O(n)$。空间复杂度为$O(m)$，因为需要额外的数组来存储next数组。

### 3.3 性能对比分析
使用`DispatchTime`来对比暴力匹配算法和KMP算法的性能：
```swift
let longText = "a".repeatElement(count: 10000)
let pattern = "aaab"

let start1 = DispatchTime.now()
_ = bruteForceSearch(longText, pattern)
let end1 = DispatchTime.now()
let time1 = end1.uptimeNanoseconds - start1.uptimeNanoseconds
print("暴力匹配算法时间: \(time1) 纳秒")

let start2 = DispatchTime.now()
_ = KMPSearch(longText, pattern)
let end2 = DispatchTime.now()
let time2 = end2.uptimeNanoseconds - start2.uptimeNanoseconds
print("KMP算法时间: \(time2) 纳秒")

可以看到，在主串和模式串长度较大时，KMP算法的性能优势明显。这是因为KMP算法利用next数组避免了大量不必要的字符比较，从而提高了匹配效率。而暴力匹配算法在每次失配时都需要重新从主串的下一个位置开始比较，效率较低。

四、图算法

4.1 深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索图的算法。它从起始顶点开始，沿着一条路径尽可能深地探索下去，直到无法继续或者达到目标顶点，然后回溯到上一个顶点，继续探索其他路径。

假设我们使用邻接表来表示图，Swift代码实现如下：

class Graph {
    var vertices: Int
    var adjList: [[Int]]
    init(vertices: Int) {
        self.vertices = vertices
        adjList = Array(repeating: [], count: vertices)
    }
    func addEdge(_ u: Int, _ v: Int) {
        adjList[u].append(v)
        adjList[v].append(u)
    }
    func DFS(_ v: Int, _ visited: inout [Bool]) {
        visited[v] = true
        print(v, terminator: " ")
        for i in adjList[v] {
            if!visited[i] {
                DFS(i, &visited)
            }
        }
    }
    func DFSUtil() {
        var visited = [Bool](repeating: false, count: vertices)
        for i in 0..<vertices {
            if!visited[i] {
                DFS(i, &visited)
            }
        }
    }
}

深度优先搜索的时间复杂度为$O(V + E)$，其中$V$是顶点数，$E$是边数。这是因为在遍历图的过程中，每个顶点和每条边最多被访问一次。空间复杂度为$O(V)$，用于存储顶点的访问状态和递归调用栈。

4.2 广度优先搜索（BFS）

广度优先搜索也是一种遍历图的算法。它从起始顶点开始，首先访问所有与起始顶点相邻的顶点，然后再依次访问这些相邻顶点的相邻顶点，以此类推，按照层次顺序进行搜索。

Swift代码实现如下：

class Graph {
    var vertices: Int
    var adjList: [[Int]]
    init(vertices: Int) {
        self.vertices = vertices
        adjList = Array(repeating: [], count: vertices)
    }
    func addEdge(_ u: Int, _ v: Int) {
        adjList[u].append(v)
        adjList[v].append(u)
    }
    func BFS(_ s: Int) {
        var visited = [Bool](repeating: false, count: vertices)
        var queue = [Int]()
        visited[s] = true
        queue.append(s)
        while!queue.isEmpty {
            let v = queue.removeFirst()
            print(v, terminator: " ")
            for i in adjList[v] {
                if!visited[i] {
                    visited[i] = true
                    queue.append(i)
                }
            }
        }
    }
}

广度优先搜索的时间复杂度同样为$O(V + E)$，因为每个顶点和每条边也最多被访问一次。空间复杂度为$O(V)$，主要用于存储队列和顶点的访问状态。

4.3 性能对比分析

在实际应用中，DFS和BFS的性能取决于具体的问题场景。如果图的目标顶点离起始顶点较近，BFS可能更快找到目标，因为它是按层次遍历的。而DFS更适合用于探索图的连通性、寻找路径等问题。如果图的规模较大且目标顶点不确定，DFS可能会因为递归调用栈的限制而出现问题，此时BFS可以通过队列来避免栈溢出问题。但总体来说，它们在时间和空间复杂度上是相同的，性能差异主要体现在应用场景的适配性上。

五、动态规划算法

5.1 斐波那契数列

斐波那契数列是一个经典的动态规划问题。数列的定义为：$F(0) = 0$, $F(1) = 1$, $F(n) = F(n - 1) + F(n - 2)$ ($n \gt 1$)。

朴素的递归实现会有大量的重复计算，效率较低。使用动态规划可以避免这种情况。

Swift代码实现如下：

func fibonacci(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    var dp = [Int](repeating: 0, count: n + 1)
    dp[1] = 1
    for i in 2...n {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

动态规划的时间复杂度为$O(n)$，因为只需要遍历一次从2到$n$的范围。空间复杂度也为$O(n)$，用于存储中间结果。我们还可以进一步优化空间复杂度，只使用两个变量来存储最近的两个结果，这样空间复杂度可以降低到$O(1)$。

5.2 背包问题

0 - 1背包问题是一个经典的组合优化问题。给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，选择哪些物品放入背包可以使得背包的总价值最大。

Swift代码实现如下：

func knapsack(_ weights: [Int], _ values: [Int], _ capacity: Int) -> Int {
    let n = weights.count
    var dp = Array(repeating: Array(repeating: 0, count: capacity + 1), count: n + 1)
    for i in 1...n {
        for w in 1...capacity {
            if weights[i - 1] <= w {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            } else {
                dp[i][w] = dp[i - 1][w]
            }
        }
    }
    return dp[n][capacity]
}

0 - 1背包问题的时间复杂度为$O(n * W)$，其中$n$是物品的数量，$W$是背包的容量。空间复杂度为$O(n * W)$，通过优化可以降低到$O(W)$，只需要记录上一行的结果即可。

5.3 性能对比分析

对于斐波那契数列问题，动态规划相比朴素递归有了巨大的性能提升，因为避免了重复计算。在背包问题中，虽然动态规划的时间复杂度较高，但在数据规模不是特别大时，能够准确地找到最优解。如果数据规模过大，可能需要考虑近似算法来提高效率。动态规划的优势在于能够利用子问题的最优解来构建全局最优解，通过合理的状态定义和转移方程设计，可以高效地解决许多复杂的问题。

六、算法优化与注意事项

  1. 数据规模与算法选择：在实际应用中，要根据数据规模来选择合适的算法。对于小规模数据，一些简单算法可能因为常数因子小而表现更好；但对于大规模数据，时间复杂度低的算法如快速排序、归并排序、二分搜索等则更具优势。
  2. 稳定性要求：如果对数据中相同元素的相对顺序有要求，例如在排序时要保持相同元素的顺序不变，那么需要选择稳定的算法，如归并排序、插入排序等。而快速排序、选择排序等是不稳定的。
  3. 空间复杂度：在内存有限的情况下，空间复杂度也是需要考虑的重要因素。例如在处理大规模数据时，一些算法虽然时间复杂度低，但空间复杂度高，可能会导致内存不足。此时可以考虑对算法进行空间优化，如在动态规划中减少中间结果的存储。
  4. 算法实现细节：在实现算法时，要注意边界条件的处理。例如在二分搜索中，要正确处理左边界和右边界的更新，避免出现死循环或者数组越界等问题。在字符串匹配算法中，要注意主串和模式串的长度关系以及字符比较的正确性。
  5. 测试与验证：编写完算法后，要进行充分的测试，包括边界情况测试、随机数据测试等，以确保算法的正确性和稳定性。可以使用单元测试框架来自动化测试过程。

通过对以上各类算法在Swift中的实现和性能对比分析，我们可以根据具体的应用场景选择最合适的算法，从而提高程序的效率和性能。在实际开发中，不断优化算法和代码实现，是提高软件质量和性能的关键。