go-数据结构[13]-二分插入排序

二分插入排序 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
70
package main

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

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

fmt.Println()
}

func main(){

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

binarysort(arr)

print(arr)
}

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

//print(arr)
length := len(arr)
for i:= 1;i<length;i++{

tmp:= arr[i]
j:= i-1
if arr[j] > arr[i]{
index:= binarysearch(arr,0,i-1,arr[i])

for k:= i-1;k>=index;k--{
arr[k+1] =arr[k]
}
arr[index] = tmp
}
}
}


func binarysearch(arr []int, low int, high int, data int) int{

for low <=high{

mid:= low + (high-low)/2

if data > arr[mid]{

if mid+1< len(arr) && data <=arr[mid+1]{
return mid+1
}else{
low = mid + 1
}
}else{
if mid == 0{
return 0
}else{
high = mid - 1
}
}
}

return 0

}

JavaScript实现

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);
}