算法-插入排序.md

插入排序

简介

如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法。

插入排序是一种稳定的内部排序算法。

稳定排序:若在待排序的记录中，存在两个或两个以上的关键码值相等的记录，经排序后这些记录的相对次序仍然保持不变，则称相应的排序方法是稳定的方法，否则是不稳定的方法。

适用范围

少量数据的排序

复杂度

O(n^2)

实现

在代码实现中，需要注意的是，A[i]>key 条件代表的是当前关键值大于待排序值，反过来想就是，如果待排序值大于前面的所有值，那么说明待排序值暂时不需要移动。

每趟循环过后，从 0-i 之间的序列一定是已经排序好的。

go 实现

type InsertionSort struct {
	Value []int
}

func (s *InsertionSort) Sort() ([]int, error) {
	if len(s.Value) <= 1 {
		return s.Value, nil
	}
	for i := 1; i < len(s.Value); i++ {
		t, j := s.Value[i], i
		for ; j >= 1 && s.Value[j-1] > t; j-- {
			s.Value[j] = s.Value[j-1]
		}
		s.Value[j] = t
	}
	return s.Value, nil
}

折半插入排序

简介

将直接插入排序中寻找 A[i] 的插入位置的方法改为采用折半比较，即可得到折半插入排序算法。

算法思想

1. 计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置到中间值的位置，这样很简单的完成了折半；
2. 在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；
3. 确定位置之后，将整个序列后移，并将元素插入到相应位置。

go 实现

折半插入排序用到了二分查找法的思想，因此在实现中也要参考二分查找法实现的思想：

low,high := 0,len
for low<=high{
	mid := (low+high)/2
	if current>key {
		high = mid - 1 
	}else if current<key {
		low = mid + 1
	}else{
		high = mid
		break
	}
}

通过不断的对半查找，不断的缩小范围来找到关键值应该所在的索引值（也就是 high 的值）

type HalfInsertionSort struct {
	Value []int
}

func (s *HalfInsertionSort) Sort() ([]int, error) {
	if len(s.Value) <= 1 {
		return s.Value, nil
	}
	for i := 1; i < len(s.Value); i++ {
		// 如果待排序值小于前值，说明需要排序
		if s.Value[i] < s.Value[i-1] {
			key, low, high := s.Value[i], 0, i
			for low <= high {
				mid := (low + high) / 2
				if s.Value[mid] > key {
					high = mid - 1
				} else if s.Value[mid] < key {
					low = mid + 1
				} else {
					high = mid
					break
				}
			}
			var k int
			// 循环结束后，high 的值便是 key 需要在待排序中的位置
			for k = i - 1; k > high; k-- {
				s.Value[k+1] = s.Value[k]
			}
			s.Value[k+1] = key
		}
	}
	return s.Value, nil
}

思维导图