Go语言数据结构之希尔排序怎么实现

这篇文章主要介绍“Go语言数据结构之希尔排序怎么实现”，在日常操作中，相信很多人在Go语言数据结构之希尔排序怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Go语言数据结构之希尔排序怎么实现”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

希尔排序

在插入排序中，在待排序序列的记录个数比较少，而且基本有序，则排序的效率较高。

1959 年，Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进，提出了希尔排序算法。

希尔排序又称为“缩小增量排序”。即将待排序记录按下标的一定增量分组（减少记录个数），对每组记录使用直接插入排序算法排序（达到基本有序）；

随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1，整个序列基本有序，再对全部记录进行一次直接插入排序。

算法思想

Shell 排序是一种高效的排序算法，基于插入排序算法。这种算法避免了插入排序中的大量移动，如果较小的值在最右边，就必须移到最左边。较小的值在最右边，必须移到最左边。

算法步骤：

• 设待排序的记录存储在数组 array[1...n]  中，增量序列为 {g1, g2, ..., gt}  , n>g1>g2>...>gt=1 。

• 第一趟增量 g1, 所有间隔为 g1 的记录分在一组，对每组记录进行插入排序。

• 第二趟取增量 g2，所有间隔为 g2 的记录分在一组，对每组记录进行插入排序。

• 依次进行下去，直到所取增量 gt = 1，所有记录在一组中进行插入排序。

图解算法

假设我们有一个数组： [7, 4, 3, 5, 2, 1, 6] :

第一次希尔排序间隔为3时：

第二次希尔排序间隔为2时：

第三次希尔排序间隔为1时：

Go 代码实现：

package main
import "fmt"
func swap(array []int, a int, b int) {
    array[a] = array[a] + array[b]
    array[b] = array[a] - array[b]
    array[a] = array[a] - array[b]
}
func shellSort(array []int, length int) {
    for gap := length / 2; gap > 0; gap = gap / 2 {
        for i := gap; i < length; i++ {
            var j = i
            for {
                if j-gap < 0 || array[j] >= array[j-gap] {
                    break
                }
                swap(array, j, j-gap)
                j = j - gap
            }
        }
    }
}
func main() {
    nums := []int{7, 4, 3, 5, 2, 1, 6}
    length := len(nums)
    shellSort(nums, length)
    for i := 0; i < length; i++ {
        fmt.Println(nums[i])
    }
}

运行结果：

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\希尔排序\main.go"
1
2
3
4
5
6
7

总结

空间复杂度： 希尔排序在分组进行插入排序时使用了一个辅助空间 j，空间复杂度为 O(1)O(1)O(1)

稳定性： 希尔排序的分组导致不同组间的相同数字可能会调换位置，所以希尔排序是不稳定的排序算法。

到此，关于“Go语言数据结构之希尔排序怎么实现”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！