美文网首页
希尔排序

希尔排序

作者: 梁森的简书 | 来源:发表于2021-01-18 23:39 被阅读0次

希尔排序是对插入排序的改进,引入了一个增量,按照增量将数组分成多个组,每个组分别进行插入排序,直到增量为1,进行最后一次插入排序。

代码

struct Shell {
    
    // 希尔排序是对插入排序的改进
    static func sort(array: inout [Int]) {
        var h:Int = 1   // 增量
        while h < (array.count / 2 ) {
            h = 2 * h + 1
        }
        while h >= 1 {
            for i in (h..<array.count) {
                for j in stride(from: i, through: h, by: -h) {
                    let a = array[j - h]
                    let b = array[j]
                    let result = compare(a: a , b: b)
                    if result == true {
                        exchange(array: &array, aIndex: j-h, bIndex: j)
                    } else {
                        break
                    }
                }
            }
            h = h / 2
        }
        
    }
    
    /// 比较大小
    static func compare(a: Int, b: Int) -> Bool {
        if a > b {
            return true
        } else {
            return false
        }
    }
    
    /// 交换位置
    static func exchange( array: inout [Int], aIndex: Int, bIndex: Int) {
        let temp = array[aIndex]
        array[aIndex] = array[bIndex]
        array[bIndex] = temp
    }
    
}

比较希尔排序和插入排序会发现,当数据上万条后,希尔排序花费的时间要少很多。

相关文章

  • 排序算法(二)之希尔排序

    图解排序算法(二)之希尔排序 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也...

  • 07-希尔排序(Shell Sort)

    希尔排序(Shell Sort) 希尔排序是唐纳德·希尔(Donald Shell)在0959年提出的。希尔排序与...

  • 排序-希尔排序(分治)

    希尔排序 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序...

  • swift经典算法-希尔排序

    希尔排序 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序...

  • 排序算法④——希尔排序

    希尔排序 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序...

  • 排序算法-希尔排序(Java实现)

    希尔排序 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是...

  • 说说算法那些事-希尔排序

    希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,希尔排序法又称...

  • 希尔排序学习

    希尔排序希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序是基...

  • 排序算法(四) 希尔排序(插入排序的进化)

    参考Java排序算法(四):希尔排序常见排序算法 - 希尔排序 (Shell Sort) 希尔排序算法是按其设计者...

  • 编程马拉松 Day04 希尔排序、归并排序、快速排序

    本文将介绍三个高级排序算法 希尔排序 归并排序 快速排序 希尔排序 希尔排序(Shell's Sort)的名称源于...

网友评论

      本文标题:希尔排序

      本文链接:https://www.haomeiwen.com/subject/ahiwaktx.html