面试题：Swift 算法实现之排序算法对比

Question

请用 Swift 分别实现冒泡排序和快速排序算法，并简要分析两者在时间复杂度和空间复杂度上的差异。

Answer 1

冒泡排序

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)
            }
        }
    }
}

快速排序

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(n²)，因为每次比较都要遍历几乎整个数组。在最好情况下，即数组已经有序，时间复杂度为 O(n)，只需要遍历一次数组就可以确认顺序。
• 快速排序：平均时间复杂度为 O(n log n)，因为每次划分大致可以将数组分为两半。但在最坏情况下（如每次选取的基准值都是数组中的最大或最小值），时间复杂度退化为 O(n²) 。

空间复杂度分析

• 冒泡排序：空间复杂度为 O(1)，因为只需有限的额外空间用于交换元素。
• 快速排序：递归实现的快速排序空间复杂度主要取决于递归调用的深度，平均情况下空间复杂度为 O(log n)，最坏情况下（如数组已经有序）空间复杂度为 O(n)。非递归实现（使用栈辅助）平均空间复杂度同样为 O(log n)，最坏为 O(n) 。