Javascript算法——希尔排序

lowett 发布于2019-08-20 16:38 / 2002人阅读

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。这里主要介绍希尔排序。一图胜千言算法介绍算法描述希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。这里主要介绍希尔排序。

一图胜千言：

1. 算法介绍 1.1 算法描述

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序。

1.2 算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

1.3 算法实现

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //动态定义间隔序列
        gap = gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

GPU云服务器云服务器希尔排序排序算法图解排序算法总结桶排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/83058.html

JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 评论0 收藏0
javascript数据结构与算法 --- 高级排序算法

摘要：高级排序算法总结希尔排序间隔序列可以动态定义，不过对于大部分的实际应用场景，算法要用到的间隔序列可以提前定义好有一些公开定义的间隔序列，使用它们会得到不同的结果。高级排序算法总结希尔排序 function shellsort(array, gaps) { for (var g = 0; g < gaps.length; g++) { for ...

qianfeng 2019-08-26 11:34 评论0 收藏0
算法笔记(JavaScript版)——排序

摘要：算法笔记版排序本文内容根据和的算法第四版整理，原代码为语言，自己修改为版本，仅供参考。希尔排序的思想是使数组中任意间隔为的元素都是有序的。使用递增序列，，，，，的希尔排序所需的比较次数不会超过的若干倍乘以递增序列的长度。算法笔记(JavaScript版)——排序本文内容根据Rebert Sedgewick和Kevin Wayne的《算法（第四版）》整理，原代码为java语言，自己修...

ctriptech 2019-08-22 10:34 评论0 收藏0
JavaScript 版各大排序算法

摘要：推荐一下，，这里还有个可视化的排序博客，各大排序算法的实现都栩栩如生。堆排序堆排序是指利用堆这种数据结构所设计的一种排序算法。共勉参考维基百科排序搜索聊一聊排序算法秒杀种排序算法版排序图解排序算法实现欢迎来我的博客交流最近看到了很多公司都在准备明年的实习校招，虽然离三月份还有一段时间，感觉已经可以准备了。在网上看了一些排序算法和数组去重操作，感觉都写的很好，心血来潮，也来写一写。 s...

FrozenMap 2019-08-20 13:47 评论0 收藏0
算法：排序算法总结（JavaScript描述）

摘要：二代码简单选择排序一分析循环次，每一次的当前项与其之后的项作比较，找出其中最小的那个，与当前项交换。二代码希尔排序是一种改进版的插入排序，缩小增量排序。这样做的目的是因为，直接插入排序在序列基本有序时效率最高。排序算法平均情况最好情况最坏情况辅助空间稳定性冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定简单选择排序 O(n^2) O(n^2)...

dkzwm 2019-08-23 11:45 评论0 收藏0