排序

快速排序

快排是不稳定的
快速排序采用的是分治的思想：

第二步进行区间的调整，最简单的做法是采取暴力的形式：

第二种做法：

第三种做法--优秀做法

分界点为x，i从左边查起，j从右边查起；i++,当i遇到一个大于等于x的值，停下；j--,当j遇到一个小于等于x的值，j停下,然后swap(q[i],q[j]),直到i==j，第一次查询结束，此时区间已经调整完毕

func quickSort(q []int,l int,r int) {
    if l>=r {
        return
    }
    x,i,j := q[l],l-1,r+1
    for i < j {
        for{ //类似于C++中的do...while循环
            i++
            if q[i] >= x {
                break
            }
        }
        for{
            j--
            if q[j] <= x {
                break
            }
        }
        if i < j {
            swap(&q[i],&q[j])
        }
    }
    quickSort(q,l,j)
    quickSort(q,j+1,r)
}
func swap(a,b *int) {
    *a,*b = *b,*a
}

算法性能分析

归并排序

归并排序是稳定的
归并排序的中心思想也是分治

将两个已经排好序的数组合二为一，每次将两个数组进行比较，选择最小的那一个插入结果数组中

var n int
var q[]int
var temp [N]int

func mergeSort(q []int,l int,r int) {
    if l >= r {
        return 
    }
    mid := (l + r) >> 1
    mergeSort(q,l mid)
    mergeSort(q,mid+1,r)
    k,i,j := 0,l,mid+1
    for i <= mid && j <= r {
        if q[i]<=q[j] {
            temp[k] = q[i]
            k,i = k++,i++
         }else{
            temp[k] = q[j]
            k,j = k++,j++
        }
    }
    for i <= mid {
        temp[k] = q[i]
        k,i = k++，i++
    }
    for j <= r {
        temp[k] == q[j]
            k,j = k++,j++
        }
    //最后还需要把结果重新存回q数组中
    for i,j = l,0 ; i<=r ;i,j = i++,j++ {
        q[i] = temp[j]
    }
}

算法性能分析

二分

整数二分

找到一个性质，可以将整个区间一分为二，区间不一定非要满足单调的性质。
二分之后可以寻找边界点

1、寻找红色边界点

//区间[l,r]被划分成[l,mid-1]和[mid,r]时使用
func search_2(l,r int) int{
    for l < r {
        //这里是为了避免出现死循环的情况，比如l=r-1，此时如果不加1，则mid仍然等于l，因为这里是向下取整
        mid := l + r + 1 >> 1 
        if check(mid) {
            l = mid
        }else{
            r = mid-1
        }
    }
    return l
}

2、寻找绿色边界点

//区间[l,r]被划分为[l,mid]和[mid+1,r]时使用
func search_2(l,r int) int{
    for(l<r){
        mid := l + r >> 1
        if check(mid){
            r = mid
        }else{
            l = mid+1
        }
    }
    return l
}

浮点数二分

不需要处理边界问题

高精度

用数组将整数的每一位存进去，从低位开始存储

两个大整数相加（两数的位数<=10的6次方）

func add(A []int,B []int) []int{
    var C []int
    t := 0
    for i := 0 ; i < len(A) || i < len(B) ; i++ {
        if i < len(A){t += A[i]}
        if i < len(B){t += B[i]}
        C = append(C,t%10)
        t = t / 10
    }
    if t > 0 {
        C = append(C,t)
    }
    return C
}

两个大整数相减（两数的位数<=10的6次方）

若A>=B则直接求A-B，否则求-（B-A ）

func cmp(A []int,B []int) bool {
    if len(A) != len(B){
        return len(A) > len(B)
    }
    for i := len(A)-1; i >= 0 ; i-- {
        if A[i] != B[i]{
            return A[i] > B[i]
        }
    }
    return true
}
//A>B
func sub(A []int,B []int) []int{
    var C []int
    for i,t := 0,0 ; i < len(A) ; i++ {
        t = A[i] - t
        if i < len(B){
            t = t-B[i]
        }
        C = append(C,(t+10)%10)
        if t < 0 {
            t = 1
        }else{
            t = 0
        }
    }
    for len(C) > 1 && C[len(C)-1] == 0 {
        C = C[:len(C)-1]
    }
    return C
}

