go 堆排序 希尔排序 归并排序

go 堆排序

package main

import "fmt"

func main() {
	list := []int{1, -2, -3, 12, 25, 96, 38, 19, 49, 59, 57, 29, 55, 66}
	HeapSort(list)
	fmt.Println(list)
}

func HeapSort(list []int) {
	length := len(list)
	//建立初始堆
	sift(list, 0, length-1)
	for idx := length / 2; idx >= 0; idx-- {
		// 从后往前调整
		sift(list, idx, length-1)
	}
	// 将大根堆的根节点和堆最后一个元素交换，重新对前面的length-1 调整堆
	for idx := length-1; idx >=0; idx-- {
		list[0],list[idx] = list[idx],list[0]
		sift(list,0,idx-1)
	}
	//结果就是逆序输出大根堆
}

func sift(list []int, left, right int) {
	fIdx := left
	sIdx := 2*fIdx + 1
	for sIdx <= right {
		if sIdx < right && list[sIdx] < list[sIdx+1] {
			sIdx++
		}
		if list[fIdx] < list[sIdx] {
			list[fIdx], list[sIdx] = list[sIdx], list[fIdx]
			fIdx = sIdx
			sIdx = fIdx*2 + 1
		} else {
			break
		}
	}
}

时间复杂度

O (nlgn)

go 希尔排序

package main

import "fmt"

func ShellSort(arr []int) {
	n := len(arr)
	h := 1
	for h < n/3 { //寻找合适的间隔h
		h = 3*n + 1
	}
	for h >= 1 {
		//将数组变为间隔h个元素有序
		for i := h; i < n; i++ {
			//间隔h插入排序
			for j := i; j >= h && arr[j] < arr[j-h]; j -= h {
				swap(arr, j, j-h)
			}
		}
		h /= 3
	}
}
func swap(arr []int, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}
func main() {
	list := []int{8, 4, 8, 2, 9, 10, -2, -3, 20, 16, -4}
	ShellSort(list)
	fmt.Println(list)
}

go 归并排序
归并排序的操作步骤如下：

1. 首先将数组一份为二，分别为左数组和右数组
2. 若左数组的长度大于1，那么对左数组实施归并排序
3. 若右数组的长度大于1， 那么对右数组实施归并排序
4. 将左右数组进行合并

package main
//归并排序
import "fmt"

func mergeSort(arr []int, a, b int) {
	if b-a <= 1 {
		return
	}
	c := (a + b) / 2
	mergeSort(arr, a, c)
	mergeSort(arr, c, b)
	arrLeft := make([]int, c-a)
	arrRight := make([]int, b-c)
	copy(arrLeft, arr[a:c])
	copy(arrRight, arr[c:b])
	i := 0
	j := 0
	for k := a; k < b; k++ {
		if i >= c-a {
			arr[k] = arrRight[j]
			j++
		} else if j >= b-c {
			arr[k] = arrLeft[i]
			i++
		} else if arrLeft[i] < arrRight[j] {
			arr[k] = arrLeft[i]
			i++
		} else {
			arr[k] = arrRight[j]
			j++
		}
	}
}

func main() {
	list := []int{8, 4, 8, 2, 9, 10, -2, -3, 20, 16, -4}
	mergeSort(list, 0, len(list))
	fmt.Println(list)
}