swift冒泡 选择 插入 排序算法

import UIKit

let a: [Int] = [4, 5, 2, 3 , 1]
/// 冒泡排序算法
/// 基本思想，每次冒泡选出和排好一个排在最后的元素。
/// 每次冒泡，选出一个排在数组最后一个元素的做法。
/// 每次都从整个数组的第一个元素开始取，然后跟后面一个元素进行比较和交换。
/// 然后再取第一个元素和后面的元素比较和交换，一直比较和交换到未排序部分的最后一个元素。
/// 共需要n-1次冒泡，就完成了排序
/// - Parameter list: 原始数组
/// - Returns: 排序后数组
func bubbleSort(list: [Int]) -> [Int] {
    var sortedList = list
    
    for i in stride(from: 1, to: list.count, by: 1) {
        for j in stride(from: 0, to: list.count - i , by: 1) {
            if sortedList[j] > sortedList[j + 1] {
                let temp = sortedList[j]
                sortedList[j ] = sortedList[j + 1]
                sortedList[j + 1] = temp
            }
        }
        print(sortedList)
    }
    return sortedList
}

//print("bubble \(bubbleSort(list: a))")

/// 选择排序算法
/// 先从整个数组中找出需要排第一个位置的元素，然后交换排在第一个位置。
/// 具体做法，取出第一个元素，暂存该元素下标位置，认为是最小值，如果后面的元素的元素的比这个更小，那么替换为这个更小的元素的下标。如果下表和第一个元素的下标不同，那么交换钙元素。
/// 然后下一轮从剩余的数组元素中，再找出排第二个位置的元素交换，依次类推。就完成了排序。
/// - Parameter list: 原始数组
/// - Returns: 排序后数组
func selectionSort(list: [Int]) -> [Int] {
    var sortedList = list
    for i in stride(from: 1, to: list.count, by: 1) {
        var key = i - 1
        for j in stride(from: i, to: list.count, by: 1) {
            if sortedList[key] > sortedList[j] {
                key = j
            }
        }
        if key != i - 1 {
            let temp = sortedList[i - 1]
            sortedList[i - 1] = sortedList[key]
            sortedList[key] = temp
        }
        print(sortedList)
    }
    return sortedList
}

//print("select \(selectionSort(list: a))")


/// 插入排序算法
/// 采用一个数据插入有序数组的思想。一个数据插入到一个有序数组，那么可以从队尾依次往前比较，
/// 如果不符合顺序那么交换位置，交换后再从倒数第二个往前继续比较和交换，以此类推。一直比较和交换到第一个。
/// 按照如上的原理，可以认为一个无序数组的第一个元素是有序的数组。
/// 那么从第二个元素开始插入到第一个元素的有序数组中，就完成了第二个元素的排序。
/// 然后再取第三个元素按照上述原理插入到前面排好序的数组中。一直插入数组的最后一个元素，就完成了排序。
/// - Parameter list: 原始数组
/// - Returns: 排序后数组
func insertionSort(list: [Int]) -> [Int] {
    print(list)
    var sortedList = list
    for i in stride(from: 1, to: list.count, by: 1) {
        for j in stride(from: i, to: 0, by: -1) {
            if sortedList[j - 1] > sortedList[j] {
                let temp = sortedList[j]
                sortedList[j] = sortedList[j - 1]
                sortedList[j - 1] = temp
            } else {
                break
            }
        }
        print(sortedList)
    }
    return sortedList
}

print("insert \(insertionSort(list: a))")