1. 前言
排序在算法题中是很常见的，在我们一些业务上也会经常用到排序，比如我上次做一个需求需要二次排序的时候就用到了排序算法,下面的代码实现均用go实现。
2. 参考资料
3. 复杂度
| 排序方法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 | 简单 |
| 选择排序 | O(n²) | O(n) | O(n²) | O(1) | 不稳定 | 简单 |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 | 简单 |
| 希尔排序 | O(n^1.25) | O(1) | 不稳定 | 较复杂 | ||
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | 较复杂 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(nlogn) | 不稳定 | 较复杂 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 不稳定 | 较复杂 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 | 较复杂 |
4. 算法不稳定性
上面的稳定性，为什么有些会写着不稳定，相信初次接触的朋友们可能会有疑问，可以这么比如：在一个待排序队列中,A和B相等,且A排在B的前面,而排序之后,A排在了B的后面.这个时候,我们说这种算法是不稳定的.
5. 冒泡排序
冒泡排序（Bubble Sort）又称为泡式排序,是一种简单直观的排序算法，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
算法步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
时间复杂度：O(n²)，空间复杂度O(1)
演示：
代码实现：
package main
import (
"fmt"
)
func main() {
arr := []int{3, 4, 6, 1, 2, 5}
fmt.Println(BubbleSort(arr))
}
// BubbleSort 冒泡排序-升序
func BubbleSort(arr []int) []int {
swapped := true
for swapped {
swapped = false
for i := 0; i < len(arr)-1; i++ {
if arr[i+1] < arr[i] {
arr[i+1], arr[i] = arr[i], arr[i+1]
swapped = true
}
}
}
return arr
}
6. 选择排序
选择排序（Selection sort）是一种简单直观的排序算法,在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种
算法步骤:
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
时间复杂度：O(n²)，空间复杂度O(1)
演示：
代码实现：
package main
import "fmt"
func main() {
arr := []int{3, 4, 6, 1, 2, 5}
fmt.Println(SelectionSort(arr))
}
// SelectionSort 选择排序-升序
func SelectionSort(arr []int) []int {
for i := 0; i < len(arr); i++ {
min := i
for j := i + 1; j < len(arr); j++ {
if arr[j] < arr[min] {
min = j
}
}
arr[i], arr[min] = arr[min], arr[i]
}
return arr
}
7. 插入排序
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤:
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
时间复杂度：O(n²)，空间复杂度O(1)
演示：
代码实现：
package main
import "fmt"
func main() {
arr := []int{3, 4, 6, 1, 2, 5}
fmt.Println(InsertionSort(arr))
}
// InsertionSort 插入排序-升序
func InsertionSort(arr []int) []int {
for i, current := range arr {
preIndex := i - 1
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex -= 1
}
arr[preIndex+1] = current
}
return arr
}
8. 希尔排序
希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
对于数组比较大的数据来说，插入排序是很慢的，这是因为它只能在相邻的元素位置之间做交换，每次只能将未排序序列数量减少 1。 希尔排序可解决插入排序的这种局限性，通过交换不相邻的元素位置，使每次可以将未排序序列的减少数量变多。
希尔排序的原理是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
算法步骤:
- 数组列在一个表中并对列排序（用插入排序）
- 重复这过程，不过每次用更长的列来进行
- 最后整个表就只有一列时就排序好了
演示：
代码实现：
package main
import "fmt"
func main() {
arr := []int{3, 4, 6, 1, 2, 5}
fmt.Println(ShellSort(arr))
}
// ShellSort 希尔排序-升序
func ShellSort(arr []int) []int {
n := len(arr)
if n < 2 {
return arr
}
column := n / 2
for column > 0 {
for i := column; i < n; i++ {
j := i
for j >= column && arr[j] < arr[j-column] {
arr[j], arr[j-column] = arr[j-column], arr[j]
j = j - column
}
}
column = column / 2
}
return arr
}
9. 归并排序
归并排序（Merge sort），是创建在归并操作上的一种有效的排序算法，将数组分成两个子数组， 分别进行排序，然后再将它们归并起来（自上而下）。
归并操作（merge）
也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
分治法
归并算法是 分治法 的一个典型应用， 所以它有两种实现方法：
- 自上而下的递归
- 自下而上的迭代
递归法（Top-down）
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
迭代法（Bottom-up）
原理如下（假设序列共有n个元素）：
- 将序列每相邻两个数组进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
- 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
- 重复步骤2，直到所有元素排序完毕，即序列数为1
时间复杂度：O(nlogn)，空间复杂度O(n)
演示：
代码实现：
package main
import "fmt"
func main() {
arr := []int{3, 4, 6, 1, 2, 5}
fmt.Println(Mergesort(arr))
}
// Mergesort 迭代法-归并排序-升序
func Mergesort(items []int) []int {
if len(items) < 2 {
return items
}
var mid = len(items) / 2
return merge(Mergesort(items[:mid]), Mergesort(items[mid:]))
}
// merge 归并操作
func merge(x, y []int) []int {
var r = make([]int, len(x)+len(y))
var i = 0
var j = 0
for i < len(x) && j < len(y) {
if x[i] <= y[j] {
r[i+j] = x[i]
i++
} else {
r[i+j] = y[j]
j++
}
}
for i < len(x) {
r[i+j] = x[i]
i++
}
for j < len(y) {
r[i+j] = y[j]
j++
}
return r
}
10. 快速排序
快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，也是分治法的一个应用，最早由东尼·霍尔提出。事实上，快速排序通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。
算法步骤
- 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
- 分区：重新排序数组，把所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个排序结束之后，基准就排在数组的中间位置。
- 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
时间复杂度分析：
- 最好的情况是每次基准都正好将数组对半分，这样递归调用最少，时间复杂度为 O(nlogn)
- 最坏的情况是每次分区过程，基准都是从最小元素开始，对应时间复杂度为 O(n²)
空间复杂度分析：
快速排序是原地排序，不需要辅助数据，但递归调用需要辅助栈，最好情况下是递归 logn 次，所以空间复杂度为 O(logn)，最坏情况下是递归 n-1 次，所以空间复杂度是 O(n)。
演示：
代码实现：
package main
import (
"fmt"
"math/rand"
)
func main() {
arr := []int{3, 4, 6, 1, 2, 5}
fmt.Println(QuickSort(arr))
}
// QuickSort 三向切分快速排序-升序
func QuickSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
pivot := arr[rand.Intn(len(arr))]
left := make([]int, 0, len(arr))
right := make([]int, 0, len(arr))
middlePart := make([]int, 0, len(arr))
for _, item := range arr {
switch {
case item < pivot:
left = append(left, item)
case item == pivot:
middlePart = append(middlePart, item)
case item > pivot:
right = append(right, item)
}
}
left = QuickSort(left)
right = QuickSort(right)
left = append(left, middlePart...)
left = append(left, right...)
return left
}
11. 堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
算法步骤：
- 将待排序数组构建成大根堆，这个堆为初始的无序区
- 将堆顶元素 R{1} 与最后一个元素 R{n} 交换，此时得到新的无序区（R{1},R{2},...R{n-1}）和新的有序区（R{n}），并且满足 R{1,2,...n-1}<= R{n}
- 由于交换后新的堆顶 R{1} 可能违反堆的性质，需要对当前无序区调整为新堆，然后再次将 R_{1} 与无序区最后一个元素交换，
- 得到新的无序区 R{1},R{2}...R{n-2} 和新的有序区R{n-1},R{n}。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成
演示：
代码实现：
package main
import "fmt"
func main() {
arr := []int{3, 4, 6, 1, 2, 5}
fmt.Println(HeapSort(arr))
}
type maxHeap struct {
slice []int
heapSize int
}
func buildMaxHeap(slice []int) maxHeap {
h := maxHeap{slice: slice, heapSize: len(slice)}
for i := len(slice) / 2; i >= 0; i-- {
h.MaxHeapify(i)
}
return h
}
func (h maxHeap) MaxHeapify(i int) {
l, r := 2*i+1, 2*i+2
max := i
if l < h.size() && h.slice[l] > h.slice[max] {
max = l
}
if r < h.size() && h.slice[r] > h.slice[max] {
max = r
}
if max != i {
h.slice[i], h.slice[max] = h.slice[max], h.slice[i]
h.MaxHeapify(max)
}
}
func (h maxHeap) size() int { return h.heapSize }
func HeapSort(slice []int) []int {
h := buildMaxHeap(slice)
for i := len(h.slice) - 1; i >= 1; i-- {
h.slice[0], h.slice[i] = h.slice[i], h.slice[0]
h.heapSize--
h.MaxHeapify(0)
}
return h.slice
}