插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
时间复杂度 最好 O(N) 平均、最坏 O(n^2)
空间复杂度 O(1)
func insertionSort(_ array: inout [Int]) {
let n = array.count
for i in 1..<n {
let key = array[i]
var j = i - 1
// 将 array[i] 插入到已排序的子数组 array[0...i-1] 中
while j >= 0 && array[j] > key {
array[j + 1] = array[j]
j -= 1
}
array[j + 1] = key
}
}
// 测试插入排序
var numbers = [5, 2, 9, 1, 5, 6]
insertionSort(&numbers)
print(numbers)
这段代码定义了一个名为 insertionSort 的函数，它接受一个整型数组作为输入，并对其进行原地排序。insertionSort 函数的核心是两个嵌套的循环：外部循环从数组的第二个元素开始遍历（因为第一个元素默认是有序的），内部循环用于将当前元素插入到已排序部分的正确位置。
选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
时间复杂度 O(n^2)
空间复杂度 O(1)
func selectionSort(_ array: inout [Int]) {
let n = array.count
for i in 0..<n {
// 假设最小数为当前元素
var minIndex = i
// 找到当前数往后剩余数组中最小的元素
for j in i+1..<n {
if array[j] < array[minIndex] {
minIndex = j
}
}
// 如果最小数 index 发生了变化，则交换当前元素和最小元素
if minIndex != i {
array.swapAt(i, minIndex)
}
}
}
// 测试选择排序
var numbers = [5, 2, 9, 1, 5, 6]
selectionSort(&numbers)
print(numbers)
这段代码定义了一个名为 selectionSort 的函数，它接受一个整型数组作为输入，并对其进行原地排序。selectionSort 函数的核心是两个嵌套的循环：外部循环从数组的第一个元素开始遍历，内部循环用于找到剩余部分中的最小元素并与当前元素交换。通过这种方式，数组逐渐变得有序。
冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地遍历要排序的元素，比较每对相邻的元素，并在它们的顺序不正确时交换它们的位置，直到整个列表有序。
时间复杂度 最坏 O(n^2) 最好 O(n)
空间复杂度 O(1)
func bubbleSort(array: inout [Int]) {
let n = array.count
for i in 0..<n {
for j in 1..<n-i {
if array[j-1] > array[j] {
array.swapAt(j-1, j)
}
}
}
}
// 测试冒泡排序
var numbers = [5, 2, 9, 1, 5, 6]
bubbleSort(&numbers)
print(numbers)
快速排序
采用分治法（Divide and Conquer）来将一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。
时间复杂度 最好、平均 O(nlogn) 最坏 O(n^2)
空间复杂度 最坏 O(n) 平均 O(log n)
func quickSort<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 equal = array.filter { $0 == pivot }
let greater = array.filter { $0 > pivot }
// 递归排序每个部分，并合并结果
return quickSort(less) + equal + quickSort(greater)
}
// 测试快速排序
var numbers = [5, 2, 9, 1, 5, 6]
print(quickSort(numbers))
这段代码定义了两个函数：quickSort 和 partition。quickSort 函数使用递归将数组分成两部分，并分别对这两部分进行排序。partition 函数选择一个枢轴，并根据枢轴将数组分成两部分，使得枢轴左边的元素都小于或等于枢轴，右边的元素都大于枢轴。通过不断递归地分割和排序，最终得到一个有序的数组。
归并排序
采用分治法（Divide and Conquer）将一个序列分成两个子序列，分别进行排序，然后将两个已排序的子序列合并成一个有序序列。
时间复杂度 O(nlogn)
空间复杂度 O(n)
import Foundation
func mergeSort(array: [Int]) -> [Int] {
guard array.count > 1 else {
return array
}
let leftArray = Array(array[0..<array.count/2])
let rightArray = Array(array[array.count/2..<array.count])
return merge(left: mergeSort(array: leftArray), right: mergeSort(array: rightArray))
}
func merge(left: [Int], right: [Int]) -> [Int] {
var mergedArray: [Int] = []
var left = left
var right = right
while left.count > 0 && right.count > 0 {
if left.first! < right.first! {
mergedArray.append(left.removeFirst())
}
else {
mergedArray.append(right.removeFirst())
}
}
return mergedArray + left + right
}
var numbers: [Int] = [4,3,2,5,1]
print(numbers)
print(mergeSort(array: numbers))
这段代码定义了两个函数：mergeSort 和 merge。mergeSort 函数使用递归将数组分成两半，并对每一半进行排序。merge 函数将两个有序的子数组合并成一个有序的数组。通过递归地将数组不断分割，直到每个子数组的长度为 1，然后再通过合并操作将它们逐步合并成一个有序的数组。
堆排序
堆排序（Heapsort）是一种基于堆这种数据结构的比较排序算法。堆排序将数组视为二叉树结构，通过调整二叉树来进行排序。
时间复杂度 O(nlogn)
空间复杂度 O(1)
func heapSort(_ array: inout [Int]) {
let n = array.count
// 构建最大堆
for i in stride(from: n / 2 - 1, through: 0, by: -1) {
heapify(&array, n, i)
}
// 一个一个取出元素进行调整
for i in stride(from: n - 1, through: 1, by: -1) {
array.swapAt(0, i)
heapify(&array, i, 0)
}
}
func heapify(_ array: inout [Int], _ n: Int, _ i: Int) {
var largest = i
let left = 2 * i + 1
let right = 2 * i + 2
if left < n && array[left] > array[largest] {
largest = left
}
if right < n && array[right] > array[largest] {
largest = right
}
if largest != i {
array.swapAt(i, largest)
heapify(&array, n, largest)
}
}
// 测试堆排序
var numbers = [5, 2, 9, 1, 5, 6]
heapSort(&numbers)
print(numbers)
这段代码定义了两个函数：heapSort 和 heapify。heapSort 函数首先构建一个最大堆，然后将堆顶元素与当前堆的最后一个元素交换，再调整堆，以此类推，直到整个数组有序。heapify 函数用于维护堆的性质，使其满足最大堆的条件。通过这种方式，数组逐渐变得有序。
