Swift 数组排序算法

在实际项目中，我们根本不用知道排序是怎么去实现的，每种语言都有对应的排序API。毕竟写代码最基本的算法还是要知道的，最近也在看一些简单的算法书，勾起了读大学时那段时光，挺后悔大学没有好好学习算法和数据结构，现在看看时，似曾相识，但却不知。

第一章介绍的二分查找法，如果我没记错的话，高中数学里面就有。但是二分查找法前提是数组有序。所以书中接下来介绍的都是排序算法(也有大篇幅的介绍数组和链表，不太熟的可以自行了解),也穿插介绍了递归和栈以及算法运行时间O。
先看一个简单的阶乘递归

func factorial(input: Int) -> Int {
   /// 应该是input == 1(这个被称为基线条件)的，过滤掉负数，
  if input <= 1 {
       return input
   }else {
        /// 递归条件
       return input * factorial(input: input - 1)
   }
}

对于递归应该是又爱又恨吧，合适地方使用会显得代码可读性特别强，找到递归的基线条件(防止无限循环)和递归条件就可以实现递归。

说到了递归，那就先介绍排序算法中的: 快速排序
这个算法应该是很熟悉的，基本都知道快速排序是啥回事，但是能用代码优雅的实现又是另外一回事了。快速排序的平均运行时间为O(nlogn)(最糟糕情况下为: O(n2),当递归条件比较极端时，就和选择排序一样慢)

/// 快速排序
func quickSort(array: [Int]) -> [Int] {
  if array.count < 2 {
     return array // 基线条件
  }else {
      let pivot = array[0] // 递归条件
      var lessArr: [Int] = [] ; var greater: [Int] = []
      for i in 1 ..< array.count {
        if array[i] <= pivot {
            lessArr.append(array[i])
        }else {
            greater.append(array[i])
        }
      }
     return quickSort(array: lessArr) + [pivot] + quickSort(array: greater)
  }
}

使用的是递归，没有嵌套循环。

再看看排序算法中的: 选择排序/冒泡排序
字面意思选择，就是每一趟选择最大的一个然后再跑第二趟，一直到结束。算法的平均运行时间为O(n2)。
之前有写过冒泡排序的算法，就不再复制粘贴了。
感觉大学C语言还是很用的的，里面基本都会接触到这些简单的算法。

想到怎样查找二个数组M和N中的相同元素这个问题
大概第一眼看到这句话，双重for循环搞定。仔细想下，双重for循环有问题，当M或者N中存在重复元素时，重复的元素可能会被重复统计。那么：首先数组元素去重(方法比较多，利用Map性质可以达到目的，或者先排序然后遍历)，然后双重for循环搞定。

还有其他方法可以解决:

func findCommon(arr1: [Int] , arr2: [Int]) -> [Int]{
  guard arr1.count > 0 , arr2.count > 0 else {
      return []
  }
  var list: [Int] = []
  let M = quickSort(array: arr1)
  let N = quickSort(array: arr2)
  var i = 0 ; var j = 0
  while i < M.count , j < N.count {
     if M[i] == N[j] {
          list.append(M[i])
          i = i + 1
          j = j + 1
      }else if M[i] < N[j] {
          i = i + 1
      }else {
          j = j + 1
      }
  }
  return list
}