Golang排序算法-希尔排序

2018-09-15 21:50:04 george518 ...

什么是希尔排序(Shell sort)

希尔排序是插入排序的一种优化算法,先来看百度百科的定义:

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

定义说的严谨,可是吧,一时半会很难看懂。我们知道插入排序是每次都是取基准元素左侧的元素比较大小,也就是每次比较的步长为1,如果是近乎有序的数组,插入排序很容易退化成O(n^2),而希尔排序每次选择的步长是不一样的(当然最后的步长肯定为1,也就是最后用一次插入排序),这是打破插入排序O(n^2)时间复杂度的关键步骤。

所以,希尔排序的思想是:
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,在对全体进行一次直接插入排序。

思路分析:

希尔排序是需要先将序列分为若干个子序列,采用什么方法分效率最高,是一个还没有解决的问题,不过,目前希尔排序的分组方法通常采用折半法分组。使用举例方法说明这一点。

假设一个数组arr [3,4,6,7,8,9,1,2,5,0]
则数组长度为len=10,

第一次分组分成5个组,(len/2)
此时需要比较的元素为:

组别 【下标】元素值 【下标】元素值
第一组 【0】3 【5】9
第二组 【1】4 【6】1
第三组 【2】6 【7】2
第四组 【3】7 【8】5
第五组 【4】8 【9】0

采用直接插入排序,分组排序结果是:

组别 【下标】元素值 【下标】元素值
第一组 【0】3 【5】9
第二组 【1】1 【6】4
第三组 【2】2 【7】6
第四组 【3】5 【8】7
第五组 【4】0 【9】8

比较并交换位置后数组arr变成:
[3,1,2,5,0,9,4,6,7,8]

第二次分组分为 2 个分组,(len/2)/2

组别 【下标】元素值 【下标】元素值 【下标】元素值 【下标】元素值 【下标】元素值
第一组 【0】3 【2】2 【4】0 【6】4 【8】7
第二组 【1】1 【3】5 【5】9 【7】6 【9】8

采用直接插入排序对这2个分组进行排序

组别 【下标】元素值 【下标】元素值 【下标】元素值 【下标】元素值 【下标】元素值
第一组 【0】0 【2】2 【4】3 【6】4 【8】7
第二组 【1】1 【3】5 【5】6 【7】8 【9】9

比较和交换位置后数组arr变成:
[0,1,2,5,3,6,4,8,7,9]

第三次分组分为1组,(len/2)/2/2
也就是直接使用插入排序法
[0,1,2,3,4,5,6,7,8,9]

以上就是折半分组法。

Golang代码

/************************************************************
** @Description: shell
** @Author: haodaquan
** @Date:   2018-09-04 22:59
** @Last Modified by:   haodaquan
** @Last Modified time: 2018-09-04 22:59
*************************************************************/
package shell

func Sort(arr []int) []int {
    len := len(arr)
    if len <= 1 {
        return arr
    }
    var i, j, gap int

    for gap = len / 2; gap > 0; gap = gap / 2 {
        for i = gap; i < len; i++ {
            for j = i - gap; j >= 0 && arr[j] > arr[j+gap]; j = j - gap {
                arr[j], arr[j+gap] = arr[j+gap], arr[j]
            }
        }
    }

    return arr
}

优缺点

希尔排序特别适合近乎有序的序列排序使用

测试代码和性能测试代码已经放到了github上,地址:

https://github.com/george518/PPGo_algorithm/tree/master/sort/shell

不妨一试.

可参考的资料

http://v.youku.com/v_show/id_XNTA3NDUxMjcy.html
http://baidu.iqiyi.com/watch/7194221101908076908.html?page=videoMultiNeed

相似文章


345708673

在路上

技术无止境,一直在路上。 年过而立,惴惴不安,愈加发奋,孜孜求学。