(3) 插入排序

一 插入排序

1.1 插入排序

插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中， 从而得到一个新的有序表，该表中的已排序数据数目加1。

1.2 插入排序实现

func InsetionSort(arr []int) {if arr == nil || len(arr) < 2 {fmt.Println("数组不满足要求")return}// 0位置时，只有1个元素，我们认为他已经是有序的for i := 1; i <= len(arr)-1; i++ {// 若当前元素比前一个元素小，查看 i 位置的元素应该插入到 0-（i-1）位置的何处if arr[i] < arr[i-1] {temp := arr[i]for j := i; j >= 0; j-- {if j > 0 && arr[j-1] > temp {arr[j] = arr[j-1]} else {arr[j] = tempbreak}}}}
}

1.3 插入排序优化：二分搜索插入

插入位置可以利用二分查找法来快速寻找

二 插入排序复杂度

逆序对：数组 [2,3,8,6,1] 的逆序对为 <2,1> < 3,1> <8,1> <8,6> <6,1>

插入排序的时间复杂度与逆序对的数量成正比关系：

• 最坏情况、平均时间复杂度都是O(n^2)
• 最好情况：已经排序的数据，即逆序对数量为0，时间复杂度为O(n)

贴士：大多情况下，快排是很快的，但是当数据量较小时，插入排序的性能很可能比快排还要高。