插入排序算法

插入排序算法

算法描述：插入算法，从第一个数开始进行循环，插入到一个已经排序的数组中
循环遍历所有元素，最终返回所有元素的排好的序列时间复杂度为 O(n^2).

算法步骤

• 选择一个数进行比较然后将比这个值小的元素插入这个值之前
• 循环向后查进行

错误总结

• 插入算法一定和冒泡算法区分开
• 插入算法是将需要的元素插入到当前元素之前
• 冒泡是两两交换将想要的元素置顶

package main

import (
    "fmt"
)

func main() {
    arrList := []int{1, 2, 8, 11, 3, 6, 8, 4, 9, 343, 3}
    arrList = standardInsertSort(arrList)
    fmt.Println(arrList)
}

func standardInsertSort(list []int) []int {
    resultList := []int{}
    length := len(list)
    i := 1
    resultList = append(resultList, list[0])
    for i < length {
        for j := 0; j < len(resultList); j++ {
            if list[i] <= resultList[j] {
                resultList = insertList(resultList, j, list[i])
                break
            }
            if j == len(resultList)-1 && list[i] > resultList[j] {
                resultList = insertList(resultList, j+1, list[i])
                break
            }
        }
        i++
    }
    return resultList
}
func insertList(list []int, i int, x int) []int {
    returnList := []int{}
    n := 0
    if i == len(list) {
        returnList = append(list, x)
        return returnList
    }
    for n < len(list) {
        if n < i {
            returnList = append(returnList, list[n])
        } else if n == i {
            returnList = append(returnList, x)
            returnList = append(returnList, list[n])
        } else {
            returnList = append(returnList, list[n])
        }
        n++
    }
    return returnList
}