排序算法笔记

从接触算法就开始说的排序，这里总结一下。

Bubble Sort

冒泡排序是最基础的排序了，主要有三个基本步骤：

• 每次比较两个值
• 如果左边的值更大，则交换两个值的位置，以将更大的值排到右边
• 向右移动一个位置

func bubbleSort(data: inout [Int]) {
    for outerIdx in stride(from: data.count - 1, to: 0, by: -1) {
        for innerIdx in 0 ..< outerIdx {
            if data[innerIdx] > data[innerIdx + 1] {
                (data[innerIdx], data[innerIdx + 1]) = (data[innerIdx + 1], data[innerIdx])
            }
        }
    }
}

对一个长度为 n 的数组，worst-case 下需要执行交换的次数为 n(n - 1)/2，需要比较的次数也为 n(n - 1)/2。冒泡排序的时间复杂度为 O(n^2)。冒泡排序是稳定的。

Selection Sort

选择排序比冒泡排序快一点，主要有两个基本步骤：

• 选择最小的值
• 把它和最左边的元素交换

func selectionSort(data: inout [Int]) {
    for outerIdx in 0 ..< data.count - 1 {
        // set initial min value's index
        var minimum = outerIdx
        // select a new minimum value's index
        for innerIdx in outerIdx + 1 ..< data.count {
            if data[innerIdx] < data[minimum] {
                // if new min, reset index
                minimum = innerIdx
            }
        }
        if outerIdx != minimum {
            (data[outerIdx], data[minimum]) = (data[minimum], data[outerIdx])
        }
    }
}

对一个长度为 n 的数组，worst-case 下需要执行交换的次数为 n - 1，需要比较的次数为 n(n - 1)/2。选择排序的时间复杂度为 O(n^2)。选择排序是不稳定的。

Insertion Sort

插入排序比前两个都快，插入排序的关键在于有一条想象的分界线。主要思路是：

• 分界线左边的元素都排好序了
• 分界线右边的第一个元素需要被插到左边的一个恰当位置中
  • 首先，把右边第一个元素的值存到一个临时变量中
  • 把左边的元素全部向右移一位，从而可以有一个位置来放要插入的值
  • 找到位置后，插入临时变量中的值

func insertionSort(data: inout [Int]) {
    guard !data.isEmpty else {
        return
    }
    for outerIdx in 1 ..< data.count {
        let tmp = data[outerIdx]
        var innerIdx = outerIdx
        // go backward in the left side of the line
        // shift the values
        while innerIdx > 0, data[innerIdx - 1] >= tmp {
            data[innerIdx] = data[innerIdx - 1]
            innerIdx -= 1
        }
        if outerIdx != innerIdx {
            data[innerIdx] = tmp
        }
    }
}

对一个长度为 n 的数组，worst-case 下需要比较的次数为 n(n - 1) / 2，如果是随机分布的数组则表现会更好。插入排序最坏的情况下复杂度为 O(n^2)，最好的情况下为 O(n)（输入数组已经排好序的情况下）。插入排序也是稳定的。

Merge Sort

归并排序的思路是 divide and conquer algorithms 的一个生动的例子。归并排序的思路为：

• 用归并排序排好前一半
• 用归并排序排好后一半
• 归并排好序的两半

func mergeSort(data: [Int]) -> [Int] {

    // helper that merges two parts
    func merge(_ a: [Int], _ b: [Int]) -> [Int] {
        var merged: [Int] = []
        var aIdx = 0
        var bIdx = 0
        while aIdx < a.count && bIdx < b.count {
            if a[aIdx] < b[bIdx] {
                merged.append(a[aIdx])
                aIdx += 1
            } else {
                merged.append(b[bIdx])
                bIdx += 1
            }
        }
        if aIdx < a.count {
            merged += a[aIdx ..< a.count]
        }
        if bIdx < b.count {
            merged += b[bIdx ..< b.count]
        }
        return merged
    }

    if data.count <= 1 {
        return data
    }

    let mid = data.count / 2
    // create left array
    let left = Array(data[0 ..< mid])
    // create right array
    let right = Array(data[mid ..< data.count])
    // call itself with left half
    let sortedLeft = mergeSort(data: left)
    // call itself with right half
    let sortedRight = mergeSort(data: right)
    // merge
    return merge(sortedLeft, sortedRight)
}

归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)，是稳定的。

Quick Sort

快速排序的思路主要有三步：

• 把数组分成左半部分（较小值）和右半部分（较大值）
• 用快速排序排序左半部分
• 用快速排序排序右半部分

中心思想就是 partitioning，需要选择一个 pivot value 来决定每个值属于哪个部分。

func quickSort(data: inout [Int]) {

    func partition(arr: inout [Int], left: Int, right: Int, pivot: Int) -> Int {
        var leftPtr = left
        var rightPtr = right
        while true {
            while arr[leftPtr] < pivot {
                leftPtr += 1
            }
            while rightPtr > 0, arr[rightPtr] > pivot {
                rightPtr -= 1
            }
            if leftPtr >= rightPtr {
                break
            } else {
                (arr[leftPtr], arr[rightPtr]) = (arr[rightPtr], arr[leftPtr])
            }
        }
        return leftPtr
    }

    func quickSortHelper(data: inout [Int], left: Int, right: Int) {
        // base case
        if left >= right {
            return
        }
        // last value is pivot
        let pivot = data[right]
        let partition = partition(arr: &data, left: left, right: right, pivot: pivot)
        quickSortHelper(data: &data, left: left, right: partition - 1)
        quickSortHelper(data: &data, left: partition + 1, right: right)
    }

    quickSortHelper(data: &data, left: 0, right: data.count - 1)

}

这是一种原位置排序的实现。利用 Swift 语言的特性，我们可以给出一种远远更为简洁的实现：

func quickSortV2(data: [Int]) -> [Int] {
    if data.count <= 1 {
        return data
    }
    var unsorted = data
    // initialize arrays
    var left: [Int] = []
    var right: [Int] = []
    // pick pivot value
    let pivot = unsorted.popLast()!
    for x in unsorted {
        if x < pivot {
            left.append(x)
        } else {
            right.append(x)
        }
    }
    // call itself
    return quickSortV2(data: left) + [pivot] + quickSortV2(data: right)
}

快速排序的时间复杂度为 O(n log n)。根据下面和大佬同学 @LisaDing 的讨论，原地快速排序的空间复杂度一般可以为 O(log n)（即递归深度，因为每次保存常数信息，栈帧里总共就会有 log n，具体讨论可见 这里），worst case 为 O(n)。第二种非原地的快速排序空间复杂度为 O(n log n)（具体见 stackoverflow 的这个帖子）。因此，快速排序的空间复杂度和具体实现关系很大。快速排序是不稳定的。