go-数据结构[11]-直接插入排序

具体算法描述

设有一组关键字{K1, K2,…, Kn};排序开始就认为 K1 是一个有序序列;让 K2 插入上述表长为 1 的有序序列,使之成为一个表长为 2 的有序序列;然后让 K3 插入上述表长为 2 的有序序列,使之成为一个表长为 3 的有序序列;依次类推,最后让 Kn 插入上述表长为 n-1 的有序序列,得一个表长为 n 的有序序列。

具体算法描述如下:

从第一个元素开始,该元素可以认为已经被排序
取出下一个元素,在已经排序的元素序列中从后向前扫描
如果该元素(已排序)大于新元素,将该元素移到下一位置
重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤 2~5
如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。

二分查找法,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

实例分析

现有一组数组 arr = [5, 6, 3, 1, 8, 7, 2, 4],共有八个记录,排序过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[5]   6   3   1   8   7   2   4
↑ │
└───┘
[5, 6] 3 1 8 7 2 4
↑ │
└────────┘
[3, 5, 6] 1 8 7 2 4
↑ │
└──────────┘
[1, 3, 5, 6] 8 7 2 4
↑ │
└──┘
[1, 3, 5, 6, 8] 7 2 4
↑ │
└────┘
[1, 3, 5, 6, 7, 8] 2 4
↑ │
└────────────────┘
[1, 2, 3, 5, 6, 7, 8] 4
↑ │
└─────────────┘

[1, 2, 3, 4, 5, 6, 7, 8]

动画演示

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
package main

import "fmt"
//打印
func print(arr []int){

for _,data := range arr{
fmt.Printf("%d ",data)
}

fmt.Println()
}

func main(){

arr:= []int{8, 5, 2, 6, 9, 3, 1, 4, 0, 7}
//arr:=[]int{1,3,2,4,9,2,6,5,4,8}
print(arr)

insertsort2(arr)

print(arr)
}

// 插入排序
func insertsort(arr []int){

//print(arr)
length := len(arr)

for i:= 1;i<length;i++{
temp := arr[i]
index:=i
for j:= i-1;j>=0;j--{
if arr[j] >temp{
arr[j+1] = arr[j]
}else{
break
}
index--
}
arr[index] = temp
}
}

//推荐
func insertsort2(arr []int){

//print(arr)
length := len(arr)

for i:= 1;i<length;i++{
temp := arr[i]
j:=i-1

for j>=0 && arr[j] > temp{
arr[j+1] = arr[j]
j--
}
arr[j+1] = temp
}
}

JavaScript 语言实现

直接插入排序 JavaScript 实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function insertionSort(array) {
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
var length = array.length,
i,
j;
for (i = 1; i < length; i++) {
for (j = i; j > 0; j--) {
if (array[j - 1] > array[j]) {
swap(array, j - 1, j);
} else {
break;
}
}
}
return array;
}

下面这种方式可以减少交换次数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function insertionSort(array) {
var length = array.length,
i,
j,
temp;
for (i = 1; i < length; i++) {
temp = array[i];
for (j = i; j >= 0; j--) {
if (array[j - 1] > temp) {
array[j] = array[j - 1];
} else {
array[j] = temp;
break;
}
}
}
return array;
}

利用二分查找法实现的插入排序,二分查找排序:

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
function insertionSort2(array) {
function binarySearch(array, start, end, temp) {
var middle;
while (start <= end) {
middle = Math.floor((start + end) / 2);
if (array[middle] < temp) {
if (temp <= array[middle + 1]) {
return middle + 1;
} else {
start = middle + 1;
}
} else {
if (end === 0) {
return 0;
} else {
end = middle;
}
}
}
}
function binarySort(array) {
var length = array.length,
i,
j,
k,
temp;
for (i = 1; i < length; i++) {
temp = array[i];
if (array[i - 1] <= temp) {
k = i;
} else {
k = binarySearch(array, 0, i - 1, temp);
for (j = i; j > k; j--) {
array[j] = array[j - 1];
}
}
array[k] = temp;
}
return array;
}
return binarySort(array);
}

资料