算法图解系列之选择排序[02] 算法图解系列之选择排序[02]

2 选择排序 O(n2)
【算法图解系列之选择排序[02]】2.2 数组和链表

// MARK: - 2.2 数组和链表 // FIXME: (1) 链表// FIXME: 1) 链表的元素可存储在内存的任何地方. // FIXME: 2) 链表的每个元素都存储了下一个元素的地址, 从而使一系列随机的内存地址串联在一起. // FIXME: 3) 链表优势: 插入元素快, 大O表示法: O(1); 劣势: 读取速度慢, 因为必须要从第一个元素获取下一个元素的地址, 以此类推. so 大O表示法: O(n)// FIXME: (2) 数组// FIXME: 1) 数组的元素存储在一块连续的内存上. // FIXME: 2) 数组优势: 读取快, 大O表示法: O(1); 劣势: 插入慢, 因为插入一个元素, 那么其后的元素地址都必须向后移动一个元素的位置大O表示法: O(n)

2.3 总结<函数表达式>

// MARK: - 总结函数表达式/** * 获取最小元素的索引 * 时间复杂度: O(n) */ func findSmallest(_ arr: Array) -> Int { var smallest = arr[0] var smallestIndex = 0 for index in 1 ..< arr.count { if smallest > arr[index] { smallest = arr[index] smallestIndex = index } }return smallestIndex }/** * 选择排序从小到大 *时间复杂度: (n + n-1 + n-2 + ... + 1) = n(n+1)/2 = (n2+n)/2 --> n2 ---> O(n2) */ func selectionSort(_ arr: Array) -> Array { var newArr = Array() var tmp = arr var smallestIndex: Intwhile tmp.count > 0 { // 循环n次 smallestIndex = findSmallest(tmp) // n, n-1, n-2, n-3, ... ,1 newArr.append(tmp[smallestIndex]) tmp.remove(at: smallestIndex) }return newArr }// MARK: Test let arr = [5, 3, 6, 2, 1, 10, 50, 8] let result = selectionSort(arr) print(result)