插入排序算法

算法描述:插入算法,从第一个数开始进行循环,插入到一个已经排序的数组中
循环遍历所有元素,最终返回所有元素的排好的序列时间复杂度为 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
}
文档更新时间: 2020-07-22 17:13   作者:kuteng