一个大整数*一个较小的数（大数的位数<=10的6次方，小数<=10000）

用A的每一位分别和B相乘，再考虑后面的计算

func mul(A []int,b int) []int{
    var C []int
    t := 0 //这是进位
    for i := 0 ; i < len(A) || t > 0 ; i++ {
        if i < len(A) {
            t += A[i]*b
        }
        C = append(C,t%10)
        t = t / 10
    }
    return C
}

一个大整数/一个较小的数

func div(A []int,b int) []int{
    var C []int
    t := 0
    for i := len(A)-1 ; i >= 0 ; i++ {
        t = t *10 + A[i]
        C = append(C,t/b)
        t = t % b
    }
    for len(C) > 1 && C[0] == 0 {
        C = C[1:]
    }
    return C
}

前缀和与差分

一维前缀和

前缀和：

for i := 1 ; i <= n ; i ++ {
    S[i] = S[i-1] + a[i]
}

作用：可以用来求一段区间内的和
求[l,r]上的和：S[r]-S[l-1]

var a []int = make([]int,N+1)
var s []int = make([]int,N+1)
s[0] = 0
func pre_sum(l,r int) int {
    for i := 1 ; i <= N ; i++ {
         s[i] = s[i-1] + a[i]
    }
    res := s[r] - s[l-1]
    return res
}

二维前缀和

Si,j是以(i,j)为界点的左上角所有元素的和

要求中间蓝色小矩形的和

var n int
var m int
var a  [][]int = make([][m+1]int,n+1)
var s [][]int = make([][m+1]int,n+1)
func pre_Sum(x1 int,x2 int,y1 int,y2 int) int {
    for i:= 1 ; i <= n ; i++ {
        for j:= 1 ; j<= m ; j++{
            s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j] //求前缀和
        }
    }
    res := s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1] //算子矩阵的和
    return res
}

一维差分

已知数组a，构造数组b，使得数组a成为数组b的前缀和，则b就称为a的差分

用处：假如现在想让a[l]到a[r]内的数都加上一个常数c，那么只需要让b[l]+c并且b[r+1]-c即可

insert(i,i,a[i])是在构造差分数组b

二维差分

想让蓝色小方框内的元素都加常数c

位运算

操作一：n>>k & 1

n的二进制表示中第k位是几

操作二：lowbit操作

lowbit(x):返回二进制数x的最后一位1
x = 101000
lowbit(x) = 1000 (返回的是一个二进制数，该二进制数的最高位是1)
lowbit(x) = x & -x = x & (~x+1)

应用：用来统计x中1的个数


计算机在底层实现的时候是没有减法的，所以要利用加法来实现减法，因此负数要用补码来进行表示

离散化

值域跨度很大，但是值的个数很少

应用

区间合并

将所有有交集的区间合并成同一个区间
/*排序+合并
1.先对区间首部从小到大排序。
2.遍历、合并重合区间：
如果cs的尾部小于当前区间的头，即不相交，添加到结果集，并将尾部指到当前区间的尾部。
如果cs的尾部小于等于当前区间的尾，即有重合区域，合并： 将当前区间尾赋到cs的尾。

*/

func merge(intervals [][]int) [][]int {
    var res [][]int
    if len(intervals) == 0 || len(intervals[0]) == 0 {
        return res
    }
    sort.Slice(intervals,func(i,j int)bool{
        return intervals[i][0] < intervals[j][0]
    })
    l := intervals[0][0]
    r := intervals[0][1]
    i := 1
    for  i < len(intervals)  {
        if intervals[i][0] > r {
            ans := []int{l,r}
            res = append(res,ans)
            l = intervals[i][0]
            r = intervals[i][1]
        }else{
            r = max(r,intervals[i][1])
        }
        i++
    }
    res = append(res,[]int{l,r})
    return res
}

func max(a,b int) int{
    if a > b {
        return a
    }
    return b
}