冒泡排序

介绍

​ 冒泡排序是一种比较简单的排序，之所以叫冒泡，是因为在两两比较的过程中较大的数就像冒泡一样被换到后面。详细解释：依次比较相邻的两个数，前面的数大于后面的数，则交换，将较大的数挪动到后面

• 第1轮: 比较1 – N 经过依次相邻两两比较交换 最大的数则放到了最后
• 第2轮: 比较1 –N-1 经过依次相邻两两比较交换 第2大的数则放到了N-1的位置
• 第N-1轮:比较1 – 2 前2个数两两比较交换 整个过程完成

代码

BubbleSort

```go func BubbleSort(a []int) { if len(a) < 2 { //一个数或者为空 不用排序 return } //外层循环控控制每轮循环两两比较的最大下标 第1次为N-1 最后一次为1(也就是最前面的2个元素) for endPos := len(a) - 1; endPos > 0; endPos-- { //内层循环完成两两比较交换 for i := 0; i < endPos; i++ { if a[i] > a[i+1] { a[i], a[i+1] = a[i+1], a[i] } } } } ```

时间复杂度

​ O($N^2$)

稳定性

​ 稳定 因为如果2个数相等 则他们的相对位置 并没有发生改变

优化

​ 看内层循环 如果并没有发生数据交换 则证明所有数据已经排序完成，这个时候直接结束即可 加一个标志判断即可

BubbleSortOpt

```go func BubbleSort(a []int) { if len(a) < 2 { //一个数或者为空 不用排序 return } isChg := false //外层循环控控制每轮循环两两比较的最大下标 第1次为N-1 最后一次为1(也就是最前面的2个元素) for endPos := len(a) - 1; endPos > 0; endPos-- { //内层循环完成两两比较交换 for i := 0; i < endPos; i++ { if a[i] > a[i+1] { a[i], a[i+1] = a[i+1], a[i] isChg = true } } if !isChg { //如果内层循环没有发生数据交换 则表明所有数据都已经排序完成 直接退出循环即可 break } } } ```

网搜图解

​ 摘自: https://www.cnblogs.com/onepixel/p/7674659.html

插入排序

介绍

​ 插入排序顾名思义就是将一个待排序的元素，插入到一组已经排好序的元素中，如果形象比喻下，可以想象一下打牌，拿起来第一张牌自然就是排好序的，拿起第二张则跟第一张进行比较，插入到合适的位置。接下来拿第三张 跟前面2张已经排好序的比较，插入合适的位置，依次类推，拿完所有的牌，顺序自然也排好了。

​ 将待排序的元素分为有序区和无序区，按照顺序每次从无序区拿一个元素，插入插入到有序区，直到所有无序区的元素都插入有序区，整个排序过程结束。第一次有序区为第1个元素，无序区为第2—N个元素，拿出第2个元素插入到有序区。

代码

InsertSort

```go func InsertSort(a []int) { if len(a) < 2 { //一个数或者为空 不用排序 return } //j为无序区的第一个元素 对应下标从1开始，每次后移一个位置 for j := 1; j < len(a); j++ { //内层循环完成比较插入 倒序依次跟有序区的元素进行比较，如果小于有序区的元素 则交换 for i := j; i > 0; i-- { if a[i] < a[i-1] { a[i], a[i-1] = a[i-1], a[i] } } } } ```

时间复杂度

​ O($N^2$)

算法稳定性

​ 稳定 没有改变两个相等元素的相对位置

优化

​ 上面代码内层循环在查找待插入位置时是倒序逐个比较的，在查找待插入位置时候是可以优化的，采用二分查找可以有效减少比较次数，但优化后的插入算法则变为不稳定的

InsertSortOpt

