选择排序

func selectSort(arr []int){
    for i:=0 ; i<len(arr)-1 ; i++ {
        minIndex := i;
        for j:=i+1 ;j<len(arr);j++ {
            if arr[minIndex] > arr[j] {
                minIndex = j
            }
        }
        arr[i] , arr[minIndex] = arr[minIndex] , arr[i]
    }	
}

时间复杂度O（n）

冒泡排序

func bubbleSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		for j := 0; j < len(arr)-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[i]
			}
		}
	}
}

时间复杂度O（n）

交换（异或运算）

// 相同为零不同为一 —->两个相同的数异或为零
// 异或运算可以理解为无进位相加–就是二进制下1+1=0，并且不向前进一
// a 10110
// b 00111
//ans10001
//由无进位相加可得：异或运算满足交换律和结合律–>一批数异或起来答案一样，无论怎么排序

// 三行代码跑完，两个数就交换过来了
// 假设  a=甲 b=乙
a = a^b  // a= 甲^乙  b= 乙 
b = a^b  // a= 甲^乙  b= 甲^乙^乙 = 甲 
a = a^b  // a= 甲^乙^甲=乙  b=甲
// 但是前提是：a,b是两块独立的区域，不然会爆零

已知数组中只有一种数出现了奇数次，其他的所有数都出现了偶数次，怎么找到出现了奇数次的数

已知数组中有两种数出现了奇数次，其他所有数都出现了偶数次，怎么找到这两种数

（要求时间复杂度为O(n),空间复杂度为O(1)）

// 第一题
func YiHuo (arr []int)int {
	eor := 0
	for i:=0;i<len(arr);i++{
		eor = eor^arr[i]
	}
	return eor
} //因为异或运算顺序无所谓，偶数次都为零

// 第二题
func DoubleYiHuo(arr []int){
    eor1:=0
    for i:=0;i<len(arr);i++{
        eor = eor^arr[i]
    }
    eor2 := 0
    // 因为a!=b，所以a,b肯定有一位是不一样的，eor必然有一个位置是1，所以可以区分两者
    // 可以假设第八位是1，可以使eor2只异或第八位为1的数字，就能得到另外一个数
    rightOne := eor &(~eor+1) //提取出最右侧的1，取反加1再&
    // eor 		1010111100
    //~eor 		0101000011
    //~eor+1	0101000100
    // 求&       0000000100 
    onlyOne := 0
    for _,n := range arr{
        if n&rightOne != 1{
            onlyOne ^= n
        }
    }
    OtherOne := eor ^ onlyOne 
}

秀

插入排序

保证第n-1位之前是有序的，然后从第n位往前看，与n-1位之前的相互比较交换，保证第n位之前都是有序的

func insertSort(arr []int){
    for i:=0;i<len(arr)-1;i++{
        for j:=i+1;j>0;j--{
            if arr[j]<arr[j-1]{
                arr[j] ,arr[j-1] = arr[j-1] ,arr[i]
            }
        }
    }
}

时间复杂度：数据状况不同，时间复杂度不同

但是时间复杂度按照最差情况进行估计，所以时间复杂度位O（n2）

二分

//已经 有序 数组看某个数是否存在
func Double(arr []int, x int)int {
    left :=0
    right := len(arr)-1
    for left<=right {
        middle := (right-left)/2 + left
        if arr[middle] == x{
            return mid
        }else if arr[middle]<x{
            left  = middle+1
        }else{
            right = middle -1
        }
    }
    return -1
}

时间复杂度O（logn）

// 二分另外一个用途
// 一个有序数组，找到大于等于某个数的位置
func Double (arr []int，target int)int{
    left :=0
    right := len(arr)-1
    for left <= right {
        middle := (right-left)/2 +left
        if arr[middle]<target{  //完全看这边加不加等于号
            left = middle +1
        }else{
            right =middle-1
        }
    } 
    return left
}

// arr无序，任何两个相邻数一定不相等，求一个局部最小的位置（在相邻的数中最小）(难)
// 时间复杂度好于O（n）
func ErFen(arr [n]int)int{
    // 判断特殊位置 0/n-1的位置
    if arr[0] < arr[1] {
        return 0
    }
    if arr[n]<arr[n-1]{
        return n
    }
    // 当0与n-1都不是，两者的变化趋势是向中间变小的，因此一定有一个拐点的位置是最小的
    // 不妨取中间的位置m 
    left :=0
    right := len(arr)-1
    for left <=right{
        mid := (left+right)/2
        if arr[mid-1]>arr[mid]&&arr[mid+1]>arr[mid]{
            return mid
        }else if arr[mid-1]<arr[mid]{
            right = mid -1
        }else{
            left = mid +1
        }
    }
    return -1
}

