一、排序算法

直接插入排序：O(n2)

for i:=1; i<len; i++ {
 //两段， i之前排好序的， i之后未排好序
 for j:=i; j>0 && arr[j]<arr[j-1]; j-- {
     arr[j], arr[j-1] = arr[j-1], arr[j]
 }
}

希尔排序：O(nlog2n)缩小增量排序，通过将全部的元素分为几个区域，逐步取较小的步长进行排序，到最后就是普通的插入排序。 O(nlog2n)

直接选择排序：O(n2) 每个元素和其它元素比较

var min int
for i:=0; i<len; i++ {
 //1. 类似插入，也是两段
 //2. 从未排好序的选最小的，和排好序的最大的比
 for j:=len; j>i; j-- {
     if arr[j] < arr[min]
         min = j
 }
 if arr[i] == arr[min] {
     continue
 }
    
 arr[i], arr[min] = arr[min], arr[i]
}

堆排序：O(nlog2n) ，将一个无序队列，构建成堆（升序为最大堆，降序最小堆）；将堆顶（根）元素和末尾元素互换；重新调整结构，继续前两步，直到整个有序
计数排序：输入一个数X，确定小于X的元素个数，即可确定X的位置。时间、空间复杂度O(n)

冒泡排序：O(n2)

for i:=0; i<len; i++ {
 //和快排类似，只是比较蠢，只能相邻的两两比较
 //大的往下沉
 for j:=1; j<len-i; j++ {
     if arr[j] > arr[j-1] {
         arr[j], arr[j-1] = arr[j-1], arr[j]
     }
 }
}

快速排序: O(nlog2n) 基数，与冒泡相比，跨度大，迅速。二分的思想。基数的一侧都比另一侧大/小; 速度最快 ``` left, right := 0, len i, j := left, right baseNum = arr[left] for i<=j { for arr[j] > baseNum { j– }

for arr[i] < baseNum { i++ }

arr[i], arr[j] == arr[j], arr[i]
}

arr[i] = baseNum

quickSort(arr, 0, i) quickSort(arr, i+1, len)

8. 归并排序： O(nlog2n) 分而治之， 空间复杂度O(n)。 稳定

func mergeSort(arr []int) []int {

middle = len/2
left := mergeSort(arr[:middle])
right := mergeSort(arr[middle:])

return merge(left, right) }

func merge(left, right []int) []int { var result []int for l<len(left) && r<len(right){ if left[l] > right[r] { result = append(result, right[r]) r++ }else { result = append(result, left[r]) l++ } } result = append(result, left[l:]) result = append(result, right[r:])
return result }

}

# 二、查找算法
## 1. 二分查找
1. 先排序，再二分，复杂度O(log2n)
2. 单调不减，单调不增，

mid, left right while(left < right) if arr[mid] < need { left = mid +1 } else { right = mid } ```

三、Bitmap & 布隆过滤器

四、字符串比较

KMP算法, Rabin–Karp(hash一致)

五、深度优先，广度优先

前者走到头，后者优先遍历邻居

六、贪心算法

当前最好的，如背包放物品，选单位质量价值最高的
A(i+1)可以通过 A(i)推理得到，归纳法

六、动态规划

A(i+1) 需要通过A（1,2,3,4…i）推理出来
第二阶数学归纳法

常用算法