「导语 」本文主要整理了以下 10 种经典的排序算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序 以及 基数排序。文中使用 Go 语言对这些算法进行了实现，并从时空复杂度等角度对算法的各项指标进行了深入地分析。
排序算法总览 在计算机科学与数学中，排序算法 (Sorting Algorithm) 是一种能将一串数据按照特定排序方式进行排列的计算方法。有效的排序算法在一些其它常用的算法（如搜索算法）中是十分重要的，理解和掌握排序算法对于我们分析这些常用算法的内部实现会很有帮助，并且排序算法中使用到的一些技巧也可以为我们在实现其它算法时提供借鉴。
首先，让我们从整体上认识一下这些排序算法。下图归纳了各个排序算法在时间复杂度，空间复杂度，排序方式以及稳定性等各个方面的指标，这些指标是在进行排序算法选择时的重要理论依据。
其中时空复杂度分别指排序算法所消耗的时间（一般为比较的次数）和空间（一般为消耗的内存）与待排序数组长度之间的渐进性函数关系，通常用大 O 来表示。
对于大多数排序算法而言其时空复杂度是相对确定的，但也有一些排序算法，根据其实现方式的不同，其时空复杂度是在动态变化的，比如希尔排序的时间复杂度会随步长序列的选择而变化，所以在计算复杂度时，要根据代码的具体实现去动态分析。
排序方式有两种，In-Place 指原址排序，表示可以在原数组的基础上通过位置交换来达到排序的目地，而 Out-Place 则表示在排序时需要借助额外的内存来存储数组元素以达到排序的目的。
需要注意的是排序方式与空间复杂度并不直接相关，也就是说 In-Place 方式的排序算法其空间复杂度不一定为 O(1)。比如快速排序的空间复杂度为 O(log n)，但它却是一种 In-Place 方式的排序算法，这是因为它的空间复杂度主要来自于栈的内存消耗，而非来自于存储数组元素的额外内存。
稳定性是指相同 key 值的元素在排序前后其相对位置的变化情况。如果相对位置没有发生变化，则该排序是稳定排序，否则为不稳定排序。
注：图中时空复杂度里的 k 在不同的排序算法中具有不同的含义，详见具体算法的分析。
冒泡排序（Bubble Sort） 基本版原理 ：从左至右依次进行数组元素的两两比较，并将最大的元素冒泡至最右边，此为 1 轮冒泡过程。重复该过程 n 次，排序完成，其中 n 为数组长度。
优化版原理 ：在基本版里，如果数组已经排好序，时间复杂度并不是最优的 O(n)，为了降低其复杂度，优化版记录了数组在上一轮冒泡中最后一次进行交换的位置 ，由此可知此位置后的元素已经有序，则下次冒泡只需遍历到该位置即可。
冒泡排序源码 func bubbleSort (nums []int ) length := len (nums) if length > 1 { for i := length - 1 ; i > 0 ; i-- { for j := 0 ; j < i; j++ { if nums[j] > nums[j+1 ] { nums[j], nums[j+1 ] = nums[j+1 ], nums[j] } } } } } func bubbleSortOptimize (nums []int ) length := len (nums) if length > 1 { lastSwapPos := length - 1 for lastSwapPos != 0 { pos := 0 for i := 0 ; i < lastSwapPos; i++ { if nums[i] > nums[i+1 ] { nums[i], nums[i+1 ] = nums[i+1 ], nums[i] pos = i } } lastSwapPos = pos } } }
冒泡排序动态排序图
冒泡排序分析
从代码可知，冒泡排序在完全正序的情况下，时间复杂度最优为 O(n)，平均的时间复杂度为 O(n^2)。
冒泡排序没有借助额外的内存，其空间复杂度为 O(1)，排序方式为 In-Place。
相同 key 值，在排序前后其相对位置没有发生变化，所以冒泡排序是稳定排序。
选择排序 （Selection Sort） 原理 ：从左至右选出数组中的最小的元素，并与最左边未排好序的第一个元素进行交换，此为 1 次选择排序过程。重复该过程 n 次，排序完成，其中 n 为数组长度。
选择排序源码 func selectionSort (nums []int ) length := len (nums) if length > 1 { for i := 0 ; i < length; i++ { index := i for j := i + 1 ; j < length; j++ { if nums[j] < nums[index] { index = j } } nums[i], nums[index] = nums[index], nums[i] } } }
选择排序动态排序图
选择排序分析
从代码可知，选择排序在任何情况下其时间复杂度均为 O(n^2)。
选择排序没有借助额外的内存，其空间复杂度为 O(1)，排序方式为 In-Place。
相同 key 值，在排序前后其相对位置可能会发生变化，比如序列 2,2,1,4，第一个 2 会被交换到 1 的位置，所以选择排序是不稳定排序。
插入排序 （Insertion Sort） 原理 ：遍历数组中的每个元素，对于该元素，其左边的数组元素已经排好序，只需将其插入到左边序列对应的位置即可，亦即从右至左遍历该元素左边的序列，并将该元素与比之大的元素进行位置交换。重复该过程 n 次，排序完成，其中 n 为数组长度。
插入排序源码 func insertionSort (nums []int ) length := len (nums) if length > 1 { for i := 0 ; i < length; i++ { for j := i; j > 0 && nums[j] < nums[j-1 ]; j-- { nums[j], nums[j-1 ] = nums[j-1 ], nums[j] } } } }
插入排序动态排序图
插入排序分析
从代码可知，插入排序在完全正序的情况下，时间复杂度最优为 O(n)，平均的时间复杂度为 O(n^2)。
插入排序没有借助额外的内存，其空间复杂度为 O(1)，排序方式为 In-Place。
相同 key 值，在排序前后其相对位置不会发生变化，所以插入排序是稳定排序。
希尔排序（Shell Sort） 原理 ：希尔排序是插入排序的一种更为高效的改进版本，可以将它理解为一种分组插入排序法。首先根据设定的步长 step，将待排序的数组分解为若干个子序列，然后分别对每个子序列进行插入排序，此为一次希尔排序。逐渐减小步长，并重复上面的操作直至步长为 1，排序完成。其中步长的选择有多种方式，这里使用了较为常用的 Shell 步长生成方式， 即 step=n/(2^i)。
希尔排序源码 func shellSort (nums []int ) length := len (nums) if length > 1 { for step := length / 2 ; step >= 1 ; step /= 2 { for i := 0 ; i < length; i += step { for j := i; j > 0 && nums[j] < nums[j-step]; j -= step { nums[j], nums[j-step] = nums[j-step], nums[j] } } } } }
希尔排序演示图
希尔排序分析
选用 Shell 步长生成方式，希尔排序的最优时间复杂度为 O(n log n)，平均时间复杂度为 O(n log^2 n)。
希尔排序没有借助额外的内存，其空间复杂度为 O(1)，排序方式为 In-Place。
相同 key 值，在排序前后其相对位置可能会发生变化，所以希尔排序是不稳定排序。
归并排序 （Merge Sort） 递归版原理 ：将待排序的长度为 n 的数组分为两个长度为 n/2 的子序列，然后对这两个子序列分别进行归并排序，最后将排好序的两个子序列进行合并形成排好序的数组。由于子序列的合并不能在原数组直接进行，所以需要长度为 n 的辅助存储空间来完成子序列的合并操作。
迭代版 1 原理 ：基于对递归版的代码分析发现，它与二叉树的后序遍历极为相似，因此这里直接复用二叉树后序遍历的实现逻辑，只是将 TreeNode 节点转为 InterVal 区间，Interval 中包含了该区间起始位置以及中间位置的索引。在确定是否需要对某一区间进行 merge 操作时，需要先分析该区间的右半部分是否已经排好序，这里借助了 preStart 来进行辅助判断，具体实现见源码。
迭代版 2 原理 ：采用自底向上合并序列的方式来完成排序，需要借助一个队列和一个栈来实现。首先将整个待排序区间入队，接着出队入栈，并将出队的区间划分为两个子区间并入队，重复此过程直到队列为空。此时栈顶到栈底的区间顺序即为自底向上的合并顺序，逐个区间出栈，并对出栈的区间进行 merge 操作，直到栈空，排序完成。
迭代版 3 原理 ：根据归并排序的思想，先将原数组分为不可再分的子序列，然后再逐子序列进行合并，因此这里首先设定一个排序区间长度 block，目的是将原数组分为 n/block 个子序列，每个序列的长度为 block，然后对每两个相邻的长度为 block 的序列进行排序。初始时 block 大小设为 1，在随后的循环的过程中每次增加 1 倍，当 block 大于等于 n/2 时，排序完成。
归并排序源码 func mergeSort (nums []int ) length := len (nums) if length > 1 { extra := make ([]int , length) mergeSortRecursion(nums, 0 , length-1 , extra) } } func mergeSortRecursion (nums []int , start, end int , extra []int ) if start < end { middle := (start + end) / 2 mergeSortRecursion(nums, start, middle, extra) mergeSortRecursion(nums, middle+1 , end, extra) merge(nums, start, middle, end, extra) } } type interval struct { start int middle int end int } func mergeSortIterator1 (nums []int , extra []int ) length := len (nums) stack := make ([]*interval, 0 ) start, end := 0 , length-1 preStart := -1 for len (stack) != 0 || start < end { for start < end { middle := (start + end) / 2 stack = append (stack, &interval{start, middle, end}) end = middle } inter := stack[len (stack)-1 ] if inter.middle+1 >= inter.end || inter.middle+1 == preStart { stack = stack[:len (stack)-1 ] merge(nums, inter.start, inter.middle, inter.end, extra) preStart = inter.start } else { start = inter.middle + 1 end = inter.end } } } func mergeSortIterator2 (nums []int , extra []int ) length := len (nums) queue := make ([]*interval, 0 ) stack := make ([]*interval, 0 ) queue = append (queue, &interval{0 , (length - 1 ) / 2 , length - 1 }) for len (queue) != 0 { inter := queue[0 ] queue = queue[1 :] stack = append (stack, inter) if inter.start < inter.middle { queue = append (queue, &interval{inter.start, (inter.start + inter.middle) / 2 , inter.middle}) } if inter.middle+1 < inter.end { queue = append (queue, &interval{inter.middle + 1 , (inter.middle + 1 + inter.end) / 2 , inter.end}) } } for len (stack) != 0 { inter := stack[len (stack)-1 ] stack = stack[:len (stack)-1 ] merge(nums, inter.start, inter.middle, inter.end, extra) } } func mergeSortIterator3 (nums []int , extra []int ) length := len (nums) for block := 1 ; block < length; block = block * 2 { for i := 0 ; i < length; i = i + block*2 { start := i middle := i + block - 1 end := i + block*2 - 1 if middle >= length { middle = length - 1 } if end >= length { end = length - 1 } merge(nums, start, middle, end, extra) } } } func merge (nums []int , start, middle, end int , extra []int ) left, right, index := start, middle+1 , start for left <= middle && right <= end { if nums[left] <= nums[right] { extra[index] = nums[left] left++ index++ } else { extra[index] = nums[right] right++ index++ } } for left <= middle { extra[index] = nums[left] left++ index++ } for right <= end { extra[index] = nums[right] right++ index++ } for i := start; i <= end; i++ { nums[i] = extra[i] } }
归并排序动态排序图
归并排序分析
从代码可知，归并排序的时间复杂度 f(n) = 2f(n/2) + n，其中 2f(n/2) 表示将序列分成两个子序列分别进行排序的时间，n 表示子序列合并所需的时间，最后可求得 f(n) 趋近于 O(n log n)。
归并排序需要借助额外的内存 O(n) 来进行子序列合并，另外栈的深度为 O(log n)，所以其整体的空间复杂度为 O(n)，排序方式为 Out-Place。
相同 key 值，在排序前后其相对位置不会发生变化，所以归并排序是稳定排序。
快速排序 （Quick Sort） 递归版原理 ：首先，选取一个元素作为基准 pivot，然后将小于该基准的元素放在其左边，大于该基准的元素放在其右边，这一过程称为分区（partition）操作。然后递归地分别对左右两边的元素进行快速排序直到排序完成。代码中我们选取了数组中最后一个元素作为基准，当然也可以选择数组中其它位置的元素，原理上都是相通的，而且都可以通过元素交换的方式转为以最后一个元素作为基准的排序。
迭代版原理 ：与递归版的原理相似，只不过需要借助栈来对待排序区间的起始位置和结束位置进行保存。首先入栈全局数组的区间位置即 0~n-1，然后出栈区间，并对该区间的序列进行分区操作，接着将新的区间信息入栈，重复此过程，直至栈空，排序完成。
快速排序源码 func quickSort (nums []int ) length := len (nums) if length > 1 { quickSortRecursion(nums, 0 , length-1 ) } } func quickSortRecursion (nums []int , start, end int ) if start < end { index := partition(nums, start, end) quickSortRecursion(nums, start, index-1 ) quickSortRecursion(nums, index+1 , end) } } type interval struct { start int end int } func quickSortIterator (nums []int ) length := len (nums) stack := make ([]*interval, 0 ) stack = append (stack, &interval{0 , length - 1 }) for len (stack) != 0 { inter := stack[len (stack)-1 ] stack = stack[:len (stack)-1 ] start, end := inter.start, inter.end if start < end { index := partition(nums, start, end) stack = append (stack, &interval{index + 1 , end}) stack = append (stack, &interval{start, index - 1 }) } } } func partition (nums []int , start, end int ) int pivot, left, right := nums[end], start, end for left < right { for left < right && nums[left] < pivot { left++ } for left < right && nums[right] >= pivot { right-- } nums[left], nums[right] = nums[right], nums[left] } nums[end], nums[left] = nums[left], nums[end] return left }
快速排序动态排序图
快速排序分析
从代码可知，当数组完全正序时，此时选取第一个元素作为基准，一遍排序后分成了两个子序列，其长度分别为 0 和 n-1，此时的时间复杂度 f(n) = f(n-1) + n，则 f(n) 最终趋近于 O(n^2)。而在随机选择基准元素的情况下，一遍排序后分成的两个子序列的长度都接近 n/2 ，此时 f(n) = 2f(n/2) + n，则快速排序的平均时间复杂度最终会趋近于 O(n log n)。
快速排序递归版在递归时使用了函数栈，迭代版需要栈来保存序列的起始信息，所以其空间复杂度为栈的深度 O(log n)，但其没有借助额外的空间来存储数组，所以其排序方式为 In-Place。
相同 key 值，在排序前后其相对位置可能会发生变化，所以快速排序是不稳定排序。
堆排序 （Heap Sort） 原理 ：首先将待排序数组构建为大小为 n 的 最大（小）堆，然后将最大的堆顶元素与数组最后一个元素交换，将最大的元素放在最后一个位置，接下来不断调整最大堆并进行与上面相同的操作，此时堆的大小为 n-1 并依次递减，直至为 0 时，排序完成。堆在本质上是一棵完全二叉树，我们可以将原始数组通过层序遍历的方式构建为一个最大（小）堆。另外，我们可以通过数组元素的位置来表示二叉树父子节点间的关系，比如父节点在数组中的位置为 parent，那么其左子节点在数组的位置为 parent*2+1，其右子节点在数组中的位置为 parent*2+2，这样我们就可以直接在数组中对二叉树的父子节点进行操作了。在建堆时，我们从二叉树最后一个非叶子节点（对应数组的位置为 (n-1)/2）开始来调整堆，使其满足最大（小）堆的性质，直到根节点（对应数组的位置为 0）调整完毕时，建堆完成。
堆排序源码 func heapSort (nums []int ) length := len (nums) if length > 1 { for i := (length - 1 ) / 2 ; i >= 0 ; i-- { maxHeap(nums, i, length) } for i := length - 1 ; i >= 0 ; i-- { nums[i], nums[0 ] = nums[0 ], nums[i] maxHeap(nums, 0 , i) } } } func maxHeap (nums []int , parent, length int ) max, left := parent, parent*2 +1 right := left + 1 if left < length && nums[max] < nums[left] { max = left } if right < length && nums[max] < nums[right] { max = right } if parent != max { nums[parent], nums[max] = nums[max], nums[parent] maxHeap(nums, max, length) } } func minHeap (nums []int , parent, length int ) min, left := parent, parent*2 +1 right := left + 1 if left < length && nums[left] < nums[min] { min = left } if right < length && nums[right] < nums[min] { min = right } if parent != min { nums[parent], nums[min] = nums[min], nums[parent] minHeap(nums, min, length) } }
堆排序动态排序图
堆排序分析
从代码可知，堆排序分为建堆和调整两部分。在建堆的过程中，完全二叉树的高度为 k=log(n)，第 i 层调整所需要的时间为节点个数 2^(i-1) 乘以要调整的高度 k-i，建堆所需的整体时间为每一层的时间相加，最终其时间复杂度趋近于 O(n)。在堆调整的过程中，每次调整需要的时间即为堆的层数 k，共需调整 n 次，累加所有调整的时间，其时间复杂度趋近于 O(n log n)。所以堆排序的整体时间复杂度为二者相加也趋近于 O(n log n)。
堆排序没有借助额外的内存，其空间复杂度为 O(1)，排序方式为 In-Place。
相同 key 值，在排序前后其相对位置可能会发生变化，所以堆排序是不稳定排序。
计数排序 （Counting Sort） 原理 ：统计数组中每个独立元素出现的次数，然后填充数组完成排序。具体实现如下：首先找出待排序数组中最小和最大的元素，并构建一个长度为（max-min+1）大小的数组 count，然后统计每个元素出现的次数并存入数组 count 中，接着累加所有的计数（count 数组中的第一个元素开始，每一项和前一项相加并存入该项），以便得出每个元素在排序数组中的最终位置，最后考虑算法的稳定性，反向填充目标数组（倒序遍历原数组）排序完成，详见稳定版计数排序。当不考虑稳定性时，可以省略辅助数组 extra，直接遍历数组 count，并按顺序将元素放回原数组完成排序，详见优化版计数排序。
计数排序源码 func countingSort (nums []int ) length := len (nums) if length > 1 { min, max := nums[0 ], nums[0 ] for i := 0 ; i < length; i++ { if nums[i] < min { min = nums[i] } if nums[i] > max { max = nums[i] } } k := max - min + 1 count := make ([]int , k) for i := 0 ; i < length; i++ { count[nums[i]-min]++ } for i := 1 ; i < k; i++ { count[i] += count[i-1 ] } extra := make ([]int , length) for i := length - 1 ; i >= 0 ; i-- { count[nums[i]-min]-- extra[count[nums[i]-min]] = nums[i] } for i := 0 ; i < length; i++ { nums[i] = extra[i] } } } func countingSortOptimize (nums []int ) length := len (nums) if length > 1 { min, max := nums[0 ], nums[0 ] for i := 0 ; i < length; i++ { if nums[i] < min { min = nums[i] } if nums[i] > max { max = nums[i] } } k := max - min + 1 count := make ([]int , k) for i := 0 ; i < length; i++ { count[nums[i]-min]++ } index := 0 for i := 0 ; i < k; i++ { for count[i] != 0 { nums[index] = i + min index++ count[i]-- } } } }
计数排序动态排序图
计数排序分析
从代码可知，计数排序的时间复杂度为 O(n + k)，其中 k 为不重复元素的个数。
计数排序需要借助额外的内存，当考虑其稳定性时，其空间复杂度为 O(n + k)，排序方式为 Out-Place。当不考虑其稳定性时，其空间复杂度为 O(k)，排序方式为 In-Place。
相同 key 值，在使用反向填充方法时，排序前后其相对位置不会发生变化，此时计数排序是稳定排序；在使用优化的方法时，排序前后其相对位置可能会发生变化，此时计数排序是不稳定排序。
桶排序（Bucket Sort） 原理 ：桶排序可以理解为计数排序的升级版，在计数排序中，每个桶中只有一个元素，而桶排序通过调整桶的大小可以存放多个元素，从而使得排序更加高效。在进行桶排序时，先将待排序数组分到有限数量的有序桶里（桶的个数由数组中最大和最小元素的差值和桶的大小决定，桶之间按容纳的数值大小顺序排列），然后分别对每个非空桶中的元素进行排序（排序算法可以是其他排序算法也可以是递归的桶排序），最后取出非空桶中元素顺序放回原数组，排序完成。
桶排序源码 func bucketSort (nums []int ) length := len (nums) if length > 1 { min, max := nums[0 ], nums[0 ] for i := 0 ; i < length; i++ { if nums[i] < min { min = nums[i] } if nums[i] > max { max = nums[i] } } bucketSize := 5 bucketNum := (max-min)/bucketSize + 1 buckets := make ([][]int , bucketNum) for i := 0 ; i < length; i++ { bn := (nums[i] - bucketNum) / bucketSize buckets[bn] = append (buckets[bn], nums[i]) } index := 0 for _, bucket := range buckets { if len (bucket) != 0 { insertionSort(bucket) for _, val := range bucket { nums[index] = val index++ } } } } }
桶排序演示图
桶排序分析
从代码可知，桶排序在完全逆序的情况下，时间复杂度最差为 O(n^2)，平均时间复杂度为 O(n + k)，其中 k 为桶的个数。
桶排序需要借助额外的内存，其空间复杂度为 O(n + k)，排序方式为 Out-Place。
相同 key 值，在排序前后其相对位置不会发生变化，所以桶排序是稳定排序。
基数排序（Radix Sort） 原理 ：将整数按位切割成不同的数字，然后按位数分别进行计数排序。具体实现如下：先找出待排序数组的最大数字，并计算其位数，即为最终循环排序的次数，然后按照位数从最低位开始进行计数排序，直到最高位，最后数组排序完成。
基数排序源码 import ( "math" ) func radixSort (nums []int ) length := len (nums) if length > 1 { max := nums[0 ] for i := 0 ; i < length; i++ { if nums[i] > max { max = nums[i] } } digital := maxDigital(max) for i := 0 ; i < digital; i++ { radix := int (math.Pow10(i)) count := make ([]int , 10 ) for j := 0 ; j < length; j++ { count[(nums[j]/radix)%10 ]++ } for j := 1 ; j < 10 ; j++ { count[j] += count[j-1 ] } extra := make ([]int , length) for j := length - 1 ; j >= 0 ; j-- { ci := (nums[j] / radix) % 10 count[ci]-- extra[count[ci]] = nums[j] } for j := 0 ; j < length; j++ { nums[j] = extra[j] } } } } func maxDigital (num int ) int digital := 0 for num != 0 { num = num / 10 digital++ } return digital }
基数排序动态排序图
基数排序分析
从代码可知，基数排序的时间复杂度为 O(n * k)，其中 k 为最大元素的位数。
基数排序需要借助额外的内存（反向填充），其空间复杂度为 O(n)，排序方式为 Out-Place。
相同 key 值，因为采用了反向填充策略，在排序前后其相对位置不会发生变化，所以基数排序是稳定排序。
