3.13 插入排序

1. 插入排序

把数组分成有序和无序的部分，从无序部分取出每一个元素插入到已排好序的数组中

在数组相对有序的情况下效率比选择排序高，时间复杂度O（N）

2. 特点

• 稳定性：稳定
• 原地排序
• 空间复杂度：O（1）
• 时间复杂度：O（n²）

3. 过程

4. 实现

//O(N²)
func InsertionSort(data []model.Comparable) {
	//data[0...i)是有序的；data[i...n)是无序的
	//每经过一次外层循环，data[i]就被放到合适的位置
	for i := 0; i < len(data); i++ {
		for j := i; j-1 >= 0; j-- {
			//data[0...i)是有序的，把data[i]放到合适的位置
			if data[j].CompareTo(data[j-1]) < 0 {
				util.Swap(data, j, j-1)
			} else {
				break
			}
		}
	}
}

//O(N²)。相对于上面的算法减少了交换次数
func InsertionSort2(data []model.Comparable) {
	//data[0...i)是有序的；data[i...n)是无序的
	//每经过一次外层循环，data[i]就被放到合适的位置
	for i := 1; i < len(data); i++ {

        //data[0...i)是有序的，把data[i]放到合适的位置
		toBeInserted := data[i]
		position := i
		for position > 0 && data[position-1].CompareTo(toBeInserted) > 0 {
		    //减少了交换次数
			data[position] = data[position-1]
		}

		data[position] = toBeInserted
	}
}

4.1. 测试

func TestInsertionSort(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	InsertionSort(data)
	fmt.Println(data)
}

5. 参考

• 排序算法稳定性_百度百科
• 6.9. The Insertion Sort — Problem Solving with Algorithms and Data Structures