排序算法——Golang实现(二)
原创
2.4 插入排序（Insertion Sort）
1. 直接插入排序
- 基本思想：每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
- 时间复杂度：
O(n^2) - 空间复杂度：
O(1) - 是
稳定排序 稳定排序：在处理相等键值的元素时，保持它们的相对顺序不变。 不稳定排序：在处理相等键值的元素时，可能改变它们的相对顺序。
代码实现
我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
func InsertSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
for i := 0; i < len(arr); i++ {
// 每次从未排序区间取一个数据 value
value := arr[i]
// 在已排序区间找到插入位置 j
var j int
for j = i - 1; j >= 0; j-- { // 遍历已排序的部分
// 如果比value大，就后移，为value腾位置
if arr[j] > value {
arr[j+1] = arr[j]
} else {
break
}
}
// 插入数据 value
arr[j+1] = value
}
return arr
}
func main() {
test := []int{4, 5, 6, 1, 3, 2}
fmt.Println(InsertSort(test))
}2. 希尔排序
直接插入排序对于基本有序的数组，会体现出良好的性能，这一特性，也给了它进一步优化的可能性。
希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为 缩小增量排序 ，同时该算法是冲破O(n^2）的第一批算法之一。
- 基本思想：把 记录 按下标的一定增量 分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
- 时间复杂度：
O(n^2)只是针对最坏情况而言，平均的效率要远远高出其他时间复杂度为O(n^2)的排序算法 - 空间复杂度是
O(1) - 但是在提供优秀性能的同时，打破了排序算法的稳定性，是
不稳定的。
希尔排序在数组中采用跳跃式分组的策略，通过 某个增量 将数组元素划分为若干组，然后 分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。
希尔排序通过这种策略使得整个数组在 初始阶段达到从宏观上看 基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
我们来看下希尔排序的基本步骤，在此我们选择增量 gap=length/2，缩小增量继续以 gap = gap/2 的方式,这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。
希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。
代码实现
func ShellSort(arr []int) []int {
length := len(arr)
// 选择增量gap，并以gap/2的方式缩小增量
for gap := length / 2; gap > 0; gap /= 2 {
// 遍历[gap:]
for i := gap; i < length; i++ {
for j := i; j >= gap && arr[j-gap] > arr[j]; j = j - gap {
arr[j], arr[j-gap] = arr[j-gap], arr[j]
}
}
}
return arr
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
