常用排序

冒泡排序

思路分析：在要排序的切片中，对当前还未排好的序列，从前往后对相邻的两个元素依次进行比较和调整，让较大的数往下沉，较小的往上冒。即，每当两相邻的元素比较后发现它们的排序与排序要求相反时，就将它们互换。

package main

import (
	"fmt"
)

var sli = []int{1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39}

func bubbleSort(sli []int) []int {
	len := len(sli)
	//该层循环控制 需要冒泡的轮数
	for i := 1; i < len; i++ {
		//该层循环用来控制每轮 冒出一个数 需要比较的次数
		for j := 0; j < len-1; j++ {
			if sli[i] < sli[j] {
				sli[i], sli[j] = sli[j], sli[i]
			}
		}
	}
	return sli
}

func main() {
	res := bubbleSort(sli)
	fmt.Println(res)
}

---

选择排序

思路分析：在要排序的切片中，选出最小的一个元素与第一个位置的元素交换。然后在剩下的元素当中再找最小的与第二个位置的元素交换，如此循环到倒数第二个元素和最后一个元素比较为止。

package main

import (
	"fmt"
)

var sli = []int{1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39}

func selectSort(sli []int) []int {
	//双重循环完成，外层控制轮数，内层控制比较次数
	len := len(sli)
	for i := 0; i < len-1; i++ {
		//先假设最小的值的位置
		k := i
		for j := i + 1; j < len; j++ {
			//sli[k] 是当前已知的最小值
			if sli[k] > sli[j] {
				//比较，发现更小的,记录下最小值的位置；并且在下次比较时采用已知的最小值进行比较。
				k = j
			}
		}
		//已经确定了当前的最小值的位置，保存到 k 中。如果发现最小值的位置与当前假设的位置 i 不同，则位置互换即可。
		if k != i {
			sli[k], sli[i] = sli[i], sli[k]
		}
	}
	return sli
}

---

插入排序

思路分析：在要排序的一切片中，假设前面的元素已经是排好顺序的，现在要把第n个元素插到前面的有序切片中，使得这n个元素也是排好顺序的。如此反复循环，直到全部排好顺序。

package main

import (
	"fmt"
)

var sli = []int{1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39}

func insertSort(sli []int) []int {
	len := len(sli)
	for i := 0; i < len; i++ {
		tmp := sli[i]
		//内层循环控制，比较并插入
		for j := i - 1; j >= 0; j-- {
			if tmp < sli[j] {
				//发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
				sli[j+1], sli[j] = sli[j], tmp
			} else {
				//如果碰到不需要移动的元素，则前面的就不需要再次比较了。
				break
			}
		}
	}
	return sli
}

func main() {
	res := insertSort(sli)
	fmt.Println(res)
}

---

快速排序

思路分析：选择一个基准元素，通常选择第一个元素或者最后一个元素。通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。

package main

import (
	"fmt"
)

var sli = []int{1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39}

func quickSort(sli []int) []int {
	//先判断是否需要继续进行
	len := len(sli)
	if len <= 1 {
		return sli
	}
	//选择第一个元素作为基准
	base_num := sli[0]
	//遍历除了标尺外的所有元素，按照大小关系放入左右两个切片内
	//初始化左右两个切片
	left_sli := []int{}  //小于基准的
	right_sli := []int{} //小于基准的
	for i := 1; i < len; i++ {
		if base_num > sli[i] {
			//放入左边切片
			left_sli = append(left_sli, sli[i])
		} else {
			//放入右边切片
			right_sli = append(right_sli, sli[i])
		}
	}

	//再分别对左边和右边的切片进行相同的排序处理方式递归调用这个函数
	left_sli = quickSort(left_sli)
	right_sli = quickSort(right_sli)

	//合并
	left_sli = append(left_sli, base_num)
	return append(left_sli, right_sli...)
}
func main() {
	res := quickSort(sli)
	fmt.Println(res)
}