插入排序

169次阅读

共计 503 个字符,预计需要花费 2 分钟才能阅读完成。

概念
插入排序算法类似于打扑克抽牌。从未排序的数组中(牌堆)取出一个元素,在已排序元素中(手牌)从后向前扫描,插入到比这个元素小或者相等的后面。重复此步骤,直到整个序列有序为止。

代码实现
func insertSort(arr []int) []int {
n := len(arr)
for i := 1; i < n; i++ {
value := arr[i]
j := i - 1
for j >= 0 && arr[j] > value {
arr[j+1] = arr[j]
j--
}
arr[j+1] = value
}
return arr
}
其中,arr 是待排序的整数序列,n 是序列的长度。在每一轮遍历中,将未排序部分的第一个元素取出,与已排序部分中的元素依次比较,找到比这个元素小或者相等的位置插入。这样一轮下来,未排序部分中的第一个元素就被插入到了已排序部分的适当位置。通过多轮的遍历比较,最终实现整个序列的排序。

算法分析
最好的情况下,当序列已排序好时,每一次迭代的过程中,只需要做一次比较即可,这个请款下,算法的时间复杂度为 O(n),最坏的情况下,当序列为逆序时,插入排序的时间复杂度为 O(n^2),其中 n 是待排序序列的长度。它的空间复杂度为 O(1),是一种稳定的排序算法。

正文完
 
dkp
版权声明:本站原创文章,由 dkp 2023-04-04发表,共计503字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。