十大经典排序算法
alc554.com温馨提示：这篇文章已超过251天没有更新，请注意相关的内容是否还可用！
冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法,它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。
func bubbleSort(_ arr: inout [Int]) { var n = arr.count for i in 0..<n { for j in 0..<n-i-1 { if arr[j] > arr[j+1] { arr.swapAt(j, j+1) } } }}选择排序（Selection Sort）
选择排序(Selection-sort)是一种简单直观的排序算法，它首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。
func selectionSort(_ arr: inout [Int]) { var n = arr.count for i in 0..<n-1 { var minIndex = i for j in i+1..<n { if arr[j] < arr[minIndex] { minIndex = j } } if minIndex!= i { arr.swapAt(i, minIndex) } }}插入排序（Insertion Sort）
插入排序（Insertion Sort）的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个数组有序。
func insertionSort(_ arr: inout [Int]) { var n = arr.count for i in 1..<n { var key = arr[i] var j = i-1 while j >= 0 && arr[j] > key { arr[j+1] = arr[j] j = j-1 } arr[j+1] = key }}希尔排序（Shell Sort）
希尔排序(Shell Sort)是直接插入排序算法的一种更高效的改进版本，但希尔排序是非稳定排序算法。
func shellSort(_ arr: inout [Int]) { var n = arr.count gap = n/2 while gap > 0 { for i in gap..<n { var key = arr[i] var j = i-gap while j >= 0 && arr[j] > key { arr[j+gap] = arr[j] j = j-gap } arr[j+gap] = key } gap = gap/2 }}归并排序（Merge Sort）
归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
func mergeSort(_ arr: inout [Int], _ l: Int, _ r: Int) { if l < r { let m = l + (r-l)/2 mergeSort(&arr, l, m) mergeSort(&arr, m+1, r) merge(&arr, l, m, r) }}func merge(_ arr: inout [Int], _ l: Int, _ m: Int, _ r: Int) { let n1 = m - l + 1 let n2 = r - m let L = [Int](repeating: 0, count: n1) let R = [Int](repeating: 0, count: n2) for i in 0..<n1 { L[i] = arr[l+i] } for j in 0..<n2 { R[j] = arr[m+1+j] } var i = 0 var j = 0 var k = l while i < n1 && j < n2 { if L[i] <= R[j] { arr[k] = L[i] i = i + 1 } else { arr[k] = R[j] j = j + 1 } k = k + 1 } while i < n1 { arr[k] = L[i] i = i + 1 k = k + 1 } while j < n2 { arr[k] = R[j] j = j + 1 k = k + 1 }}快速排序（Quick Sort）
快速排序（Quick Sort）是对冒泡排序的一种改进，它选择基准元素，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
func quickSort(_ arr: inout [Int], _ l: Int, _ r: Int) { if l < r { let p = partition(&arr, l, r) quickSort(&arr, l, p-1) quickSort(&arr, p+1, r) }}func partition(_ arr: inout [Int], _ l: Int, _ r: Int) -> Int { let pivot = arr[r] let i = (l-1) for j in l..<r { if arr[j] <= pivot { i = i + 1 arr.swapAt(i, j) } } arr.swapAt(i+1, r) return (i+1)}堆排序（Heap Sort）
堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种，可以利用数组的特点快速定位指定索引的元素。
func heapify(_ arr: inout [Int], _ n: Int, _ i: Int) { let largest = i let left = 2 * i + 1 let right = 2 * i + 2 if left < n && arr[left] > arr[largest] { largest = left } if right < n && arr[right] > arr[largest] { largest = right } if largest!= i { arr.swapAt(i, largest) heapify(&arr, n, largest) }}func heapSort(_ arr: inout [Int]) { let n = arr.count for i in (n-1..>0).reversed() { heapify(&arr, n, i) } for i in (n-1..>0).reversed() { arr.swapAt(0, i) heapify(&arr, i, 0) }}计数排序（Counting Sort）
计数排序不是比较排序,排序的速度快于任何比较排序算法，它只能用在数据范围不大的场景中，而且一定是整数。
func countingSort(_ arr: inout [Int], _ max: Int) { let n = arr.count let count = [Int](repeating: 0, count: max+1) for i in 0..<n { count[arr[i]] = count[arr[i]] + 1 } for i in 1..<max { count[i] = count[i] + count[i-1] } let sorted = [Int](repeating: 0, count: n) for i in (n-1)..>=0 { sorted[count[arr[i]]-1] = arr[i] count[arr[i]] = count[arr[i]] - 1 } for i in 0..<n { arr[i] = sorted[i] }}桶排序（Bucket Sort）
桶排序（Bucket Sort）是计数排序的升级版，它利用函数的映射关系，高效与否的关键就在于这个映射函数的确定。
func bucketSort(_ arr: inout [Int], _ max: Int) { let n = arr.count let bucket = [Int](repeating: 0, count: max+1) for i in 0..<n { bucket[arr[i]] = bucket[arr[i]] + 1 } for i in 1..<max { bucket[i] = bucket[i] + bucket[i-1] } let sorted = [Int](repeating: 0, count: n) for i in (n-1)..>=0 { sorted[bucket[arr[i]]-1] = arr[i] bucket[arr[i]] = bucket[arr[i]] - 1 } for i in 0..<n { arr[i] = sorted[i] }}基数排序（Radix Sort）
基数排序（Radix Sort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位，有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
func radixSort(_ arr: inout [Int], _ maxDigit: Int) { for digit in 1..<maxDigit { let buckets = [[Int]](repeating: [], count: 10) for num in arr { let place = num / (10 ** digit) % 10 buckets[place].append(num) } arr = [] for bucket in buckets { arr.append(contentsOf: bucket) } }}| 排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(n^{1.5})$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 归并排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | 稳定 |
| 快速排序 | $O(nlogn)$ | $O(nlogn)$ | $O(n^2)$ | $O(logn)$ | 不稳定 |
| 堆排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(1)$ | 不稳定 |
| 计数排序 | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | 稳定 |
| 桶排序 | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | 稳定 |
| 基数排序 | $O(d(n+k))$ | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | 稳定 |
是十种常见排序算法的平均时间复杂度、最好时间复杂度、最坏时间复杂度、空间复杂度以及稳定性的总结，在实际应用中，需要根据具体情况选择合适的排序算法。
The End
发布于：2025-03-16，除非注明，否则均为原创文章，转载请注明出处。