Swift - 基础排序算法

前言

排序算法可谓数据结构中的基础知识。在实际编码工作中，直接手写排序算法的情况越来越少，更多的是应用其思想来指引我们更好的写出高效率的代码。温故而知新，写这篇文章目的就是笔者记录复习的一个过程。

常见几种排序

名称	时间复杂度	空间复杂度	是否稳定
冒泡排序	O(n^2)	O(1)	是
插入排序	O(n^2)	O(1)	是
选择排序	O(n^2)	O(1)	否
堆排序	O(nlogn)	O(1)	否
归并排序	O(nlogn)	O(1)	是
快速排序	O(nlogn)	O(1)	否
桶排序	O(n)	O(k)	是

冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

• 算法思路：
  1 ，比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2 ，对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3， 针对所有的元素重复以上的步骤，除了最后一个。
  4，持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

• 实现

func bubleSort<T:Comparable>(_ array:[T] , _ compare:(T,T) -> Bool) -> [T] {
    var tempArray = array
    for i in 1..<tempArray.count {
        for j in 0..<tempArray.count - I {
            if compare(tempArray[j],tempArray[j + 1]) {
                tempArray.swapAt(j, j+1)
            }
        }
    }
    return tempArray
}

插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 算法思路
  1，从第一个元素开始，该元素可以认为已经被排序
  2，取出下一个元素，在已经排序的元素序列中从后向前扫描
  3，如果该元素（已排序）大于新元素，将该元素移到下一位置
  4，重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5，将新元素插入到该位置后
  6，重复步骤2~5

• 实现

func insertSort<T : Comparable> (_ array : [T], _ compare:(T,T) -> Bool ) -> [T]{
    var tempArray = array
    for var i in 1..<tempArray.count {
        while i > 0 && compare(tempArray[i], tempArray[i - 1]) {
            tempArray.swapAt(i, i - 1)
            i -= 1
        }
    }
    return tempArray
}

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对N个元素的表进行排序总共进行至多N-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

• 思路
  1，循环比较当次数组中最大或最小的数值，并标记。
  2，如果发现最大或最小数值，进行交换位置。
• 实现

func selectionSort<T : Comparable> (_ array:[T] , _ compare:(T,T) -> Bool) -> [T]{
    var tempArray = array
    for i in 0..<tempArray.count-1 {
        var selectedItemIndex = I
        for j in i+1..<tempArray.count {
            if compare(tempArray[selectedItemIndex],tempArray[j]) {
                selectedItemIndex = j
            }
        }
        if selectedItemIndex != I {
            tempArray.swapAt(miniItemIndex, i)
        }  
    }
    return tempArray
}

堆排序

是指利用堆这种数据结构所设计的一种排序算法堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

• 思路
  1，最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
  2，创建最大堆（Build_Max_Heap）：将堆所有数据重新排序。
  3，堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

• 实现

/**
 * 最大堆调整
 */
func heapify(_ array:inout [Int], _ i:Int,_ size:Int) {
    let left = 2 * I
    let right = left + 1
    var largest = I

    if left < size && array[left] > array[i] {
        largest = left
    }
    if right < size && array[right] > array[largest] {
        largest = right
    }
    if largest != I {
        array.swapAt(i, largest)
        heapify(&array,largest,size)
    }
}
/**
 * 构建最大堆
 */
func buildHeap(_ array:inout [Int]) {
    var i = array.count
    while i > 0 {
        heapify(&array, i - 1, array.count)
        I-=1
    }
    print("build heap:\(array)")
}
/**
 *堆排序
 */
func heapSort(_ array: inout [Int]) {
    buildHeap(&array)
    var size = array.count
    for i in stride(from: array.count-1, through: 1, by: -1){
        array.swapAt(i, 0)
        size-=1
        heapify(&array, 0, size)
    }
    print("sorted heap:\(array)")
}

归并排序

归并排序是创建在归并操作上的一种有效的排序算法，1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

• 思路

1. 将序列每相邻两个数字进行归并操作ceil(n/2)个序列，排序后每个序列包含两/一个元素
2. 若此时序列数不是1个则将上述序列再次归并，形成 ceil()个序列，每个序列包含四/三个元素
3. 重复步骤2，直到所有元素排序完毕，即序列数为1

• 实现

func mergeSort(array: [Int]) -> [Int] {
  var helper = Array(count: array.count, repeatedValue: 0)
  var array = array
  mergeSort(&array, &helper, 0, array.count - 1)
  return array
}

func mergeSort(inout array: [Int], inout _ helper: [Int], _ low: Int, _ high: Int) {
  guard low < high else {
    return
  }
  
  let middle = (high - low) / 2 + low
  mergeSort(&array, &helper, low, middle)
  mergeSort(&array, &helper, middle + 1, high)
  merge(&array, &helper, low, middle, high)
}

func merge(inout array: [Int], inout _ helper: [Int], _ low: Int, _ middle: Int, _ high: Int) {
  // copy both halves into a helper array
  for i in low ... high {
    helper[i] = array[i]
  }
  
  var helperLeft = low
  var helperRight = middle + 1
  var current = low
  
  // iterate through helper array and copy the right one to original array
  while helperLeft <= middle && helperRight <= high {
    if helper[helperLeft] <= helper[helperRight] {
      array[current] = helper[helperLeft]
      helperLeft += 1
    } else {
      array[current] = helper[helperRight]
      helperRight += 1
    }
    current += 1
  }
  
  // handle the rest
  guard middle - helperLeft >= 0 else {
    return
  }
  for i in 0 ... middle - helperLeft {
    array[current + i] = helper[helperLeft + I]
  }
}

快速排序

快速排序，又称划分交换排序，一种排序算法,最早由东尼·霍尔提出。

• 思路

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

• 实现

func breakCollection (array : inout Array<Int> , left : Int ,right : Int) -> Int{
    var left = left
    var right = right
    let temp = array[left]
    while left < right {
        while left < right && array[right] >= temp {
            right -= 1
        }
        array[left] = array[right]
        while left < right && array[left] <= temp {
            left += 1
        }
        array[right] = array[left]
    }
    array[left] = temp
    print(array)
    return left
}
func quickSort(array : inout Array<Int> , start:Int ,end:Int) ->Array<Int>{
    if start < end {
        let mid = breakCollection(array: &array, left: start, right:end)
        quickSort(array: &array, start: 0, end: mid - 1)
        quickSort(array: &array, start: mid + 1, end: end)
    }
    return array
}

结语

算法排序的精妙之处在于前人总结的数据处理理论，合理的利用好各个算法能够提高我们日常编码的效率。理解学会算法，避免死记硬背，学会运用，而不是照搬代码。共勉！

Refrence
https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
http://www.jianshu.com/p/70e08f1a95c6