冒泡排序
冒泡排序是一种时间复杂度为 O(N^2) 的慢速排序。每一次遍历数组，比较相邻两元素的大小，将较大者换到右边。也就是说，每一次遍历都会选出未排序的元素中的最大值。
func bubbleSort<T: Comparable>(array: inout[T]) -> [T]{
for i in 0..<array.count - 1 {
for j in 0..<array.count - 1 - i {
if array[j] > array[j + 1] {
let temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
return array
}
插入排序
插入排序是一种 O(N^2) 的排序方法，思路是将未排序的元素插入到已排序的数组当中合适的位置。
func insertionSort<T: Comparable>(array: inout[T]) -> [T]{
for i in 1..<array.count {
// 当前待插入的元素
let insertion = array[i]
// 从后往前遍历之前的所有元素
for j in (0..<i).reversed() {
// 如果 insertion 小于 array[j]，那么 array[j] 向右移动一位
if insertion < array[j] {
// move array[j] to right by 1
array[j + 1] = array[j]
array[j] = insertion
// 如果不小于，那么位置正确，插入并且跳出循环
} else {
array[j + 1] = insertion
break
}
}
}
return array
}
选择排序
选择排序的性能不如插入排序，时间复杂度依然是 O(N^2) 。思路是每一次遍历数组，都选出数组的最小值。与冒泡排序不同的是，选择排序通过遍历所有未排序元素来选出最小值；而冒泡排序是通过两两比较并且交换来滤出最小值/最大值。
func selectionSort<T: Comparable>(array: inout[T]) -> [T]{
guard array.count > 1 else {return array}
for i in 0..<array.count {
// 选出最小值
var minIndex = i
for j in i + 1 ..< array.count {
if array[j] < array[minIndex] {
minIndex = j
}
}
// 交换两个值
let temp = array[minIndex]
array[minIndex] = array[i]
array[i] = temp
// 也可以用 swift 元组来交换
// (array[minIndex], array[i]) = (array[i], array[minIndex])
}
return array
}
快速排序
快速排序是一种时间复杂度为 O(Nlog N)* 的算法，其思路是首先选定某一个位置的值作为支点，然后将数组一分为二，大于支点的元素和小于支点的元素。将这个过程递归直到不可再分为止。然后将整个递归的结果串联起来便是排好序的数组。
func quickSort<T: Comparable>(array: [T]) -> [T] {
guard array.count > 0 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 }
// 递归并且拼接，加号是 swift 当中拼接数组的方法
return quickSort(array: less) + equal + quickSort(array: greater)
}
以上代码选取支点的方式是取中间元素，根据特殊的情况选择一个合适的支点可以对性能有很大提升。
代码中使用 swift 中的 filter 闭包来实现对数组中元素的筛选，最后返回值是将三个数组拼接在一起。
下面我们使用一张图来说明整个过程：
示例
从图中可以看出，如果我们的支点选择的不够恰当，比如恰好选择的是最大值或者最小值，那么整个数将会失衡。如果大多数元素都集中在一侧的子节点的话，那么会增加无用的递归次数。
归并排序
归并排序的思路是将原数组进行二分分割，直到不可分。然后再调用一个合并函数将这些分割后的数组进行有序的合并。时间复杂度为 O(NlogN)*。
归并排序
func mergeSort<T: Comparable>(array: [T]) -> [T] {
guard array.count > 1 else { return array }
// 一分为二
let mid = array.count / 2
let leftArray = mergeSort(array: Array(array[0..<mid]))
let rightArray = mergeSort(array: Array(array[mid..<array.count]))
return merge(leftPile: leftArray, rightPile: rightArray)
}
func merge<T: Comparable>(leftPile: [T], rightPile: [T]) -> [T] {
// 两个索引，用于记录两边数组的位置
var leftIndex = 0
var rightIndex = 0
// 归并的结果
var result = [T]()
// 此循环将两边的数组的元素有序的往 result 数组中添加元素
while leftIndex < leftPile.count && rightIndex < rightPile.count {
// 左 < 右
if leftPile[leftIndex] < rightPile[rightIndex] {
result.append(leftPile[leftIndex])
leftIndex += 1
// 左 > 右
} else if leftPile[leftIndex] > rightPile[rightIndex] {
result.append(rightPile[rightIndex])
rightIndex += 1
// 左 = 右
} else {
// 左右都放
result.append(leftPile[leftIndex])
leftIndex += 1
result.append(rightPile[rightIndex])
rightIndex += 1
}
}
// 处理左侧剩余的元素，比如右侧已经空了，但左侧还有很多元素
while leftIndex < leftPile.count {
result.append(leftPile[leftIndex])
leftIndex += 1
}
// 处理右侧剩余的元素
while rightIndex < rightPile.count {
result.append(rightPile[rightIndex])
rightIndex += 1
}
return result
}
计数排序
计数排序的思路是创建另一个数组来记录原数组中数据出现的位置，然后再按照顺序还原出有序数组。时间复杂度为O(n + k)，k 代表创建一个 counting 数组需要用的时间。计数排序是一种典型的牺牲空间复杂度来换取时间复杂度的算法，其空间复杂度为O(2n)。
let array = [8, 4, 6, 9, 1, 3, 5, 8, 2, 10]
func countingSort(array: [Int]) -> [Int]{
// 第一步：创建一个用于计数的数组来保存原数组数据的出现次数。
let max = array.max() ?? 0
var countArray = [Int](repeating: 0, count: max + 1)
for each in array {
countArray[each] += 1
}
print(countArray) // [0, 1, 1, 1, 1, 1, 1, 0, 2, 1, 1]
// Step 2: Sum up.
// 第二步：横着求和，每一个元素等于之前的元素的和。
for index in 1 ..< countArray.count {
countArray[index] += countArray[index - 1]
}
print(countArray) // [0, 1, 2, 3, 4, 5, 6, 6, 8, 9, 10]
// Step 3: Place.
// 第三步：放置。
var sortedArray = [Int](repeating: 0, count: array.count)
for each in array {
countArray[each] -= 1
sortedArray[countArray[each]] = each
}
return sortedArray
}
print(countingSort(array: array)) // [1, 2, 3, 4, 5, 6, 8, 8, 9, 10]
附：排序算法度量总结图
排序算法度量
