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

二分插入排序 go实现

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实现

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