2 選擇排序 O(n2)

2.2 數(shù)組和鏈表

// MARK: - 2.2 數(shù)組和鏈表
// FIXME: (1) 鏈表

// FIXME: 1) 鏈表的元素可存儲在內(nèi)存的任何地方.
// FIXME: 2) 鏈表的每個元素都存儲了下一個元素的地址, 從而使一系列隨機的內(nèi)存地址串聯(lián)在一起.
// FIXME: 3) 鏈表優(yōu)勢: 插入元素快, 大O表示法: O(1); 劣勢: 讀取速度慢, 因為必須要從第一個元素獲取下一個元素的地址, 以此類推. so 大O表示法: O(n)

// FIXME: (2) 數(shù)組

// FIXME: 1) 數(shù)組的元素存儲在一塊連續(xù)的內(nèi)存上.
// FIXME: 2) 數(shù)組優(yōu)勢: 讀取快, 大O表示法: O(1); 劣勢: 插入慢, 因為插入一個元素, 那么其后的元素地址都必須向后移動一個元素的位置 大O表示法: O(n)

2.3 總結(jié)<函數(shù)表達(dá)式>

// MARK: - 總結(jié) 函數(shù)表達(dá)式

/**
 * 獲取最小元素的索引
 * 時間復(fù)雜度: 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
}

/**
 * 選擇排序 從小到大
 *  時間復(fù)雜度: (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 { // 循環(huán)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)