冒泡，选择，插入排序

//冒泡排序
//从小到大排序
func bubbleSort(arr []int) {
    m := len(arr)
    //m-1趟
    for i := 0; i < m-1; i ++ {
        //每一趟比较的次数 m - 1 - i 表示需要比较的次数
        for j := 0; j < m - 1 - i; j ++ {
            //左边比右边大 需要交换
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

冒泡排序的时间复杂度是 O(n^2)

//选择排序
//算法思想：每次选择除当前元素之外最小的元素替换当前元素，使得最后从小到大排序
//怎么选择？用下标 如果之后元素小于当前元素更新下标，交换
func selectSort(arr []int) {
    var index int
    for i := 0; i < len(arr)-1; i ++ {
        //保存当前元素的下标
        index = i
        //从之后的元素选择最小的元素进行交换
        for j := i+1; j < len(arr); j ++ {
            if arr[j] < arr[index] {
                //如果下标为j的值 小  保存下标j
                index = j
            }
        }
        //交换下标i和index (j) 的值
        arr[i], arr[index] = arr[index], arr[i]
    }
}

选择排序的时间复杂度是 O(n^2)

//插入排序
//算法思想：遍历数组，将数组中的每个元素插入到正确的位置
//所以直接从第二个元素开始，先备份当前值，然后不断和之前的元素值进行比较，如果小于，将其右移动，直到插入正确的位置
for insertionSort(arr []int) {
    for i := 1; i < len(arr); i ++ {
        //备份当前值
    temp := arr[i]
    //移动左边 比当前元素大的
    j := i - 1
    for ;j >= 0 && arr[j] > temp; j -- {
        arr[j + 1] = arr[j]
    }
    //插入该元素
    arr[j+1] = temp
    }
}

插入排序的时间复杂度是 O(n^2)

//希尔排序
//算法思想：首先它把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高
func shellSort(arr []int) {
    m := len(arr)
    //进行分组，一开始为数组的一半,之后每次减半
    for gap:=m/2; gap>0; gap /= 2 {
        //对一个分组进行排序
        for i:=gap; i<m; i++ {
            insertRightPosition(arr, gap, i)
        }
    }
}

func insertRightPosition(arr []int, gap, i int) {
    //类似于插入排序
    inserted := arr[i]
    j := i-gap
    for ;j>=0 && arr[j]>inserted; j -= gap {
        arr[j+gap] = arr[j]
    }
    //这时候的 j+gap 下标的元素是 左边的元素
    arr[j+gap] = inserted
}

func insertSort(nums []int) []int {
	for i := 1; i < len(nums); i ++ {
		// 保留当前值
		tmp := arr[i]
		// 和前面的值比较，插入正确的位置
		j := i - 1
		for ;j >= 0 && nums[j] > tmp; j -- {
			nums[j + 1] = nums[j]
		}
		nums[j + 1] = tmp
	}
}