直接插入排序

直接插入排序是简单排序中性能最好的

平均时间复杂度: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"
)

/**
* @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))
}

直接插入排序版本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"
)

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

func InsertSortV2(nums []int) []int {
insertSortV2(nums)
return nums
}

//大话数据结构书上的直接插入排序
func insertSortV2(nums []int) {
//默认下标为0的已经有序,因此从下标为1的开始插入
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]
}
//此时要记得将temp放置到正确位置
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))
}

评论