```go //BinSerachInsertIndex 二分查找在a数组 begin到end区间 key元素的插入位置 func BinSerachInsertIndex(a []int, begin int, end int, key int) int { pos := -1 //需要插入的位置 for begin <= end { mid := begin + (end-begin)/2 if a[mid] == key { //如果等于key 则找到位置 pos = mid + 1 break } else if a[mid] < key { begin = mid + 1 } else { end = mid - 1 } } if pos == -1 { pos = begin } return pos } func InsertSortOpt(a []int) { if len(a) < 2 { //一个数或者为空 不用排序 return } for j := 1; j < len(a); j++ { begin, end, key := 0, j-1, a[j] //找到插入的位置 pos := BinSerachInsertIndex(a, begin, end, key) //将pos到end区间的元素逐个后移 for index := j; index > pos; index-- { a[index] = a[index-1] } //插入待排序元素 a[pos] = key } } ```

网搜图解

​ 摘自:https://www.cnblogs.com/onepixel/p/7674659.html

归并排序

介绍

​ MergeSort 合并两个有序的序列为1的大的有序的序列，最典型的归并排序可以分2个大的步骤：

1 采用递归思想 将一个大的序列:二分为大致平均的子序列，然后针对每个子序列都再递归二分(最后每个子序列长度都为1)

2 两两子序列合并为有序序列 直到所有子序列合并完成

​ 整体归并排序也用到了很重要的分治思想，也就是将大的问题分为小的问题 逐个解决

代码

MergeSort

```go func MergeSort(a []int, left int, right int) { //校验 if len(a) < 2 || left < 0 || right > len(a) || left >= right { return } mid := left + (right-left)/2 //数组中间位置 MergeSort(a, left, mid) //左边归并排序 MergeSort(a, mid+1, right) //右边递归排序 MergeSlice(a, left, mid, right) //合并2个子序列为大的有序序列 } func MergeSlice(a []int, left int, mid int, right int) { //先生成1个辅助空间 长度 容量都是right-left+1 help := make([]int, right-left+1, right-left+1) helpIndex := 0 //help数组起始位置 填入一个数值 往后移动一位 //定义2个下标 开始分别指向2个子区间的最开始位置 然后逐个遍历 LIndex := left RIndex := mid + 1 for LIndex <= mid && RIndex <= right { if a[LIndex] <= a[RIndex] { //左边区间数值较小 左边进辅助空间 help[helpIndex] = a[LIndex] LIndex++ } else { help[helpIndex] = a[RIndex] RIndex++ } helpIndex++ //不管左边区间进辅助还是右边区间 辅助数组下标下移一个位置 因为必定进了一个数 } for LIndex <= mid { //如果遍历完成 左边区间还有数没放进辅助数组 那就说明剩下的左边区间数较大 依次cp进辅助 help[helpIndex] = a[LIndex] LIndex++ helpIndex++ } for RIndex <= right { //如果遍历完成 左边区间还有数没放进辅助数组 那就说明剩下的左边区间数较大 依次cp进辅助 help[helpIndex] = a[RIndex] RIndex++ helpIndex++ } //辅助空间已经排好序 覆盖填回原数组 for i := 0; i < helpIndex; i++ { a[left+i] = help[i] } } ```

时间复杂度

​ O( NLogN)

算法稳定性

​ 稳定

优化

规模较小的时候 不用归并，改为插排

​ 递归其实非常消耗性能 规模较小的时候可以不再递归 较少递归调用次数

MergeSortOpt

```go func MergeSortOpt(a []int, left int, right int) { //一个数 为空 下标不合法 拆分完成 if len(a) < 2 || left < 0 || right > len(a) || left >= right { return } if left+20 >= right {//这里增加几行代码 规模较小 改为插排 InsertSort(a[left : right+1]) return } mid := left + (right-left)/2 //数组中间位置 MergeSort(a, left, mid) //左边归并排序 MergeSort(a, mid+1, right) //右边递归排序 MergeSlice(a, left, mid, right) //合并2个子序列为大的有序序列 } ```

检查合并前两个数组是否已经有序 没有必要再调用合并了

MergeSortOpt2

```go func MergeSortOpt2(a []int, left int, right int) { //一个数 为空 下标不合法 拆分完成 if len(a) < 2 || left < 0 || right > len(a) || left >= right { return } if left+20 >= right {//这里增加几行代码 规模较小 改为插排 InsertSort(a[left : right+1]) return } mid := left + (right-left)/2 //数组中间位置 MergeSort(a, left, mid) //左边归并排序 MergeSort(a, mid+1, right) //右边递归排序 if a[mid]<=a[mid+1]{//如果2个子序列本身已经有序 无需再合并 return } MergeSlice(a, left, mid, right) //合并2个子序列为大的有序序列 } ```

