插入排序

package mysort

type InsertionSort struct {
   Sort
   Binarysearch

}
//插入排序(Insertion Sort)
//插入排序非常类似于扑克牌的排序
//执行流程
//1 在执行过程中，插入排序会将序列分为2部分
//头部是已经排好序的，尾部是待排序的
//2 从头开始扫描每一个元素
//每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序
func (this *InsertionSort) SortFunc() {
   this.SortFunc2()

}
//
func (this *InsertionSort) SortFunc0() {
   for begin := 1; begin < len(this.Array); begin++ {
      // 找合适的位置然后将数放进去
      current := begin
      for current > 0 {
         if this.ComWithIndex(current,current -1) < 0 {
            this.Swap(current,current-1)
         }
         current --
      }
   }
}
// 优化 将交换改为挪动
// 先将代插入的元素备份，然后挪动比其大的元素
// 将待插入的元素放到这个位置
func (this *InsertionSort) SortFunc1() {
   for begin := 1; begin < len(this.Array); begin++ {
      // 找合适的位置然后将数放进去
      current := begin
      beginV := this.Array[begin]
      for current > 0 && this.ComWithValue(beginV,this.Array[current -1])< 0{
         this.Array[current]=this.Array[current -1]
         current --
      }
      this.Array[current] = beginV

   }
}
// 使用二分查找
func (this *InsertionSort) SortFunc2() {
   for begin := 1; begin < len(this.Array); begin++ {
      // 找合适的位置然后将数放进去
      beginV := this.Array[begin]
      this.Data = this.Array
      index := this.Find(begin)
      for i := begin; i > index ; i-- {
         this.Array[i]=this.Array[i -1]
      }
      this.Array[index] = beginV

   }
}