mid = left + (right-left)/2

等价于 mid = left + (right-left)>>1

右移一位就是求中点的意思，而且右移一位比除以二要快

归并排序(递归+合并)

分治思想；就是先分解再合并，先分解成单个数，排完序，再拼凑起来合并

先求中点位置，中点左侧排好序，中点右侧排好序
准备一个辅助数组，双指针比较下，谁小拷贝谁
装备有两个指针，分别指向左右两个数组的头，通过双指针的方法比较

func mergeSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	// 获取分区位置
	mid := len(nums) / 2
	// 通过递归分区
	left := mergeSort(nums[0:mid])
	right := mergeSort(nums[mid:])
	return merge(left, right) // 排序并合并
}
func merge(left []int, right []int) []int {
	i, j := 0, 0                  // 双指针
	m, n := len(left), len(right) //两个数组大小
	var result []int              // 用于存放结果集
	for i < m && j < n {
		if left[i] <= right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}
	for i < m {
		result = append(result, left[i])
		i++
	}
	for j < n {
		result = append(result, right[j])
		j++
	}
	return result
}

func main() {
	arr := []int{2, 3, 5, 1, 2, 3, 6, 2, 3, 6, 7, 1, 4, 7}
	fmt.Println(mergeSort(arr))
}
// out:[1 1 2 2 2 3 3 3 4 5 6 6 7 7]

时间复杂度：

T(N) = 2 *T(N/2) + O(N)

a = 2 b = 2 d = 1

log (b,a) = d

时间复杂度 = O(N*logN) 空间复杂度为O（N）

归并算法的比较行为信息是向下传递的，没有被浪费，因此时间复杂度较小

题目

小和问题

在一个数组中，每一个数左边比当前数小的数积累起来，叫做这个数组的小和

例如 [1 3 4 2 5] 对于4来说，1和3就是比他小的数积累起来等于4

整个数组的小和就是所有小和数加起来（可以暴力解法）

换个思路~~~不如看有多少右边的数比当前数大

对于1 右边有四个数比他大，因此有 4个1

对于3 右边有两个数比他大，因此有 2个3

在merge的比较过程中，对于每个数都是比较并且不重复产生小和的。

func smallSum(arr []int) int {  
	if len(arr) < 2 {  
		return 0  
	}  
	return mergeSortSmallSum(arr, 0, len(arr)-1)  
}  
  
func mergeSortSmallSum(arr []int, left int, right int) int {  
	if left == right {  
		return 0  
	}  
	mid := left + (right-left)/2  
	return 
    mergeSmallSum(arr, mergeSortSmallSum(arr, left, mid), mergeSortSmallSum(arr, mid+1, right), left, mid, right)  
}  
  
func mergeSmallSum(arr []int, sumLeft int, sumRight int, left int, mid int, right int) int {  
	temp := make([]int, right-left+1)  
	i, j, k := left, mid+1, 0  
	totalSum := 0  
	for i <= mid && j <= right {  
		if arr[i] < arr[j] {  
			totalSum += arr[i] * (right - j + 1)  
			temp[k] = arr[i]  
			i++  
		} else {  
			temp[k] = arr[j]  
			j++  
		}  
		k++  
	}  
	for i <= mid {  
		temp[k] = arr[i]  
		k++  
		i++  
	}  
	for j <= right {  
		temp[k] = arr[j]  
		k++  
		j++  
	}  
	for i := 0; i < len(temp); i++ {  
		arr[left+i] = temp[i]  
	}  
	return totalSum + sumLeft + sumRight  
}

快速排序

例子

有一个num和一个数组，需要实现arr中的num左边都是小于num,右边都是大于num的

使用一个指针从左往右遍历，然后把大于Nums的数都扔到右边去，其他的留在左边

其中的实现还需要一个指针指向小于等于num的区域右边界，右边界的右边就是大于Num的

随着i向右边划动，小于num区域只有在（arr[i]<num）时才右扩

荷兰国旗问题 ， num放中间了，其他与上面的问题相同

就可以有两个区域了，小于Num区域和大于num区域，两个指针分别从两边从中间划动

arr[i]<num , 小于区域右扩,i++
arr[i]=num,i++
arr[i]>num,大于区域左扩，i++
当大于区域与i相撞的时候，过程停止

快排1.0

就是把数组中的最后一个数字做划分，划分成大于这个数和小于这个数的两组数，然后把这个数字放中间

接着用这两组数的最后一个数重复刚才的操作，以此类推

快排2.0

