学习排序算法

在年后拜读几位掘金大咖的年度总结的时候，他们不约而同的都提到了数据结构的重要性，在粗略的看了一些后，我选择跟着k_night的脚步去学习那些曾经在大学没有好好学习的东西（虽然目前的工作中还未曾用到）。
K_night的本篇文章简述了算法的两项衡量指标，时间复杂度和空间复杂度。常见的时间复杂度有：常数阶O(1)，对数阶O(log n)，线性阶 O(n)，线性对数阶O(nlog n)，平方阶O(n^{2}) ，立方阶O(n^{3}) ，!k次方阶O(n^{k})，指数阶 O(2^{n}))。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。在正常工作中，不能够出现时间复杂度在立方阶及其以上的算法，尽量不要出现时间复杂度为平方阶的算法；。并简单的介绍了递归算法及其注意的问题。
主要的篇幅用来介绍几种排序算法，包括冒泡排序，选择排序，插入排序，归并排序和快速排序。
冒泡排序，选择排序和插入排序三者都是通过双重的for循环来实现的，所以三者的平均时间复杂度都为O(n^2)，但是三者的实现思路却是不同的。
交换排序作为最容易理解的排序方式，整体思路是：外层循环控制边界，内层循环寻找边界内的最小值并放到最前端，即范围的后端不变，前端在向后移动。第一次循环寻找0 ~ n的最小值并置于第一个位置（array[0]），第二次循环寻找1 ~ n的最小值并置于第二个位置（array[1]），以此类推。

//交换排序
/*
 基本思想：两层循环，第一次遍历寻找数组中最小的数，将其放数组首位，第二次寻找第二小的数，放在第二位，依次重复。
 外层遍历数组从0到末尾的元素，索引为i.
 内层遍历数组从i+1至数组末尾的元素，索引为j。
 当i上的元素比j上的元素大的时候，交换i和j的元素，目的是保持index为i的元素是最小的。
 */
