直接插入排序
直接插入排序是简单排序中性能最好的
平均时间复杂度:O(n^n / 4)
最好时间复杂度:O(n)
最坏时间复杂度:O(n^n)
直接插入排序版本1
思路:将每次要插入的当前元素依次与左边元素比较,如果左边元素大于当前元素则交换,直到左边元素小于等于当前元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| package main
import ( "log" "math/rand" "time" )
func InsertSort(nums []int) []int { insertSort(nums) return nums }
func insertSort(nums []int) { 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)) }
|
直接插入排序版本2
摘自<<大话数据结构>>
思路:将前面比要插入元素大的元素挪到后面,找到插入位置之后将要插入元素插入即可,最后找到的插入位置一定是j+1而不是j因为我们判断了nums[j]小于等于我们要插入的元素
注意:此时要记得将temp放置到正确位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| package main
import ( "log" "math/rand" "time" )
func InsertSortV2(nums []int) []int { insertSortV2(nums) return nums }
func insertSortV2(nums []int) { for i := 1; i < len(nums); i++ { if nums[i] < nums[i-1] { temp := nums[i] j := i-1 for ; j >= 0 && nums[j] > temp ; j-- { nums[j+1] = nums[j] } nums[j+1] = temp } } }
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(InsertSortV2(nums)) }
|