网搜图解

选择排序

介绍

​ 每轮都选择一个极值(最大或者最小)放到数组的某一端，其实也是分为有序区和无序区，刚开始全是无序区，

第1轮 遍历N个数 挑选极值放到数组最左侧 有序区有1个数

第2轮 遍历剩下的N-1个数，挑选极值放入数组第2个位置，也就是依次放入有序区

…

直到剩下最后一个元素 这个元素自然是整个数组的极值 整个数组排序完成

代码

SelectSort

```go func SelectSort(a []int) { if len(a) < 2 { //一个数或者为空 不用排序 return } for j := 0; j < len(a)-1; j++ {//控制每轮循环 遍历比较的元素个数 min := j //min记录最小元素下标 for i := j + 1; i < len(a); i++ { if a[min] > a[i] { min = i } } a[j], a[min] = a[min], a[j] //将最小元素依次放入有序区 } } ```

时间复杂度

​ O($N^2$)

算法稳定性

​ 不稳定 会改变两个相等元素本身的相对位置 如 (7) 2 4 8 3 4 [7] 1 第一轮下来(7)会跑到最后

优化

​ 修改内层循环，每一轮遍历 不仅找到最小下标 也要找到最大下标 最小放数组左边，最大放数组右边，减少循环次数，当然外层循环条件也要修改，最开始无序区为整个数组 每一轮下来 数组两端2个元素变为有序，有序区从两端往中间扩大，直到所有元素都为有序

SelectSortOpt

```go func SelectSortOPT(a []int) { if len(a) < 2 { //一个数或者为空 不用排序 return } //刚开始left right分别为数组最小和最大下标 每轮循环left和rignt分别放置最小和最大值 //终止条件为left==right 每轮循环后left右移 right左移 for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 { minIndex, maxIndex := left, right for i := left; i <= right; i++ { if a[i] < a[minIndex] { //找到最小值下标 minIndex = i } if a[i] > a[maxIndex] { //找到最大值下标 maxIndex = i } } a[left], a[minIndex] = a[minIndex], a[left]//最小的放当前无序区最左边 if left == maxIndex { //如最大下标就是刚开始的最小下标 因为已经交换到了minIndex位置 所以最大下标也要跟着修改 maxIndex = minIndex } a[maxIndex], a[right] = a[right], a[maxIndex]//最大值放到当前无序区最右边 } } ```

网搜图解

​ 摘自： https://www.cnblogs.com/onepixel/p/7674659.html

堆排序

介绍

二叉堆介绍

堆排序是借助堆这种数据结构进行排序，又分为最大堆和最小堆。堆也分很多种，这里用二叉堆，下面从网上找到的2张图展示下最大堆和最小堆。

​ 最大堆 所有父节点都**>=两个子节点 最小堆 所有父节点都<=**两个子节点

​ 最大堆 可用于升序排序 最小堆可用于降序排序

​ 二叉堆实现方式不止一种，这里选择最简单的数组实现，下图展示二叉堆如何用数组存放以及父子节点关系如何对应到数组下标关系。

堆排序大致过程

• 首选遍历数组 构建二叉堆(数组实现)

• 交换堆头尾两个元素，也就是数组头尾元素，最大值放到了数组最后一个元素。因为根节点发生变化

  所以重新堆化，范围不包括最后一个元素，最后一个元素相当于已经输出排序完成，为最大值。

• 对于重新堆化的前面N-1个元素 循环执行第2步 直到输出所有堆节点 完成最终排序

代码

最大堆

MaxHeapSort

