十大排序算法

算法名称	英文名	最大时间复杂度	稳定状态
选择排序	selection	n*n	不稳
冒泡排序	bubble		稳
插入排序	insertion		稳定
堆排序	heap
希尔排序	shell
归并排序	merge
快速排序	Quick
桶排序	bucket
计数排序	counting
基数排序	Radix

1. 选择排序

依次找出最大或最小的数

伪代码

for i=0 to A.length-1{
	minIndex = i;
	for j=i+1 to A.length-1{
		if(A[minIndex] > A[j]){
			minIndex = j;
		}
	}
	temp = A[i];
	A[i] = A[minIndex]
	A[minIndex] = temp
}

//description
// 从第一个数开始，找出数列中最小或最大的数交换他们的位置 具体算法描述如下：

// 1. 记录最值的位置；
// 2. 交换位置

func main() {
	disordered := [10]int{11, 7, 2, 5, 8, 1, 9, 4, 6, 3}
	// fmt.Println(disordered)
	for k := 0; k < len(disordered)-1; k++ {
		var minPos = k
		// 找到最值下标
		for i := k + 1; i < len(disordered); i++ {
			if disordered[minPos] > disordered[i] {
				minPos = i
			}
		}
		//值交换
		var temp = disordered[k]
		disordered[k] = disordered[minPos]
		disordered[minPos] = temp

		fmt.Println(disordered)
	}
}

2.冒泡排序

描述：循环遍历元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。

//description
// 每次遍历都会找到最大的剩余项中的最大项 具体算法描述如下：

// 1. 比较相邻俩元素大小；
// 2. 交换位置
// 3. 排除已拍好的元素
func main() {
	disordered := [10]int{11, 7, 2, 5, 8, 1, 9, 4, 6, 3}
	for j := 0; j < len(disordered)-1; j++ {
		for i := 0; i < len(disordered)-1-j; i++ {
			var temp = disordered[i]
			if disordered[i] > disordered[i+1] {
				disordered[i] = disordered[i+1]
				disordered[i+1] = temp
			}
		}
		fmt.Println(disordered)
	}
}

3.插入排序

描述：从第二个数开始，往前比较，按大小交换循序，

伪代码

for j=2 to A.length:
	key=A[j]
	i = j-1
	while i>0 and A[i] > key:
		A[i+1] = A[i]
		i--
	A[i+1] = key

func main() {
	disordered := [10]int{11, 7, 2, 5, 8, 1, 9, 4, 6, 3}
	for i := 1; i <= len(disordered)-1; i++ {
		// var minPos = i
		for j := i; j > 0 && disordered[j-1] > disordered[j]; j-- {
			var temp = disordered[j]
			disordered[j] = disordered[j-1]
			disordered[j-1] = temp
		}
		fmt.Println(disordered)
	}
}

4.堆排序

描述：堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

参考链接

package main

import "fmt"

func main() {
	// disordered := []int{11, 7, 2, 5, 8, 1, 9, 4, 6, 3}
	disordered := []int{10, 2, 3, 4, 5, 6, 7, 8, 9, 1}
	//将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点
	for i := len(disordered)/2 - 1; i >= 0; i-- {
		bigTopHeap(disordered, i, len(disordered))
	}
	//将其与末尾元素进行交换，此时末尾就为最大值
	for j := len(disordered) - 1; j > 0; j-- {
		swap(disordered, 0, j)
		bigTopHeap(disordered, 0, j)
	}
	fmt.Println(disordered)
}

//大顶堆
func bigTopHeap(arr []int, i int, length int) {
	//父节点
	var temp = arr[i]
	for j := i*2 + 1; j < length; j = j*2 + 1 { //从i结点的左子结点开始，也就是2i+1处开始
		if j+1 < length && arr[j] < arr[j+1] { //如果左子结点小于右子结点，k指向右子结点
			j++
		}
		if arr[j] > temp { //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
			arr[i] = arr[j]
			i = j
		}
	}
	arr[i] = temp
}

//小顶堆
func smallTopHeap(arr []int, i int, length int) {
	//父节点
	var temp = arr[i]
	for j := i*2 + 1; j < length; j = j*2 + 1 {
		if j+1 < length && arr[j] > arr[j+1] {
			j++
		}
		if arr[j] < temp { //
			arr[i] = arr[j]
			i = j
		}
	}
	arr[i] = temp
}

//值交换
func swap(arr []int, i int, j int) {
	var temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp
}