- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
冒泡排序（Bubble Sort）
算法描述
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iK0Xg6QS-1615043828947)(D:\MarkDownNotes\go语言学习\排序算法.assets\849589-20171015223238449-2146169197.gif)]
代码实现
// BubbleSort 原地排序，排序区间[start,end)
func BubbleSort(arr []int, start, end int) {
for i := start; i < end; i++ {
for j := start; j < end-1-i; j++ {
if arr[j] > arr[j+1] {
// swap
arr[j], arr[i] = arr[i], arr[j]
}
}
}
}
选择排序（Selection Sort）
算法描述
- 初始状态：无序区为R[1…n]，有序区为空；
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6Lwor5Wi-1615043828950)(D:\MarkDownNotes\go语言学习\排序算法.assets\849589-20171015224719590-1433219824.gif)]
代码实现
// SelectionSort ...
func SelectSort(arr []int, start, end int) {
var minIndex = 0
for i := start; i < end-1; i++ {
minIndex = i
for j := i + 1; j < end; j++ {
if arr[minIndex] > arr[j] {
minIndex = j
}
}
arr[minIndex], arr[i] = arr[i], arr[minIndex]
}
}
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
插入排序（Insertion Sort）
算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8FvapKHa-1615043828954)(D:\MarkDownNotes\go语言学习\排序算法.assets\849589-20171015225645277-1151100000.gif)]
代码实现
// InsertionSort ...
func InsertionSort(arr []int) {
n := len(arr)
for i := 1; i < n; i++ {
j := i - 1
for j >= 0 && arr[j] > arr[i] { // 找到第一个小于自己的数字，放在它的后面
j--
}
// 后移数据
tmp := arr[i]
for k := i; k > j+1; k-- {
arr[k] = arr[k-1]
}
// 插入数据
arr[j+1] = tmp
}
}
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
希尔排序（Shell Sort）（ 缩小增量排序）
算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
- 增量序列的取值依次为：5，2，1
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0t2qHoPA-1615043828955)(D:\MarkDownNotes\go语言学习\排序算法.assets\562c11dfa9ec8a136327c52c9d49868fa0ec09fa6aee)]
代码实现
// ShellSort ...
func ShellSort(arr []int) {
n := len(arr)
for i := n / 2; i > 0; i /= 2 { // 设定增量
// 对增量分割的每个序列进行排序
for j := 0; j < n; j++ {
k := j - i
for k >= 0 && arr[k] > arr[j] {
k -= i
}
// 移动数据
tmp := arr[j]
for l := j - i; l > k; l -= i {
arr[l+i] = arr[l]
}
// 插入数据
arr[k+i] = tmp
}
}
}
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。
归并排序（Merge Sort）
算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lhwV6VHE-1615043828957)(D:\MarkDownNotes\go语言学习\排序算法.assets\849589-20171015230557043-37375010.gif)]
代码实现
// MergeSort ...
func MergeSort(arr []int) []int {
n := len(arr)
// 最小分区（递归出口）
if n == 1 {
return arr
}
mid := n / 2
// 左、右分区
left := MergeSort(arr[:mid])
right := MergeSort(arr[mid:])
// 合并左右分区
merge := make([]int, 0, n)
for i := 0; i < n && len(left) > 0 && len(right) > 0; i++ {
if left[0] <= right[0] { // 不加等号会导致排序不稳定
merge = append(merge, left[0])
left = left[1:]
} else {
merge = append(merge, right[0])
right = right[1:]
}
}
if len(left) > 0 {
merge = append(merge, left...)
} else {
merge = append(merge, right...)
}
return merge
}
归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。
快速排序（Quick Sort）
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6LpSduid-1615043828959)(D:\MarkDownNotes\go语言学习\排序算法.assets\849589-20171015230936371-1413523412.gif)]
代码实现
// QuickSort ...
func QuickSort(arr []int) {
i, j := 0, len(arr)-1
// 递归出口
if i < j {
// 选取基准值
pivot := arr[i]
// 选取左边,则从右边开始遍历
for i < j {
// 遍历右边
for i < j && arr[j] >= pivot {
j--
}
arr[i] = arr[j]
// 遍历左边
for i < j && arr[i] <= arr[j] {
i++
}
arr[j] = arr[i]
}
// 基准值定位
arr[i] = pivot
// 递归左边
QuickSort(arr[:i])
// 递归右边
QuickSort(arr[i+1:])
}
}
堆排序（Heap Sort）
算法描述
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2Cev07Zk-1615043828960)(D:\MarkDownNotes\go语言学习\排序算法.assets\849589-20171015231308699-356134237.gif)]
代码实现
// HeapSort ...
func HeapSort(arr []int) []int {
// 建立堆
heap := buildMaxHeap(arr)
for i := len(heap) - 1; i >= 0; i-- {
// 将堆顶元素放到最后面
// 1、删除堆顶元素
// 2、放到最后
_, heap[i] = siftDown(heap[:i+1], 0)
}
return heap
}
// 建立大顶堆
func buildMaxHeap(heap []int) []int {
// 索引从0开始
// 父节点和子节点关系：
// parent = (i - 1) / 2
// left = 2 * i + 1
// right = 2 * i + 2
ret := make([]int, 0, len(heap))
for _, v := range heap {
ret = siftUp(ret, v)
}
return ret
}
// siftUp 向大顶堆中插入节点
func siftUp(heap []int, data int) []int {
// 加入到堆中
n := len(heap)
heap = append(heap, data)
// 维护大顶堆
// 计算父亲节点索引
child := n
parent := (child - 1) >> 1
for child > 0 && heap[parent] < heap[child] {
swap(&heap[parent], &heap[child])
child = parent
parent = (child - 1) >> 1
}
return heap
}
// siftDown 删除大顶堆中的节点
func siftDown(heap []int, index int) ([]int, int) {
// 记录被删除的节点
ret := heap[index]
// 堆中最后一个元素放到当前根节点位置
n := len(heap)
heap[index] = heap[n-1]
heap = heap[:n-1]
// 计算父子节点关系
root := index
left, right := 2*root+1, 2*root+2
maxIndex := -1
// 向下循环
for root < n-1 {
maxIndex = max(heap, root, left, right) // 找到最大值
swap(&heap[root], &heap[maxIndex]) // 根节点更新为最大值
if root == maxIndex {
break
}
root = maxIndex
left, right = 2*root+1, 2*root+2
}
return heap, ret
}
func swap(a, b *int) {
tmp := *a
*a = *b
*b = tmp
}
func max(slice []int, indexs ...int) int {
max := indexs[0]
n := len(slice)
for _, index := range indexs[1:] {
if index >= n {
return max
} else if slice[index] > slice[max] && index < n {
max = index
}
}
return max
}
非比较类排序
计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法描述
iiiC(i)C(i)[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LIX2UT8U-1615043828961)(D:\MarkDownNotes\go语言学习\排序算法.assets\849589-20171015231740840-6968181.gif)]
代码实现
// CountingSort ...
func CountingSort(arr []int) []int {
// 找出最大值和最小值
min, max := arr[0], arr[0]
for _, v := range arr[1:] {
if v > max {
max = v
}
if v < min {
min = v
}
}
// 建立数组C
c := make([]int, max-min+1)
// 扫描待排序数组进行计数
for _, v := range arr {
c[v-min]++
}
// 如果不做这一步则会失去稳定性
for i := range c[1:] {
c[i+1] += c[i]
}
// 填充数组
// 建立临时数组
tmp := make([]int, len(arr))
// 从后向前填充
for i := len(arr) - 1; i >= 0; i-- {
tmp[c[arr[i]-min]-1] = arr[i]
c[arr[i]-min]--
}
return tmp
}
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
算法描述
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4JeuQi1a-1615043828962)(D:\MarkDownNotes\go语言学习\排序算法.assets\849589-20171015232107090-1920702011.png)]
代码实现
懒...
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
基数排序（Radix Sort）
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
算法描述
arrradixradix[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ogOh6HY2-1615043828964)(D:\MarkDownNotes\go语言学习\排序算法.assets\849589-20171015232453668-1397662527.gif)]
代码实现
// RadixSort ...
func RadixSort(arr []int) {
digit := 1
// 初始化
radix := make([]*list.List, 19)
for i := range radix {
radix[i] = list.New()
}
// 找到最大值或者最小值
max, min := arr[0], arr[0]
for _, v := range arr[1:] {
if max < v {
max = v
}
if min > v {
min = v
}
}
// 计算位数
count := 0
for max > 0 || min < 0 {
max /= 10
min /= 10
count++
}
// 排序
index := 0
for digit <= count {
// 按位排序
for i, v := range arr {
index = (v % int(math.Pow10(digit))) / int(math.Pow10(digit-1))
radix[index+9].PushBack(arr[i])
}
digit++
// 每躺排序后都要将填充一次原数组
index = 0
for _, l := range radix {
for l.Len() > 0 {
arr[index] = l.Front().Value.(int)
index++
l.Remove(l.Front())
}
}
}
}