golang实现各种排序 - golang

趁着疫情隔离期间，打算把以前丢掉的算法重新捡起来。。。ε=(´ο｀*))) 唉

第一天，先复习以前的知识：

无非就是从后往前去遍历，如果满足条件就把值 place：

	func (A SortByAgeName) InsertSort() {
	for i := 1; i < A.Len(); i++ {
	s := A[i]
	j := i - 1 // 游标
	for j >= 0 && A[j].Age > s.Age {
	A[j+1] = A[j]
	j--
	}
	A[j+1] = s
	}
	}

这个排序显然是 stable 的。

插入排序有一个缺点那就是游标是 stepbystep，折半插入就是就是折半查找加上插入排序，它的复杂度并没有改变。

这里参考了 https://zhuanlan.zhihu.com/p/139579615 的代码

普通二分搜索：

	let binatySearch = function(nums){
	let left = 0, right = nums.length - 1

	while (left <= right) {
	let mid = (left + right) >> 1

	if (nums[mid].value == target) {
	return mid
	}
	else if (nums[mid].value < target) {
	left = mid + 1
	}
	else { // nums[mid].value > target
	right = mid - 1
	}
	}
	return -1
	}

右边界二分搜索：

最终 right 停的地方就是右边界第一个满足或不满足条件的值。

左边界二分搜索：

最终 left 停的地方就是右边界第一个满足或不满足条件的值。

如果忘记的话就是查看上面的链接，这个东西容易忘，而且也挺难去理解的。

二分插入排序就很好写了：

	func (A SortByAgeName) HalfInsertSort() {
	for i := 1; i < A.Len(); i++ {
	s := A[i]
	left, right := 0, i-1
	for left <= right {
	mid := left + (right-left)/2
	if A[mid].Age <= s.Age { // 因为要保证稳定，Stable
	left = mid + 1
	} else {
	right = mid - 1
	}
	}
	for j := i - 1; j >= right+1; j-- {
	A[j+1] = A[j]
	}
	A[right+1] = s
	}
	}

	func (A SortByAgeName) ShellInsertSort() {
	step := A.Len() / 2
	for ; step >= 1; step /= 2 {
	for j := step; j < A.Len(); j += step {
	s := A[j]
	k := j - step
	for k >= 0 && A[k].Age > s.Age {
	A[k+step] = A[k]
	k -= step
	}
	A[k+step] = s
	}
	}
	}

就是多个步长使用插入排序，这个东西我至少没用过。

	func (A SortByAgeName) BubbleSort() {
	for i := 1; i < A.Len(); i++ {
	for j := 0; j < A.Len()-i; j++ {
	if A[j+1].Age < A[j].Age {
	A[j], A[j+1] = A[j+1], A[j]
	}
	}
	}
	}

冒泡排序属于交换排序，每次冒泡就把最大的那个元素交换到最末尾。

	func (A SortByAgeName) QuickSort(left, right int) {
	i, j := left, right
	if right <= left {
	return
	}
	t := rand.Intn(right-left+1) + left
	base := A[t]
	A[right], A[t] = A[t], A[right]
	for left < right {
	for left < right && A[left].Age <= base.Age {
	left += 1
	}
	A[right] = A[left]
	for left < right && A[right].Age >= base.Age {
	right -= 1
	}
	A[left] = A[right]
	}
	// 永远会多保存一份副本，所以直接把 base 填在 right 处就行了
	A[right] = base
	A.QuickSort(i, right-1)
	A.QuickSort(right+1, j)
	}

这个快排版本和我之前写的有些不一样的地方在于，选取 base 是随机的而不是直接选取 right 或 left 作为 base。

代码并不复杂，忘记的话就多看几遍就懂了。

理解堆排序的核心在于理解建堆，先上代码：

	func (A SortByAgeName) HeapSort() {
	adjust := func(start, len int) {
	i := start
	j := start*2 + 1
	for j < len {
	if j+1 < len && A[j].Age < A[j+1].Age { // 有左孩子，并且左孩子比右孩子小
	j = j + 1
	}
	if A[i].Age < A[j].Age {
	A[j], A[i] = A[i], A[j]
	}
	i = j
	j = i*2 + 1
	}
	}
	// create
	for i := A.Len() / 2; i >= 0; i-- {
	adjust(i, A.Len())
	}
	// sort
	for i := 0; i < A.Len(); i++ {
	A[0], A[A.Len()-i-1] = A[A.Len()-i-1], A[0]
	adjust(0, A.Len()-i-1)
	}
	}

每次在于自上而下进行调整。