```go func MaxHeapSort(a []int) { size:=len(a)//数组长度 if size < 2 { return } for i := 0; i < len(a); i++ {//遍历数组 构建堆 MaxHeapInsert(a, i) } for size > 0 { a[0], a[size-1] = a[size-1], a[0] //将当前堆顶也就是最大值放到最后 把最后的元素换到堆顶 然后重塑堆 size-- MaxHeapify(a, 0, size) } } func MaxHeapInsert(a []int, index int) { //如果插入节点大于父节点 则需要向上调整 先跟父节点交换 然后再比较上面的父节点 for parentIndex := (index - 1) / 2; a[index] > a[parentIndex]; index, parentIndex = parentIndex, (index-1)/2 { a[index], a[parentIndex] = a[parentIndex], a[index] } } //大堆 重新堆化过程 func MaxHeapify(a []int, index int, size int) { for maxIndex := -1; maxIndex != index; { maxIndex = index leftIndex := 2*index + 1 rightIndex := 2*index + 2 //求当前节点 左孩子 右孩子中最大值对应的下标 if leftIndex < size && a[maxIndex] < a[leftIndex] { maxIndex = leftIndex } if rightIndex < size && a[maxIndex] < a[rightIndex] { maxIndex = rightIndex } if maxIndex != index { a[index], a[maxIndex] = a[maxIndex], a[index] //跟左孩子、右孩子中最大的交换 index = maxIndex maxIndex = -1 } } } ```

最小堆

MinHeapSort

```go func MinHeapSort(a []int) { if len(a) < 2 { return } for i := 0; i < len(a); i++ { MinHeapInsert(a, i) } size := len(a) for size > 0 { a[0], a[size-1] = a[size-1], a[0] //将当前堆顶也就是最大值放到最后 把最后的元素换到堆顶 然后重塑堆 size-- MinHeapify(a, 0, size) } } //MinHeapInsert 创建大堆 数组实现 index为要插入的元素下标 //节点下标为i 对应左孩子为2*i+1 右边孩子为2*i+2 //节点下标为i 对应父节点为(i-1)/2 func MinHeapInsert(a []int, index int) { parentIndex := (index - 1) / 2 for a[index] < a[parentIndex] { //如果插入节点小于父节点 则需要向上调整 先跟父节点交换 然后再比较上面的父节点 a[index], a[parentIndex] = a[parentIndex], a[index] index = parentIndex parentIndex = (index - 1) / 2 } } //MinHeapify 下标index发生了变化 重塑堆 一路向下调整 如果两个孩子中有一个比自己小 则交换 然后继续往下调整找到比自己小的孩子 然后跟其交换 //节点下标为i 对应左孩子为2*i+1 右边孩子为2*i+2 //节点下标为i 对应父节点为(i-1)/2 func MinHeapify(a []int, index int, size int) { for minIndex := -1; minIndex != index; { minIndex = index leftIndex := 2*index + 1 rightIndex := 2*index + 2 //求当前节点 左孩子 右孩子中最小值对应的下标 if leftIndex < size && a[minIndex] > a[leftIndex] { minIndex = leftIndex } if rightIndex < size && a[minIndex] > a[rightIndex] { minIndex = rightIndex } if minIndex != index { a[index], a[minIndex] = a[minIndex], a[index] //跟左孩子、右孩子中最小的交换 index = minIndex minIndex = -1 } } } ```

## 时间复杂度

​ O(NlogN)

算法稳定性

​ 不稳定

优化

​ 当前实现的就是原地堆排序，没有使用额外的辅助空间，暂无好的优化思路，待补充

网搜图解

希尔排序

介绍

​ 希尔排序是直接插入排序的优化版本，由一个叫shell的人提出来的，核心思想是按照步长分组，然后每组分组插排，然后缩短步长分组，继续每组插排，最后步长为1，变为直接插排。

​ 关于步长及缩短步长如何选择，有很多种方案，可以直接分半，然后再除以2 最后为1，这里采用的Knuth序列，也就是按照下面的规律递增

gap=1—–»gap=3*gap+1

代码

ShellSort

```go func ShellSort(a []int) { //步长采用knuth序列 变化规律为 h=1 ---> h = 3*h+1 h := 1 for h <= len(a)/3 { h = 3*h + 1 } //控制gap递减 最后变为1 for gap := h; gap > 0; gap = (gap - 1) / 3 { //控制分组 for j := gap; j < len(a); j++ { //每组进行直接插排 for i := j; i > gap-1; i = i - gap { if a[i] < a[i-gap] { a[i], a[i-gap] = a[i-gap], a[i] } } } } } ```