func switchSort(_ array: inout [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    for i in 0 ..< array.count {
        
        for j in i + 1 ..< array.count {
            
            if array[i] > array[j] {
                array.swapAt(i, j)
            }
        }
    }
    
    return array
}

冒泡排序和交换排序很像，不同的地方在于它每次比较的是相邻的两个数字并且按大小交换顺序，每次会寻找到范围内的最大值并将它放到最后一位，它的内层的范围是不断缩小的，而且范围的前端不变，后端在向前移。

//冒泡排序
/*
 基本思想：每次相邻的两个数字进行比较，按大小交换顺序。
 循环的边界条件：冒泡排序的外层是[0,array.count-1);内层是[0,array.count-1-i)。可以看到内层的范围是不断缩小的，而且范围的前端不变，后端在向前移。
 交换排序比较的是内外层索引的元素（array[i] 和 array[j]）,但是冒泡排序比较的是两个相邻的内层索引的元素：array[j]和array[j+1]。
 */
func bubbltSort(_ array: inout [Int]) -> [Int] {
    guard array.count > 1 else {
        return array
    }
    for i in 0..<array.count - 1{
        
        for j in 0..<array.count - i - 1 {
            if array[j] > array[j+1]{
                array.swapAt(j, j+1)
            }
        }
    }

    return array
}

//冒泡排序(优化版)
/*
 在排序过程中，数组已经是有序的了，每次都比较会做无用功，降低排序效率。
 设定一个标志，初始值为false，发生交换会使其置为true，如果内层循环没有发生树值交换（flag为false），则数组为有序数组，跳出循环。
 */
func bubbltSortAdvanced(_ array: inout [Int]) -> [Int] {
    guard array.count > 1 else {
        return array
    }
    for i in 0..<array.count - 1{
        
        var flagSort = false
        
        for j in 0..<array.count - i - 1 {
            if array[j] > array[j+1]{
                array.swapAt(j, j+1)
                flagSort = true
            }
        }
        
        if flagSort == false {
            break
        }
    }
    
    return array
}

选择排序的基本思想也是外层循环控制边界，内层循环寻找边界内的最小值并放到最前端，即范围的后端不变，前端在向后移动。与冒泡排序的不同在于，选择排序不会每次比较后都将数组内的两个数字进行交换，而是将其下标进行保存，在内层循环完成后，再将最小值与首位元素进行交换。

//选择排序
/*
 基本思想：两层循环，内层遍历从数组中找到最小的值，与数组第一位进行交换；外层遍历控制遍历的范围，后端不变，依次缩小。
 实现思路：
 在外层循环的开始，将i作为最小值的index（很可能不是该数组的最小值）。
 在内层循环里面找到当前内层循环范围内的最小值，并与已经记录的最小值作比较：如果与当前记录的最小值index不同，则替换；如果与当前记录的最小值index相同，则不替换。
 */
func selectionSort(_ array: inout [Int]) -> [Int] {
    guard array.count > 1 else {
        return array
    }
    for i in 0..<array.count - 1 {
        
        var minIndex = i
        
        for j in i + 1 ..< array.count {
            if array[j] < array[minIndex] {
                minIndex = j
            }
        }
        
        if i != minIndex {
            array.swapAt(i, minIndex)
        }
    }
    return array
}

插入排序的基本思想为：从数组中拿出一个元素（通常就是第一个元素）以后，再从数组中按顺序拿出其他元素。如果拿出来的这个元素比这个元素小，就放在这个元素左侧；反之，则放在右侧。插入排序因为本身是有顺序的，所以一旦出现当前index为j的元素只要比前面的元素大，那么该内层循环就可以提前终止了。

//插入排序
/*
 基本思想：从数组中拿出一个元素（通常就是第一个元素）以后，再从数组中按顺序拿出其他元素。如果拿出来的这个元素比这个元素小，就放在这个元素左侧；反之，则放在右侧。
 实现思路：
    外层循环的边界是[1,array.count)，index为i。
    内层循环开始的时候初始index j = i，然后使用一个while循环，循环条件是j>0 && array[j] < array[j - 1],循环内侧是交换j-1和j的元素，并使得j-1。可以简单理解为如果当前的元素比前一个元素小，则调换位置；反之进行下一个外层循环。
 */
func insertionSort(_ array: inout [Int]) -> [Int] {
    guard array.count > 1 else {
        return array
    }
    
    for i in 0..<array.count{
        var j = i
        while j > 0 && array[j] < array[j-1] {
            array.swapAt(j, j-1)
            j -= 1
        }
    }
    
    return array
}

归并排序和快速排序都是用了递归的思想，将一个需要排序的数组不停地分割为更小的数组，排序之后再组合起来。
归并排序的合并方法为新建一个空数组用于存放合并后的有序数组。两个传入的数组从index 0 开始两两比较，较小的元素放在新建的空数组中，index + 1; 较大的元素不做操作，index 不变，然后继续两两比较。直到index移到末尾为止。需要注意在两个数组长度不一致的情况下需要将数组里剩余的元素放在新建的数组中。

//归并排序
/*
 基本思想：归并排序采用分治思想来处理。整个方法分为两部分，一分一合。归并的操作就是把两个数组（在这里这两个数组的元素个数通常是一致的）合并成一个完全有序数组。
 实现思路：
    新建一个空数组，该数组用于存放合并后的有序数组。
    两个传入的数组从index 0 开始两两比较，较小的元素放在新建的空数组中，index + 1; 较大的元素不作操作，index 不变，然后继续两两比较。直到index移到末尾为止。
    个别情况当两个数组长度不一致的情况下需要将数组里剩余的元素放在新建的数组中。
 */
//合并
func merge(leftPile: [Int], rightPile: [Int]) -> [Int]{
    var leftIndex = 0
    var rightIndex = 0
    var sortedPile = [Int]()
    
    while leftIndex < leftPile.count && rightIndex < rightPile.count {
        
        if leftPile[leftIndex] < rightPile[rightIndex] {
            sortedPile.append(leftPile[leftIndex])
            leftIndex += 1
        }else if leftPile[leftIndex] > rightPile[rightIndex]{
            sortedPile.append(rightPile[rightIndex])
            rightIndex += 1
        }else{
            sortedPile.append(leftPile[leftIndex])
            leftIndex += 1
            sortedPile.append(rightPile[rightIndex])
            rightIndex += 1
        }
    }
    
    //检查是否有剩余元素，如果有则添加到新建数组里面
    while leftIndex < leftPile.count {
        sortedPile.append(leftPile[leftIndex])
        leftIndex += 1
    }
    
    while rightIndex < rightPile.count {
        sortedPile.append(rightPile[rightIndex])
        rightIndex += 1
    }
    
    return sortedPile
}
//拆分
func mergeSort(_ array: [Int]) -> [Int]{
    guard array.count > 1 else {
        return array
    }
    
    let middleIndex = array.count / 2
    let leftArray = mergeSort(Array(array[0..<middleIndex]))
    let rightArray = mergeSort(Array(array[middleIndex..<array.count]))
    
    return merge(leftPile: leftArray, rightPile: rightArray)
}

快速排序的基本思路是从数列中挑出一个元素（挑选的算法可以是随机，也可以作其他的优化），称为"基准"（pivot）。重新对数组进行排序：所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面，相同的放两边。

//快速排序
/*
 基本思想：通过一趟排序将带排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
 实现思路：
 从数列中挑出一个元素（挑选的算法可以是随机，也可以作其他的优化），称为"基准"（pivot）。
 重新对数组进行排序：所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面，相同的放两边。
 递归地进行分区操作，继续把小于基准值元素的子数列和大于基准值元素的子数列排序。
 */

func quickSort0<T: Comparable>(_ array: [T]) -> [T] {
    
    guard array.count > 1 else { return array }
    
    let pivot = array[array.count/2]
    let less = array.filter { $0 < pivot }
    let greater = array.filter { $0 > pivot }
    
    return quickSort0(less) + quickSort0(greater)
}


//将快速排序中新增一个equal，可以优化排序方式，三路快速排序。
func quicksortTW(_ array: [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    let pivot = array[array.count/2]
    let less = array.filter { $0 < pivot }
    let equal = array.filter { $0 == pivot }
    let greater = array.filter { $0 > pivot }
    
    return quicksortTW(less) + equal + quicksortTW(greater)
}

原文链接：https://juejin.im/post/5a7b4101f265da4e7071b097#heading-22