排序算法

1. 冒泡排序

/**
* 冒泡排序
 */
func BubbleSort(slice []int) {
	n := len(slice)            //切片长度
	for i := 0; i < n-1; i++ { //冒泡最多n-1轮
		exchange := false
		for j := 0; j < n-1-i; j++ { //每一轮冒泡
			if slice[j] > slice[j+1] { //调换位置
				slice[j], slice[j+1] = slice[j+1], slice[j]
				exchange = true
			}
		}
		if !exchange { //没有发生位置调换，已是有序，可提前退出
			break
		}
	}
}

2. 选择排序

/**
* 选择排序
 */
func SelectSort(slice []int) {
	n := len(slice)
	for i := 0; i < n-1; i++ {
		pos := i
		for j := i + 1; j < n; j++ {
			if slice[j] < slice[pos] {
				pos = j //记录最小数位置
			}
		}
		if pos != i { //调换位置
			slice[i], slice[pos] = slice[pos], slice[i]
		}
	}
}

3. 插入排序

/**
* 插入排序
 */
func InsertSort(slice []int) {
	n := len(slice)
	for i := 1; i < n; i++ {
		for j := i; j > 0; j-- { //从后往前比较，边比较边移位，直至找到插入位置
			if slice[j] < slice[j-1] { //调换位置
				slice[j-1], slice[j] = slice[j], slice[j-1]
			} else { //已找到插入位置，进入下一个待排序元素的插入
				break
			}
		}
	}
}

4. 希尔排序

算法原理理解：https://blog.csdn.net/qq_39207948/article/details/80006224

/**
* 希尔排序：对插入排序的优化，适用于大量数据排序
*/
func ShellSort(slice []int) {
	n := len(slice)
	for add := n / 2; add > 0; add /= 2 { //增量控制
		for i := add; i < n; i++ {
			for j := i; j >= add; j -= add {
				if slice[j] < slice[j-add] {
					slice[j-add], slice[j] = slice[j], slice[j-add]
				} else {
					break
				}
			}
		}
	}
}

5. 堆排序

算法原理理解：https://www.cnblogs.com/Java3y/p/8639937.html

/**
* 堆排序：利用堆进行选择排序
 */
func HeapSort(slice []int) {
	n := len(slice)
	//建堆
	for root := n / 2; root >= 0; root-- {
		Heapify(slice, root)
	}
	//排序
	for i := n; i > 1; i-- {
		slice[0], slice[i-1] = slice[i-1], slice[0]
		Heapify(slice[:i-1], 0)
	}
}

//堆调整
func Heapify(slice []int, root int) {
	n := len(slice)
	left := root*2 + 1
	right := root*2 + 2
	max := root
	if left < n && slice[max] < slice[left] {
		max = left
	}
	if right < n && slice[max] < slice[right] {
		max = right
	}
	if max != root {
		slice[root], slice[max] = slice[max], slice[root]
		Heapify(slice, max)
	}
}

6. 归并排序

算法原理理解：https://www.jianshu.com/p/33cffa1ce613

/**
* 归并排序
 */
func MergeSort(slice []int) {
	n := len(slice)
	if n == 1 {
		return
	}
	mid := n / 2
	MergeSort(slice[:mid])
	MergeSort(slice[mid:n])
	p1, p2 := 0, mid
	var newSlice []int
	for p1 < mid && p2 < n {
		if slice[p1] < slice[p2] {
			newSlice = append(newSlice, slice[p1])
			p1++
		} else {
			newSlice = append(newSlice, slice[p2])
			p2++
		}
	}
	if p1 < mid {
		for p1 < mid {
			newSlice = append(newSlice, slice[p1])
			p1++
		}
	}
	if p2 < n {
		for p2 < n {
			newSlice = append(newSlice, slice[p2])
			p2++
		}
	}
	for k, v := range newSlice {
		slice[k] = v
	}
}

7. 快速排序

func QuickSort(slice []int, start, end int) {
	if start >= end {
		return
	}
	i, j := start, end
	val := slice[(start+end)/2]
	for i <= j {
		for i <= end && slice[i] < val {
			i++
		}
		for j >= start && slice[j] > val {
			j--
		}
		if i <= j {
			slice[i], slice[j] = slice[j], slice[i]
			i++
			j--
		}
	}
	if start < j {
		QuickSort(slice, start, j)
	}
	if i < end {
		QuickSort(slice, i, end)
	}
}