go排序算法快速实现

package main

import (
	"fmt"
)

// 快速排序
// 基本思路: 选取移动作为中心点, 然后把比他大的和比它小的分别放在left和right两边, 同时注意处理// 好和中心点相等的情况
func QuickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
	mData := arr[0]
	low := make([]int, 0, 0)
	high := make([]int, 0, 0)
	mid := make([]int, 0, 0)
	mid = append(mid, mData)
	for i := 1; i < len(arr); i++ {
		if arr[i] > mData {
			high = append(high, arr[i])
		}
		if arr[i] < mData {
			low = append(low, arr[i])
		}
		if arr[i] == mData {
			mid = append(mid, arr[i])
		}
	}
	low, high = QuickSort(low), QuickSort(high)
	newArr := append(append(low, mid...), high...)
	return newArr
}

// 使用快慢指针的实现方式, 效率更高
func QuickSort2(nums []int, l int, r int) {
	if l < r {
		mid := partition(nums, l, r)
		QuickSort(nums, l, mid-1)
		QuickSort(nums, mid+1, r)
	}
}

func partition(nums []int, l int, r int) int {
	key := nums[r]
	fast, slow := l, l
	for fast < r {
		if nums[fast] > key {
			nums[fast], nums[slow] = nums[slow], nums[fast]
			slow++
		}
		fast++
	}
	nums[slow], nums[r] = nums[r], nums[slow]
	return slow
}

// 冒泡排序
// 基本思路: 每次循环都把当次循环最大的值放到尾部, 每一轮的最大值像气泡一样不断地向某个方向移动
func BubbleSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
	for i := 0; i < len(arr); i++ {
		for j := i + 1; j < len(arr); j++ {
			if arr[i] > arr[j] {
				arr[i], arr[j] = arr[j], arr[i]
			}
		}
	}
	return arr
}

// 堆排序
// 基本思路: 找到最大的节点, 通过位置变换把它移动到堆顶
func HeapSortMax(arr []int, length int) []int {
	if len(arr) <= 1 {
		return arr
	}
	depth := length/2 - 1
	for i := depth; i >= 0; i-- {
		topMax := i
		leftChild := 2*i + 1
		rightChild := 2*i + 2
		if leftChild <= length-1 && arr[leftChild] > arr[topMax] {
			topMax = leftChild
		}
		if rightChild <= length-1 && arr[rightChild] > arr[topMax] {
			topMax = rightChild
		}
		if topMax != i {
			arr[i], arr[topMax] = arr[topMax], arr[i]
		}
	}
	return arr
}

// 每次把堆顶的节点后和本次循环倒数第i个节点交换
func HeapSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	}
	for i := 0; i < length; i++ {
		lastLen := length - i
		HeapSortMax(arr, lastLen)
		if i < length {
			arr[0], arr[lastLen-1] = arr[lastLen-1], arr[0]
		}
	}
	return arr
}

func main() {
	arr := []int{4, 6, 8, 1, 0, 2, 2, 4, 7, 9, 10, 34, 99, 0, 1, 4}
	fmt.Println(QuickSort(arr))

    arr2 := []int{4, 6, 8, 1, 0, 2, 2, 4, 7, 9, 10, 34, 99, 0, 1, 4}
	QuickSort2(arr2)
	fmt.Println(arr2)

	fmt.Println(BubbleSort(arr))

	fmt.Println(HeapSort(arr))
	fmt.Println(HeapSort([]int{1, 9}))
}