时间复杂度

O($N^3/2$)

算法稳定性

​ 不稳定

优化

​ 待补充

网搜图解

快速排序

介绍

​ 快速排序主要用到了分治和递归思想，跟归并排序差不多，快速排序一般要选择一个基准值(pivot),然后将小于这个基准的放左边，大于这个基准的放右边，基准值放那边无所谓，这样一轮下来，数组分成了2个区域，左边区域比右边区域小，然后对2个区域用递归的方法继续快排。

​ 这里的快速用荷兰国旗问题分成了3个区域，<pivot | ==pivot | >pivot 然后递归 <pivot 和>pivot的区域 继续分区快排序

​ 关于基准值的选取可以有很多种，可以随机选取，可以最前面的，可以最后面的，这里采用的是最常见(选取最末端元素)

代码

QuickSort

```go func QuickSort(a []int, left int, right int) { if len(a) < 2 || left >= right { return } base := a[right] //基准选取最末端元素 equalArea := PartitionIntSlice(a, left, right, base) QuickSort(a, left, equalArea[0]-1) //递归快排小于区间 QuickSort(a, equalArea[1]+1, right) //递归快排大于区间 } //PartitionIntSlice 给定一个数组，左边界left 右边界right 比较基准base //返回一个2个数值的int数组 该数组第一个值为等于base的开始位置 第二个值为等于base的结束位置 //所以下标小于该数组第一个值的区间都小于base 下标大于数组第二个值的区间都大于base func PartitionIntSlice(a []int, left int, right int, base int) [2]int { l := left - 1 //l为小于区间的结束下标 刚开始指向最小下标左边 r := right + 1 //l为大于区间的开始下标 刚开始指向最大下标右边 cur := left //当前遍历的数设置为整个区间最左边 for cur < r { if a[cur] < base { //如果当前数小于基数 当前数和小于区间的下一个数交换 小于区间扩一个 a[cur], a[l+1] = a[l+1], a[cur] l++ cur++ } else if a[cur] > base { //如果当前数大于基数 则cur下标++ a[cur], a[r-1] = a[r-1], a[cur] r-- } else { //当前数跟基数相等 不变 cur++ } } return [2]int{l + 1, r - 1} } ```

时间复杂度

​ O(NlogN)

算法稳定性

​ 不稳定

优化

​ 可以选择双轴快排序，也就是选择2个base(不相同,相同的话就又变成了荷兰国旗) 分区为 <minbase | minbase<= && <=maxBase | >maxbase

代码后续补充

网搜图解

计数排序

介绍

​ 计数排序的应用场景比较清晰，也是桶排序的一种。明确的知道一个数组有N的整数，量比较大，但是数据范围比较小 都是[0,MAX), 然后创建一个计数数组，长度为MAX,计数数组值都初始化为0，然后遍历原数组，将原数组的值和计数数组的下标对应起来，比如原数组某个元素值为1，则计数数组下标为1的元素加1，表示1的元素出现过一次，这个步骤可以叫做入桶。然后顺序遍历计数数组，如果该下标的元素出现过(也就是值>0)，数组元素值为多少，则该下标出桶多少次，依次填回原数组即可。

​

代码

CountingSort

```go func CountSort(a []int, max int) { if len(a) < 2 { return } count := make([]int, max, max) //创建计数的桶 for i := 0; i < len(a); i++ { count[a[i]]++ } indexOfa := 0 for i := 0; i < len(count); i++ { for count[i] > 0 { a[indexOfa] = i indexOfa++ count[i]-- } } } ```

时间复杂度

O(N)

算法稳定性

​ 直接计数排序本身是不稳定的，如果采用累加计数数组，然后倒序遍历原数组结合累加计数数组 则可以实现成稳定的，下面优化版本给出了一个稳定版本

优化

