实现堆排序、归并排序、快速排序
堆排序
堆排序是简单选择排序的升级，首先构建大顶堆，然后交换堆顶，最后依次旋转。
平均复杂度：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
}
归并排序
平均复杂度：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
}
}
迭代版本
/* 循环实现 */
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)
}
}
快速排序
快速排序是冒泡排序的升级。
平均复杂度：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)
}
}
}
迭代版本
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
}
优化
快速排序的优化思路：
/* 尾递归 优化 */
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
}
总结
- 简单算法：冒泡、简单选择、直接插入
- 改进算法：希尔、堆、归并、快速
从平均情况来看，后 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位置数据发生改变后，对堆再平衡，优先级队列使用到了该方法
*/
实现了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)
}
}