Golang实现经典排序算法【二】— 堆排序、归并排序、快速排序_go实现分类算法

Golang实现经典排序算法【二】

实现堆排序、归并排序、快速排序

堆排序

堆排序是简单选择排序的升级，首先构建大顶堆，然后交换堆顶，最后依次旋转。
平均复杂度：O(nlogn) , 稳定性：不稳定

func main() {
	s := []int{1, 44, 4, 6, 74, 42, 346, 536, 453, 0, 0, 1, 1, 32, 3}
	fmt.Println(heapSort(s))
}
/*堆排序 大顶堆*/
func heapSort(s []int) []int {
	length := len(s)

	// 首先构建堆，从右下开始
	for i := length / 2; i >= 0; i-- {
		heapAdjust(s, i, length-1)
	}

	// 交换并旋转构建
	for i := length - 1; i > 0; i-- {
		s[0], s[i] = s[i], s[0]
		heapAdjust(s, 0, i-1)
	}
	return s
}

// 构建与旋转
func heapAdjustBH(s []int, start, end int) {
	tmp := s[start]
	var j int
	for j = start * 2; j <= end; j *= 2 {
		/* 完全二叉树的性质中，s[i]为当前节点，则s[2*i]为左子节点，s[2*i+1]为右子节点 */
		if j < end && s[j] < s[j+1] {
			j++ // j定位较大的数——s[2*i]或者s[2*i+1]
		}
		// 如果上面if执行了，那么此刻s[j]就是右子树，而且是比左子树大的

		if tmp >= s[j] { //结束旋转的条件
			break
		}

		s[start] = s[j] // 控制start为当前最大值
		start = j
	}
	s[start] = tmp 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

归并排序

平均复杂度：O(nlogn) , 稳定性：稳定

递归版本

func main() {
	s1 := []int{1, 44, 4, 6, 74, 42, 346, 536, 453, 0, 0, 0, 1, 1, 32, 3}
	fmt.Println(mergeSort_Go(s1))
	s := []int{1, 44, 4, 6, 74, 42, 346, 536, 453, 0, 0, 0, 1, 1, 32, 3}
	fmt.Println(mergeSort_loop(s))
}

/*归并排序 递归*/
func mergeSort_Go(s []int) []int {
	mergeControl(s, 0, len(s)-1)
	return s
}

func mergeControl(s []int, f, d int) {

	if f == d {
		return
	}
	// 折半处理
	mergeControl(s, f, (f+d)/2)
	mergeControl(s, (f+d)/2+1, d)
	
	mergeGo(s, f, (f+d)/2, d)
}

func mergeGo(S []int, start, mid, end int) {
	var j int = mid + 1
	T := []int{} // 利用这部分空间暂时储存结果
	var ss = start
	for start <= mid && j <= end {
		//start与j交替等待
		if S[start] < S[j] {
			T = append(T, S[start])
			start++
		} else {
			T = append(T, S[j])
			j++
		}
	}

	if start <= mid { 
		T = append(T, S[start:mid+1]...)
	}
	if j <= end { 
		T = append(T, S[j:end+1]...)
	}

	for i, j := range T {
		S[ss+i] = j
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

迭代版本

/* 循环实现 */
func mergeSort_loop(s []int) []int {
	length := len(s)
	k := 1

	for k < length {
		mergeLoopPass(s, k, length-1)
		k *= 2
	}
	return s
}

func mergeLoopPass(s []int, step, end int) {
	var i int = 0
	for i <= end+1-2*step { // end >= i-1+2*step
		mergeGo(s, i, i+step-1, i-1+2*step) 
		i = i + 2*step          
	}
	// 剩下的不足以构成段，比如，要4个4个（共8个）一组的，但只剩下0--7个数
	if end > i-1+step {
		mergeGo(s, i, i+step-1, end)
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

快速排序

快速排序是冒泡排序的升级。
平均复杂度：O(nlogn) , 稳定性：不稳定

递归版本

/*递归一版*/
func quickSort1(arr []int, left, right int) {
	if left < right {
		pivot := arr[right]
		j := left - 1 //j为标记，标记i的前面，扫描到比pivot小的就往前交换
		// i是遍历指针 j是定位指针
		for i := left; i < right; i++ {
			if arr[i] < pivot {
				j++             
				arr[j], arr[i] = arr[i], arr[j] //交换
			}
		}
		// 循环结束j<i=right
		arr[right], arr[j+1] = arr[j+1], arr[right] //把pivot交换到定位的j的下一位
		j += 1                                      //基于当前[right]的pivot已经完成了，a[j+1]之前就比它小，后面就比它大
		quickSort1(arr, left, j-1)
		quickSort1(arr, j+1, right)
	}
}

/*递归二版*/
func quickSort2(arr []int, start, end int) {
	if start < end {
		i, j := start, end
		key := arr[(start+end)/2]
		for i <= j {
			for arr[i] < key {
				i++
			}
			for arr[j] > key {
				j--
			}
			if i <= j {
				arr[i], arr[j] = arr[j], arr[i]
				i++
				j--
			}
		}

		if start < j {
			quickSort2(arr, start, j)
		}
		if end > i {
			quickSort2(arr, i, end)
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

迭代版本

func main() {
	s := []int{1, 44, 4, 6, 74, 42, 346, 536, 453, 0, 0, 0, 1, 1, 32, 3}
	s1 := []int{1, 44, 4, 6, 74, 42, 346, 536, 453, 0, 0, 0, 1, 1, 32, 3}
	s3 := []int{1, 44, 4, 6, 74, 42, 346, 536, 453, 0, 0, 0, 1, 1, 32, 3}

	fmt.Println(s)
	
	quickSort2(s1, 0, len(s)-1)
	fmt.Println(s1)
	quickSortLoop(s3)
	fmt.Println(s3)
}


/* 使用循环实现（借助栈） */
func quickSortLoop(s []int) {
	length := len(s)
	var i, j int
	stack := []int{0, length - 1}
	for len(stack) > 0 {
		i = stack[len(stack)-1]
		j = stack[len(stack)-2]
		stack = stack[:len(stack)-2]
		d := doPivot(s, j, i)
		if d-1 > j {
			stack = append(stack, j, d-1)
		}
		if d+1 < i {
			stack = append(stack, d+1, i)
		}
	}
}

func doPivot(s []int, start, end int) int {
	var p = s[start] // 用第一个数作为枢轴

	for start < end {
		for start < end && s[end] > p {
			end--
		}
		s[start] = s[end]  //覆盖而不是交换，优化了不必要的交换
		
		for start < end && s[start] <= p {
			start++
		}
		s[end] = s[start]
		
	}
	s[start] = p
	return start
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

优化

快速排序的优化思路：

1. 优化选取的枢轴，在mid，start，end间使用随机选取
2. 优化小数组时候的排序方案，少量数据可以使用直接插入排序
3. 优化递归操作，将两次递归优化为一次递归.

   /* 尾递归 优化 */
   func quickSort3(s []int, low, high int) []int {
   	var pviot int
   	if high-low > MAX_LENGTH {
   		for low < high {
   			pviot = doPivot(s, low, high)
   			quickSort3(s, low, pviot-1)
   			low = pviot+1
   		}
   	} else {
   		insertSort(s)
   	}
   
   	return s
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15

总结

• 简单算法：冒泡、简单选择、直接插入
• 改进算法：希尔、堆、归并、快速

从平均情况来看，后 3 种改进算法要胜过希尔排序，也胜过前 3 种简单算法。

从最好情况看，反而冒泡和直接插入排序要好一些，如果待排序序列总是基本有序，反而不应该考虑 4 种复杂的改进算法。

从最坏情况看，堆排序与归并排序又强过快速排序以及其他简单排序。

补充

heap在标准包的使用

/* go中heap包的方法 go的标准库 container/heap */
/*
	h := &IntHeap{3, 8, 6}  // 创建IntHeap类型的原始数据
	func Init(h Interface)  // 对heap进行初始化，生成小根堆（或大根堆）
	func Push(h Interface, x interface{})  // 往堆里面插入内容
	func Pop(h Interface) interface{}  // 从堆顶pop出内容
	func Remove(h Interface, i int) interface{}  // 从指定位置删除数据，并返回删除的数据
	func Fix(h Interface, i int)  // 从i位置数据发生改变后，对堆再平衡，优先级队列使用到了该方法
*/
1
2
3
4
5
6
7
8
9

实现了swap接口就可以使用heap的方法

sort包中的快速排序实现

func quickSort(data Interface, a, b, maxDepth int) {
	for b-a > 12 { // Use ShellSort for slices <= 12 elements
		if maxDepth == 0 {
			heapSort(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivot(data, a, b)
		// Avoiding recursion on the larger subproblem guarantees
		// a stack depth of at most lg(b-a).
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		// Do ShellSort pass with gap 6
		// It could be written in this simplified form cause b-a <= 12
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		insertionSort(data, a, b)
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29