跳到主要内容

排序算法笔记

· 阅读需 7 分钟

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

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 的这个帖子)。因此,快速排序的空间复杂度和具体实现关系很大。快速排序是不稳定的。