-
Notifications
You must be signed in to change notification settings - Fork 44
/
InsertSort.go
69 lines (64 loc) · 1.62 KB
/
InsertSort.go
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
57
58
59
60
61
62
63
64
65
66
67
68
69
// InsertSort
/*
------------------------------------------------------
作者 : Black Ghost
日期 : 2019-03-05
版本 : 0.0.0
------------------------------------------------------
插入排序法
理论:
时间复杂度: O(n^2)
最好情况 : O(n)
最坏情况 : O(n^2)
空间复杂度: O(1)
稳定性 : 不稳定
------------------------------------------------------
输入 :
in 输入矩阵, 1xn
输出 :
sol 排序结果
err 解出标志:false-未解出或达到步数上限;
true-全部解出
------------------------------------------------------
*/
package goNum
// InsertSort 插入排序法
func InsertSort(in Matrix) (Matrix, bool) {
/*
插入排序法
输入 :
in 输入矩阵, 1xn
输出 :
sol 排序结果
err 解出标志:false-未解出或达到步数上限;
true-全部解出
*/
//判断初值维数
if in.Rows != 1 {
panic("Error in goNum.InsertSort: Input Matrix error")
}
if in.Columns < 1 {
panic("Error in goNum.InsertSort: Empty input Matrix")
} else if in.Columns == 1 {
return in, true
}
n := in.Columns
sol := ZeroMatrix(1, n)
var err bool = false
//初始化sol
for i := 0; i < n; i++ {
sol.Data[i] = in.Data[i]
}
//排序开始
for i := 1; i < n; i++ {
index := i - 1
min := sol.Data[i]
for (index >= 0) && (sol.Data[index] > min) {
sol.Data[index+1] = sol.Data[index]
index--
}
sol.Data[index+1] = min
}
err = true
return sol, err
}