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

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)