package main

import (
	"log"
	"math/rand"
	"time"
)

/**
 * @Author: yirufeng
 * @Email: yirufeng@foxmail.com
 * @Date: 2020/9/10 9:12 上午
 * @Desc: 直接插入排序
 */

func InsertSort(nums []int) []int {
	insertSort(nums)
	return nums
}

//思路：如果当前元素比前一个元素小就交换，一直到当前元素大于等于前一个元素
func insertSort(nums []int) {
	//默认下标为0的已经有序，因此从下标为1的开始插入
	for i := 1; i < len(nums); i++ {
		//插入条件：要排序的元素一定要小于前面的元素
		if nums[i] < nums[i-1] {
			//什么时候结束插入：当要插入的元素的值大于等于前面的那个元素就停止插入
			for j := i; j >= 1 && nums[j] < nums[j-1]; j-- {
				nums[j], nums[j-1] = nums[j-1], nums[j]
			}
		}
	}
}


//写一个随机数生成器
func RandArray(length int) []int {
	nums := []int{}
	for i := 0; i < length; i++ {
		r := rand.New(rand.NewSource(time.Now().UnixNano()))
		nums = append(nums, r.Intn(100))
	}
	return nums
}

func main() {
	rand.Seed(time.Now().UnixNano())
	nums := RandArray(30)
	log.Println(nums)
	log.Println(InsertSort(nums))
}