借鉴荷兰国旗问题，一开始用最后一个数作为比较，然后把与这个数相等的数放中间，接着用两组的数的最后一个数比较继续做递归…..

快排3.0

最差情况–划分值很偏，所以效率差

随机选一个数放到最后的位置上来做划分，所以是等概率时间

func partition(arr []int, low int, high int) int {
	pivot := arr[high]
	for low < high {
		// 当low指针小于pivot时，low右移
		for low < high && pivot >= arr[low] {
			low++
		}
		// 当low指针>pivot low值移到high值的地方
		arr[high] = arr[low]

		//当high指针值>=pivot，high--
		for low < high && pivot <= arr[high] {
			high--
		}
		arr[low] = arr[high]
	}
	// 最终low,high相遇则是最右边的数的地方
	arr[high] = pivot
	return high
}

func QuickSort(arr []int, low int, high int) {
	if high > low {
		pivot := partition(arr, low, high)
		// 左边部分排序
		QuickSort(arr, low, pivot-1)
		// 右边部分排序
		QuickSort(arr, pivot+1, high)
	}
}

func main() {
	r := []int{2, 1, 6, 8, 4, 5, 6, 9, 1, 2, 3, 7, 8, 5, 1, 6, 4, 5}
	QuickSort(r, 0, 17)
	fmt.Println(r)
    // out : [1 1 1 2 2 3 4 4 5 5 5 6 6 6 7 8 8 9]
    // 空间复杂度log(n)

堆结构

堆结构就是用数组实现的完全二叉树结构（叶子从左往右连续）
完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
堆结构的heapInsert与heapify操作
堆结构的增大与减小
优先级队列结构，就是堆结构

如果数组是从Index=0开始计数，第i个数，左孩子为2i+1，右孩子为2i+2**，父为（i-1）/2

heapInsert过程(important) 元素向上调整

// 就是形成大根堆,每次数的输入都会形成大根堆
// 原理：如果当前的数大于父位置的数，就两个数交换
func heapInsert(nums []int, index int){
    for nums[index] > nums[(index-1)/2]{
        nums[index] , nums[(index-1)/2] = nums[(index-1)/2] , nums[index]
        index = (index-1)/2
    }
}

healpify过程(important) 元素向下调整

// 背景是在堆中删除最大的或者其中某一个值（这个值后来变小了），且使其重新为大根堆
// 从index的位置开始做Heapify
// heapSize表示堆的大小
// index 表示的是空出来的那个值

func Heapify(arr []int, heapSize int, index int) {
	left := 2*index + 1
	right := 2*index + 2

	for left < heapSize {
		largest := index //比较两个孩子和父亲谁比较大
		if right < heapSize && arr[right] > arr[left] {
			largest = right
		} else if arr[left] > arr[index] {
			largest = left
		}
		// 如果是父结点比较大，说明已经是大根堆，退出
		if largest == index {
			break
		}
		// 不然，交换，重新再来
		arr[largest], arr[index] = arr[index], arr[largest]
		index = largest
		left = 2*index + 1
		right = 2*index + 2
	}
}

时间复杂度按高度算O(logn)

堆排序

先自己认为数组不构成堆，heapSize=0 ，然后后面的数字可以认为是不断地加进来新的数字，类似于HeapInsert，从而可以形成一个大根堆
堆中第一个数是最大的，把有效堆中最后一个数和第一个数相互换，同时你会发现第一个数（最大的数）已经来到了最大的位置，然后heapSize–
heapSize表示堆的有效部分，在heapSize范围之外的已经排序好了
同时你会发现第二部的步骤就是Heapify的步骤，最大的数arr[0]与最小的数相互换且还需要形成大根堆

/* 1. 形成大根堆HeapInsert			2. 交换Swap
   3. 重新形成大根堆Heapify		   4. 交换Swap
   5. 重新形成大根堆Heapify		   6. 交换..............	
  */
func HeapSort(arr []int) {
	// 元素小于2
	if len(arr) == 0 || len(arr) < 2 {
		return
	}
	// 形成大根堆
	for i := 0; i < len(arr); i++ {
		HeapInsert(arr, i)      // O（logn）
	}
	// 交换
	heapSize := len(arr)
	arr[0], arr[heapSize-1] = arr[heapSize-1], arr[0]
	// 排序
	for heapSize > 0 {
        Heapify(arr, 0, heapSize)  // O(logn)
		heapSize--
		arr[0], arr[heapSize-1] = arr[heapSize-1], arr[0]
	}
}

时间复杂度为O(nlogn) 空间复杂度为O(1)

注意：

堆结构扩容对时间影响小
系统的堆结构是一个黑盒，具体不能调整，比较固定
有些东西需要手写堆，有些东西可以使用系统的堆结构

对数器

一道题目有两个方法，想知道两个方法哪个好

生成一个随机样本发生器，两个方法一起跑，然后判断两个方法跑出来的东西是否正确

如果不正确，就把随机样本的范围缩小，一点点修改，修改完成后再把范围扩大就行

使用 rand.Seed(time.Now().UnixNano()) rand.Intn(101) 返回随机数

由此可以不依赖线上测试平台

比较器

实质是重载比较运算符
可以应用在特殊标准的排序上 —->系统不认识的数据类型要我们自己设置怎么比较
可以应用在根据特殊标准排序的结构上

返回负数的时候，第一个参数排前面

返回正数的时候，第二个参数排前面

返回零的时候，谁排前面无所谓

计数排序

计数排序简单的来说就是哈希加简单排序

基础思路就是先把slice放入哈希中，然后通过哈希非零值进行排序

// 计数排序
func CountingSort(slice []int)[]int{
	m := make(map[int]int)
	
	for _, v := range slice {
		m[v]++
	}
	
	var result []int
	for i := 0; i < len(m); i++ {
		for j := 0; j < m[i]; j++ {
			result = append(result, i)
		}
	}
	
	return result
}

基数排序

唯一一个不需要看数组中的具体数据大小而能够排序的方法

他是靠位数来比较（个位，十位，百位……..）

思路：

求出这些数组中位数最大的数字
模拟一个队列
将所有数字从个位开始比较到最高位
将比较的结果放入队列中，比较的结果就是，比如41，个位是1，那么就把41加到slice[1]上，像链表一样
总共比较max次，max=第一步中求出的最大值
return

案例：

slice = [71 91 34 25 15]

总共最高位是十位，所以max=2

对每个数的个位开始比较，并放入队列得到

0	1	2	3	4	5	6	7	8	9
	71			34	25
	91				15

再按照队列从左到右的顺序，队列的某个数中从上到下的顺序取出这些数字得

slice2 = [71 91 34 25 15]

按照十位开始比较，并放入队列得到

0	1	2	3	4	5	6	7	8	9
	15	25	34				71		91

再按照队列从左到右的顺序，队列的某个数中从上到下的顺序取出这些数字得

result = [15 25 34 71 91]

就成功了

代码

// 基数排序
func RadixSort(slice []int) []int {
	// 1. 找到最大值
	max := slice[0]
	for _, v := range slice {
		if v > max {
			max = v
		}
	}

	// 2. 计算最大值的位数
	d := 1
	for max/10 > 0 {
		d++
		max /= 10
	}

	// 3. 创建桶
	bucket := make([][]int, 10)

	// 4. 进行d次分配和收集
	for i := 0; i < d; i++ {
		// 4.1. 分配数据
		for _, v := range slice {
			index := v / pow(10, i) % 10
			bucket[index] = append(bucket[index], v)
		}

		// 4.2. 收集数据
		var result []int
		for i := 0; i < 10; i++ {
			result = append(result, bucket[i]...)
		}

		// 4.3. 将数据放回到slice中
		copy(slice, result)
	}

	return slice
}

func pow(i int, i2 int) int {
	result := 1
	for i2 > 0 {
		result *= i
		i2--
	}

	return result
}

该排序只能给数字排序

桶排序

桶排序是基数和计数的结合

其实很简单，一般来说用的不多

假设你现在有0-1的12个数组成的数组
然后你就设置四个桶，范围分别是[0-0.25],[0.25-0.5],[0.5-0.75],[0.75-1]
然后就对整个数组遍历，将满足的数放入相应的桶中
分别对四个桶进行遍历
取出桶中的元素

总的来说就是遍历，但是很无语啊，浪费空间不说，时间其实也没有多节省

func BucketSort(slice []int) []int {
	// 1. 创建桶
	bucket := make([][]int, len(slice))

	// 2. 将数据分配到桶中
	for _, v := range slice {
		index := v / len(slice)
		bucket[index] = append(bucket[index], v)
	}

	// 3. 对每个桶进行排序
	for i := 0; i < len(slice); i++ {
		bucket[i] = CountingSort(bucket[i])
	}

	// 4. 将桶中的数据取出来
	var result []int
	for i := 0; i < len(slice); i++ {
		result = append(result, bucket[i]...)
	}

	return result
}

总结

简单排序就这些了，总的来说现在写了，以后也忘光了，这篇博客的唯一的作用就是以后忘光了可以免费抄答案

就是这样

选择排序

冒泡排序

交换（异或运算）

插入排序

二分

归并排序(递归+合并)

快速排序