插入排序

func insertSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		tmp := nums[i]
		for j := i; j >= 0; j-- {
			if j > 0 && tmp < nums[j-1] {
				nums[j] = nums[j-1]
			} else {
				nums[j] = tmp
				break
			}
		}
	}
}

折半插入排序

func binaryInsertSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		left, right := 0, i-1
		mid := 0
		for left < right {
			mid = (left + right) >> 1
			if nums[mid] > nums[i] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		}
		index := right
		tmp := nums[i]
		if nums[right] < tmp {
			index++
		}
		for j := i; j >= index+1; j-- {
			nums[j] = nums[j-1]
		}
		nums[index] = tmp

	}
}

shell 排序

func shellSort(nums []int) {
	n := len(nums)
	if n == 0 {
		return
	}

	for gap := n / 2; gap > 0; gap = gap / 2 {
		for i := gap; i < n; i++ {
			for j := i - gap; j >= 0 && nums[j] > nums[j+gap]; j -= gap {
				nums[j], nums[j+gap] = nums[j+gap], nums[j]
			}
		}
	}
}

冒泡排序

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

选择排序

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

快速排序

func quickSort(arr []int) {
	if len(arr) <= 1 {
		return
	}
	idx := partition(arr)
	quickSort(arr[:idx])
	quickSort(arr[idx+1:])
}

func partition(a []int) int {
	left := 0
	right := len(a) - 1
	flag := 0
	for left < right {
		for left < right && a[right] >= a[flag] {
			right--
		}
		for left < right && a[left] <= a[flag] {
			left++
		}
		a[left], a[right] = a[right], a[left]
	}
	a[flag], a[right] = a[right], a[flag]
	return right
}

基数排序

func radixSort(a []int) {
	n := len(a)
	lists := make([][]int, 10)
	max := a[0]
	for i := 1; i < len(a); i++ {
		if max < a[i] {
			max = a[i]
		}
	}

	exp := 1
	for max > 0 {
		//将之前的元素清空
		for i := 0; i < 10; i++ {
			lists[i] = []int{}
		}
		for i := 0; i < n; i++ {
			index := a[i] / exp % 10
			array := lists[index]
			array = append(array, a[i])
			lists[index] = array
		}
		index := 0
		for i := 0; i < 10; i++ {
			arr := lists[i]
			for j := 0; j < len(arr); j++ {
				a[index] = arr[j]
				index++
			}
		}
		max /= 10
		exp *= 10
	}
}

归并排序

func mergeSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	left, right := 0, len(nums)
	mid := (left + right) >> 1
	return merge(mergeSort(nums[:mid]), mergeSort(nums[mid:]))

}
func merge(left, right []int) []int {
	res := make([]int, 0, len(left)+len(right))
	leftIndex := 0
	rightIndex := 0
	for leftIndex < len(left) || rightIndex < len(right) {
		if leftIndex < len(left) && rightIndex < len(right) {
			if left[leftIndex] < right[rightIndex] {
				res = append(res, left[leftIndex])
				leftIndex++
			} else {
				res = append(res, right[rightIndex])
				rightIndex++
			}
		} else if leftIndex == len(left) && rightIndex < len(right) {
			res = append(res, right[rightIndex])
			rightIndex++
		} else if rightIndex == len(right) && leftIndex < len(left) {
			res = append(res, left[leftIndex])
			leftIndex++
		}
	}
	return res
}

堆排序

func heapSort(a []int) {
	//构建大顶堆
	lenA := len(a)
	for i := len(a)/2 - 1; i >= 0; i-- {
		adjustHead(a, i, lenA)
	}
	for i := len(a) - 1; i > 0; i-- {
		a[0], a[i] = a[i], a[0]
		adjustHead(a, 0, i)
	}

}
func adjustHead(a []int, i, length int) {
	tmp := a[i]
	//用k := 2*i + 1 的到i子节点的位置
	for k := 2*i + 1; k < length; k = 2*k + 1 {
		// 让k先指向子节点中最大的节点
		if k+1 < length && a[k] < a[k+1] {
			k++
		}
		if a[k] > tmp { //子节点比根节点大
			a[i], a[k] = a[k], a[i]
			i = k
		} else {
			break
		}
	}
}

KMP查找子串

func kmp(str string, needle string) int {
	next := makeNext(str)
	j := 0
	for i := 0; i < len(str); i++ {
		for j > 0 && str[i] != needle[j] {
			j = next[j-1]
		}
		if str[i] == needle[j] {
			j++
		}
		if j == len(needle) {
			return i - j + 1
		}
	}
	return -1
}

func makeNext(s string) []int {
	next := make([]int, len(s))
	next[0] = 0
	k := 0
	for i := 1; i < len(s); i++ {
		for k > 0 && s[k] != s[i] {
			k = next[k-1]
		}
		if s[k] == s[i] {
			k++
		}
		next[i] = k
	}
	return next
}