2 选择排序 O(n2)
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>) -> 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<Int>) -> Array<Int> {
var newArr = Array<Int>()
var tmp = arr
var smallestIndex: Int
while 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)
