iOS开发实战：多算法实现有序数组中位数求解

2026年1月20日 互联网

一、问题背景与算法选择

在iOS开发面试或算法竞赛中，合并两个有序数组并求解中位数是高频考点。该问题要求在O(log(m+n))时间复杂度内完成，但本文将通过三种基础排序算法的实现，帮助开发者理解不同算法的适用场景与优化空间。

1.1 问题定义

给定两个非递减顺序的整数数组nums1和nums2，合并后找到新数组的中位数。若合并后长度为偶数，则返回中间两个数的平均值。

1.2 算法选择依据

  • 冒泡排序：适合教学演示，但时间复杂度较高（O(n²)）
  • 选择排序：通过每次选择最小值优化比较次数
  • 插入排序：对小规模有序数据效率较高

二、冒泡排序实现方案

2.1 算法原理

通过相邻元素比较交换，将较大值逐步”冒泡”至数组末端。合并两个数组后执行冒泡排序，最后根据数组长度奇偶性返回中位数。

2.2 Swift代码实现

  1. func findMedianSortedArraysBubble(_ nums1: [Int], _ nums2: [Int]) -> Double {
  2.     var merged = nums1 + nums2
  3.     let n = merged.count
  5.     // 冒泡排序
  6.     for i in 0..<n {
  7.         for j in 0..<n-i-1 {
  8.             if merged[j] > merged[j+1] {
  9.                 merged.swapAt(j, j+1)
  10.             }
  11.         }
  12.     }
  14.     // 计算中位数
  15.     if n % 2 == 0 {
  16.         return Double(merged[n/2 - 1] + merged[n/2]) / 2.0
  17.     } else {
  18.         return Double(merged[n/2])
  19.     }
  20. }

2.3 性能分析

  • 时间复杂度：O((m+n)²)
  • 空间复杂度：O(m+n)（需存储合并数组）
  • 适用场景：教学演示或极小规模数据

三、选择排序优化方案

3.1 算法改进点

通过每次循环选择两个数组中的最小值，避免全量排序。使用双指针遍历两个数组，动态维护当前最小值。

3.2 Swift代码实现

  1. func findMedianSortedArraysSelection(_ nums1: [Int], _ nums2: [Int]) -> Double {
  2.     var merged = [Int]()
  3.     var i = 0, j = 0
  4.     let total = nums1.count + nums2.count
  6.     // 合并数组（选择排序思想）
  7.     while merged.count < (total + 1) / 2 {
  8.         if i < nums1.count && (j >= nums2.count || nums1[i] <= nums2[j]) {
  9.             merged.append(nums1[i])
  10.             i += 1
  11.         } else {
  12.             merged.append(nums2[j])
  13.             j += 1
  14.         }
  15.     }
  17.     // 计算中位数
  18.     if total % 2 == 0 {
  19.         let next = merged.last!
  20.         let prev = (i > 0 && j > 0) ? min(nums1[i-1], nums2[j-1]) : 
  21.                    (i > 0 ? nums1[i-1] : nums2[j-1])
  22.         return Double(prev + next) / 2.0
  23.     } else {
  24.         return Double(merged.last!)
  25.     }
  26. }

3.3 优化效果

  • 时间复杂度：O(m+n)
  • 空间复杂度：O((m+n)/2)（仅存储前半部分）
  • 改进点：减少不必要的完整排序

四、插入排序的渐进优化

4.1 算法特性

对已部分有序的数据效率较高，可通过二分查找优化插入位置。本方案采用双指针+插入排序的混合策略。

4.2 Swift代码实现

  1. func findMedianSortedArraysInsertion(_ nums1: [Int], _ nums2: [Int]) -> Double {
  2.     var merged = [Int]()
  3.     var i = 0, j = 0
  5.     // 双指针合并（插入排序思想）
  6.     while i < nums1.count || j < nums2.count {
  7.         if i >= nums1.count {
  8.             merged.append(nums2[j])
  9.             j += 1
  10.         } else if j >= nums2.count {
  11.             merged.append(nums1[i])
  12.             i += 1
  13.         } else if nums1[i] <= nums2[j] {
  14.             merged.append(nums1[i])
  15.             i += 1
  16.         } else {
  17.             merged.append(nums2[j])
  18.             j += 1
  19.         }
  20.     }
  22.     // 计算中位数（优化版）
  23.     let mid = merged.count / 2
  24.     return merged.count % 2 == 0 ? 
  25.            Double(merged[mid-1] + merged[mid]) / 2.0 : 
  26.            Double(merged[mid])
  27. }

4.3 性能对比

算法 时间复杂度 空间复杂度 适用场景
冒泡排序 O(n²) O(n) 教学演示
选择排序优化 O(m+n) O(n/2) 中等规模有序数据
插入排序优化 O(m+n) O(m+n) 需要稳定排序的场景

五、工程化实践建议

  1. 算法选择策略：

    • 小规模数据（n<100）：插入排序
    • 中等规模数据：选择排序优化
    • 超大规模数据：考虑二分查找+双指针（O(log(m+n))方案）

  2. Swift语言优化：

    1. // 使用Swift特有语法优化
    2. func optimizedMerge(_ nums1: [Int], _ nums2: [Int]) -> Double {
    3.     var merged = nums1 + nums2
    4.     merged.sort() // 使用Swift内置排序（Timsort变种）
    6.     let count = merged.count
    7.     let mid = count / 2
    8.     return count % 2 == 0 ? 
    9.            (Double(merged[mid-1]) + Double(merged[mid])) / 2 : 
    10.            Double(merged[mid])
    11. }

  3. 测试用例设计：

    1. func testMedianAlgorithms() {
    2.     let testCases = [
    3.         ([1, 3], [2], 2.0),
    4.         ([1, 2], [3, 4], 2.5),
    5.         ([0, 0], [0, 0], 0.0),
    6.         ([], [1], 1.0),
    7.         ([2], [], 2.0)
    8.     ]
    10.     testCases.forEach { (nums1, nums2, expected) in
    11.         assert(findMedianSortedArraysBubble(nums1, nums2) == expected)
    12.         assert(findMedianSortedArraysSelection(nums1, nums2) == expected)
    13.         assert(findMedianSortedArraysInsertion(nums1, nums2) == expected)
    14.     }
    15. }

六、进阶方向

  1. O(log(m+n))算法实现：

    • 采用二分查找定位中位数位置
    • 通过比较两个数组的中间元素动态调整搜索范围

  2. 通用化扩展：

    • 支持K个有序数组的中位数求解
    • 添加权重参数实现加权中位数计算

  3. 性能监控：

    1. func benchmarkAlgorithm(_ algorithm: ([Int], [Int]) -> Double, 
    2.                        _ nums1: [Int], _ nums2: [Int]) {
    3.     let start = DispatchTime.now()
    4.     let _ = algorithm(nums1, nums2)
    5.     let end = DispatchTime.now()
    6.     let nanoTime = end.uptimeNanoseconds - start.uptimeNanoseconds
    7.     let timeInterval = Double(nanoTime) / 1_000_000_000
    8.     print("耗时: \(timeInterval)秒")
    9. }

本文通过三种算法实现方案，系统展示了iOS开发中处理有序数组合并问题的不同思路。开发者可根据实际场景选择合适方案，同时建议掌握二分查找的终极优化方法以应对大规模数据挑战。

最新文章