这里记录了几种常用、基础的排序算法， 包括： 冒泡排序、插入排序、选择排序
冒泡排序
冒泡排序 算法的原理：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
时间复杂度： O(n^2) 、空间复杂度 O(1) 。
冒泡排序是稳定排序算法（不会改变元素的相对位置）。
示例代码 1：
func bubbleSort(s []int) {
n := len(s)
if n < 2 {
return
}
for i := 0; i < n; i++ {
for j := 1; j < n; j++ {
if s[j-1] > s[j] {
s[j-1], s[j] = s[j], s[j-1]
}
}
}
}
示例代码 2：
和上面的基本相同， 不过上面的代码稍微有点傻， 无论数据是否已经有序， 它都会将所有元素遍历 n * n 遍， 下面的方法加了一个 flag， 当它知道数据已经是有序的了， 就不会再遍历，将退出循环。 假设传入的数据是一个已经排序好的数据， 那它就只会遍历一遍数据， 复杂度就会降低到 O(n) 。
func bubbleSort(s []int) {
n := len(s)
if n < 2 {
return
}
for i := 0; i < n; i++ {
flag := true // 每次外层循环开始时， 我们都假装数据是已经有序
for j := 1; j < n; j++ {
if s[j-1] > s[j] {
s[j-1], s[j] = s[j], s[j-1]
// 如果移动过元素， 就证明数据还不是有序的， 标记
flag = false
}
}
// 内存循环结束时判断下，是否移动过数据， 如果一次没移动过， 就结束整个循环
if flag {
break
}
}
}
插入排序
插入排序 算法原理：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
插入排序是稳定排序算法。
示例代码：
插入排序也是很简单的， 比冒泡稍微难理解一点， 已经在代码中添加了注释
// 这里的排序结果是从小到大排序
func insertionSort(s []int) {
n := len(s)
if n <= 1 {
return
}
// 从第一个元素开始拿出， 假设第一个元素就是有序的了
// 以后 i 前面的都是有序的
for i := 1; i < n; i++ {
// 拿出第 i 个元素, 记录到临时变量， 否则移动后就找不到了
temp := s[i]
// 拿 temp 和 i 前面的已经有序的元素进行比较
j := i
for ; j > 0 && temp < s[j-1]; j-- {
// 如果 temp 比它前面的元素小， 它前面的元素就要向右移动一位
// 最终留出需要插入的位置
s[j] = s[j-1]
}
// 已经腾出位置了， 可以将元素插入（因为上个循环退出的时候还是执行一次 -- 操作）
s[j] = temp
}
}
选择排序
选择排序 原理：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
选择排序不是稳定排序算法（因为交换位置的时候会改变元素的相对位置）
示例代码 1：
func slelectionSort(s []int) {
n := len(s)
if n < 2 {
return
}
// 遍历所有元素
for i := 0; i < n-1; i++ {
// 用后面所有位置和 第 i 个元素进行比较， 如果比 i 小， 进行交换
// 第 1 次 s[0] 和后面比较， 交换完成后 s[0]， 就是最小的了， 索引+1
// 第 2 次 s[1] 和后面比较 ……
// 直到最后一个结束
for j := i + 1; j < n; j++ {
if s[j] < s[i] {
s[j], s[i] = s[i], s[j]
}
}
}
}
示例代码 2：
和示例 1 基本相同， 不过在比较的时候只记录最小值的下标， 这样可以减少交换元素的次数
func slelectionSort(s []int) {
n := len(s)
if n < 2 {
return
}
// 遍历所有元素
for i := 0; i < n-1; i++ {
// 记录一个最小值的坐标， 第一次是 0， 第二次是 1 ……
min := i
for j := i + 1; j < n; j++ {
if s[j] < s[min] {
min = j
}
}
// 全部遍历完再进行数据的替换
s[i], s[min] = s[min], s[i]
}
}