go(插入排序)

package main

import "fmt"

//插入排序可以读取数据量比较大,内存装不下
func InserTest(arr []int) []int{
    backup := arr[2]
    j := 2-1
    for j>=0 && backup<arr[j]{
        arr[j+1]=arr[j]  //源数组中大的值往后移一位
        j--
    }
    arr[j+1]=backup
    return arr
}

//从左往右进行排序,左边一次存入较小的值
func InsertSort1(arr []int) []int{
    length := len(arr)
    if length <= 0{
        return arr
    }
    for i:=0;i<length-1;i++{
        fmt.Println("before:",arr)
        backup := arr[i+1]
        j := i
        for j >= 0 && backup < arr[j]{
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1]=backup
        fmt.Println("after:",arr)
    }
    return arr
}


//从左往右进行排序,左边一次存入较大的值
func InsertSort2(arr []int) []int{
    length := len(arr)
    if length <= 0{
        return arr
    }
    for i:=0;i<length-1;i++{
        fmt.Println("before:",arr)
        backup := arr[i+1]
        j := i
        for j >= 0 && backup > arr[j]{
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1]=backup
        fmt.Println("after:",arr)
    }
    return arr
}


//从右往左排序,右边一次存入较小的值
func InsertSort3(arr []int) []int{
    length := len(arr)
    if length <= 0{
        return arr
    }
    for i:=length-1;i>0;i--{
        fmt.Println(i,"before:",arr)
        backup := arr[i-1]
        j := i
        for j < length && backup < arr[j]{
           arr[j-1] = arr[j]
           j++
        }
        arr[j-1]=backup
        fmt.Println(i,"after:",arr)
    }
    return arr
}


//从右往左排序,右边一次存入较小的值
func InsertSort4(arr []int) []int{
    length := len(arr)
    if length <= 0{
        return arr
    }
    for i:=length-1;i>0;i--{
        fmt.Println(i,"before:",arr)
        backup := arr[i-1]
        j := i
        for j < length && backup > arr[j]{
            arr[j-1] = arr[j]
            j++
        }
        arr[j-1]=backup
        fmt.Println(i,"after:",arr)
    }
    return arr
}

func main(){
    arr := []int{0,1,19,11,29, 30, 2, 5, 45, 8, 234, 63, 12}
    //fmt.Println(InserTest(arr))
    fmt.Println(InsertSort4(arr))
}