​ 分桶方法可以有很多种，比如0号桶 存放0-9数据 1号桶存放10-19等等都是可以的，每个桶可以再放一个数组 然后对于这个数组进行快排或者插排之类的

如果某个桶数量太大，可以针对这个桶继续分桶等等 这里不再赘述，后续有兴趣再补充。

这里列出一个稳定版本的计数排序

CountSortStable

```go //CountSortStable 桶排序的一种 应用场景 知道一个数组有N个整数 并且范围都是[0 ,MAX) //也就是量大 但是数据范围比较小 稳定版本 采用累加计数数组+倒序遍历原数组 func CountSortStable(a []int, max int) { if len(a) < 2 { return } count := make([]int, max, max) //创建桶 for i := 0; i < len(a); i++ { count[a[i]]++ } //累加计数数组 从下标1开始 其值等于count[i]+count[i-1] for i := 1; i < len(count); i++ { count[i] += count[i-1] //记录原数组元素在原数组出现的最后一个位置 } //然后倒序遍历原数组 这里要用到一个附加数组 help := make([]int, len(a), len(a)) for k := len(a) - 1; k >= 0; k-- { count[a[k]]-- lastIndex := count[a[k]] //这里为了代码好理解 多写一行 help[lastIndex] = a[k] } for i := 0; i < len(help); i++ { a[i] = help[i] } } ```

网搜图解

基数排序

介绍

​ 基数排序也是桶排序的一种，主要思想是按照低优先级先排序 然后再按照高优先级再排序，最后完成排序。

比如整数排序，先按照个位排序，再按照十位排序 再按照百位、千位排序，可以参看图解，比较一目了然

代码

RadixSort

```go //GetMax 返回数组中的最大值 func GetMax(a []int) int { max := a[0] for i := 1; i < len(a); i++ { if a[i] > max { max = a[i] } } return max } //radixSort 传入按照什么基数排序 1 个位 10十位 100百位... func radixSort(a []int, radix int) { help := make([]int, len(a), len(a)) //无论是个位、十位、百位... 都只有0-9 10个数字 所以准备10个桶 bucket := make([]int, 10, 10) for i := 0; i < len(a); i++ { radixNum := (a[i] / radix) % 10 //得到某个基数位的数字 比如345 传入radix是1 也就是个位数也就是3 bucket[radixNum]++ } //这个for循环完成 也就完成了个位数桶计数 比如bucket[1]=3 也就是个位数是1的数字有3个 for j := 1; j < len(bucket); j++ { bucket[j] += bucket[j-1] } //这个for循环完成 桶计数含义发生改变 bucket[1]=3表示个位数<=1的数字有3个 //倒序遍历原数组 按照基数位排序后输出到辅助数组 for k := len(a) - 1; k >= 0; k-- { bucket[(a[k]/radix)%10]-- help[bucket[(a[k]/radix)%10]] = a[k] } for i := 0; i < len(a); i++ { a[i] = help[i] } } //RadixSort 基数排序 先按照个位排序 再按照10位排序 再按照百位排序 ... func RadixSort(a []int) { max := GetMax(a) for radix := 1; max/radix > 0; radix *= 10 { radixSort(a, radix) //依次按照个位 十位 百位 ...排序 } } ```

时间复杂度

​ O(X*2N) 这里的X 主要是指分了多少个基数 比如个位、十位、百位 那X=3 对于每个基数 内部都至少需要2N的时间复杂度

算法稳定性

​ 上面实现的是稳定的 就是采用累加计数 然后倒序遍历数组的方法

优化

​ 待补充

网搜图解

桶排序

介绍

计数排序和基数排序是最常见的2种桶排序思想，不是基于比较的排序思想，桶排序的前提假设大致如下：

1. 假设原数据是大值均匀分布的 量也比较大
2. 在原数据上建立1个函数映射关系 将原数据映射到有限个数的桶上
3. 然后针对每个桶再想办法排序(比如插排、快排等)
4. 最后按照桶顺序依次输出桶里的元素 就完成了整个排序

代码

​ 这里不写代码了

时间复杂度

​ 去掉常数项就是O(N)

算法稳定性

可以做到稳定

优化

待补充

网搜图解

待补充