基于JavaScript实现的希尔排序算法分析

2024-11-26 12:32:23

本文实例讲述了基于JavaScript实现的希尔排序算法。分享给大家供大家参考，具体如下：

通过对直接插入排序的分析，可知其时间复杂度为O（n2），但是，如果待排序序列为正序时，其时间复杂度可提高至O（n）。希尔排序正是对此进行改进的排序。希尔排序的核心理念与插入排序不同，它会首先比较距离较远的元素，而非相邻元素。通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。

下图演示了希尔排序中间隔序列是如何运行的：

下面我们通过js来实现希尔排序，代码如下：

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JavaScript希尔排序</title>
</head>
<body>
<script type="text/javascript">
  function shellSort(nums){//希尔排序
    var gaps=[5,3,1];//定义间隔区间
    for(var g=0;g<gaps.length;g++){//一个一个间隔值开始
      for(var i=gaps[g];i<nums.length;i++){//以间隔值遍历
        var temp=nums[i];//选中元素
        for(var j=i;j>=gaps[g]&&nums[j-gaps[g]]>temp;j-=gaps[g]){//如果前面一个大于后面一个
          nums[j]=nums[j-gaps[g]];//后移
        }
        nums[j]=temp;//填补
      }
    }
  }
  function show(nums){//显示数组
    for(var i=0;i<nums.length;i++){
      document.write(nums[i]+' ');
    }
    document.write('<br>');
  }
  var nums=[6,0,2,9,3,5,8,0,5,4];
  show(nums);//6 0 2 9 3 5 8 0 5 4
  shellSort(nums);//希尔排序
  show(nums);//0 0 2 3 4 5 5 6 8 9
</script>
</body>
</html>

其排序过程如下：

希尔排序根据间隔序列的选取不同，时间复杂度也不同，但是需要注意，应该使间隔序列中的值没有除1以外的公因子，并且最后一个间隔值必须等于1。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

JS排序之快速排序详解

本文为大家分享了JS快速排序的具体代码,供大家参考,具体内容如下说明时间复杂度指的是一个算法执行所耗费的时间空间复杂度指运行完一个程序所需内存的大小稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面不稳定指,如果a=b,a在b的前面,排序后可能会交换位置 --JS快速排序-- 原理从数组中选定一个基数,然后把数组中的每一项与此基数做比较,小的放入一个新数组,大的放入另外一个新数组.然后再采用这样的方法操作新数组.直到所有子集只剩下一个元素,排序完成. 时间复杂度,空间复杂度,稳
JavaScript之排序函数_动力节点Java学院整理

排序算法排序也是在程序中经常用到的算法.无论使用冒泡排序还是快速排序,排序的核心是比较两个元素的大小.如果是数字,我们可以直接比较,但如果是字符串或者两个对象呢?直接比较数学上的大小是没有意义的,因此,比较的过程必须通过函数抽象出来.通常规定,对于两个元素x和y,如果认为x < y,则返回-1,如果认为x == y,则返回0,如果认为x > y,则返回1,这样,排序算法就不用关心具体的比较过程,而是根据比较结果直接排序. JavaScript的Array的sort()方法就是用于排序的,但是
JS实现的点击表头排序功能示例

本文实例讲述了JS实现的点击表头排序功能.分享给大家供大家参考,具体如下: 运行效果: 1.index.html文件: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html> <head> <title>jb51.net点击表头排序</t
利用JavaScript对中文（汉字）进行排序实例详解

前言在网页上展示列表时经常需要对列表进行排序:按照修改/访问时间排序.按照地区.按照名称排序. 对于中文列表按照名称排序就是按照拼音排序,不能简单通过字符串比较-- 'a' > 'b'--这种方式来实现. 比如比较 '北京' vs '上海',实际是比较 'běijīng' vs 'shànghǎi':比较 '北京' vs '背景',实际是比较 'běijīng' vs 'bèijǐng'. 一般需要获取到字符串的拼音,再比较各自的拼音. 实现方法 JavaScript 提供本地化文字排序,比如
基于JavaScript实现的快速排序算法分析

本文实例讲述了基于JavaScript实现的快速排序算法.分享给大家供大家参考,具体如下: 首先要介绍一下冒泡排序,冒泡排序的过程很简单,首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个关键字交换,然后比较第二个和第三个,直到最后一个比较完成.这是第一趟冒泡,其结果使得关键字最大的记录被安置到最后一个位置上了.然后对序列前n-1个元素进行第二次冒泡,将倒数第二个选出.以此类推直到所有被选出,冒泡结束. 通过分析可以得出,冒泡排序的时间复杂度为O(n2). 快速排序是对冒泡
javascript 数组排序与对象排序的实例

javascript 数组排序与对象排序的实例数组排序在使用JavaScript的时候,我们都发现了sort这个函数其实是按照字典顺序进行排序的,比如下面的这个例子: var ary = [2, 98, 34, 45, 78, 7, 10, 100, 99]; ary.sort(); console.log(ary); 控制台输出结果: Array [ 10, 100, 2, 34, 45, 7, 78, 98, 99 ] 这个也很显然验证了我之前所写的东西,上面的结果就是比较数组元素的第
Vue.js bootstrap前端实现分页和排序

写之前先抱怨几句.本来一心一意做.net开发的,渐渐地成了只做前端.最近项目基本都用java做后台,我们这些.net的就成了前端,不是用wpf做界面,就是用html写web页面. 深知自己前端技术不足,以前虽说用asp.net前后台都做,但是,对于前端都是用现成的js库和页面模板,对于vue.js等框架基本没有接触过. 只怪自己不会写java,最近做一个项目,负责前端,后台传来数据不分页,前端收到所有数据后自己分页.我尽是无语. 正好最近在看vue.js.这个页面就用它来实现吧.顺便总结下. 效
JS实现简易的图片拖拽排序实例代码

由HTML5的拖放API,实现的简易图片拖放效果. 一.HTML5拖放API的知识点首先我们得知道元素怎么才可以被拖放,需要设置它们的draggable属性,其中img和a标签的dragable属性默认是true,不需要我们手动设置. 拖放API的监听事件如下: dragstart: 源对象拖拽开始: drag: 源对象拖拽的过程中: dragend: 源对象拖拽结束: dragenter: 进入过程对象区域; dragover: 在过程对象区域内移动: dragleave: 离开过程对象区域
基于JavaScript实现的希尔排序算法分析

本文实例讲述了基于JavaScript实现的希尔排序算法.分享给大家供大家参考,具体如下: 通过对直接插入排序的分析,可知其时间复杂度为O(n2),但是,如果待排序序列为正序时,其时间复杂度可提高至O(n).希尔排序正是对此进行改进的排序.希尔排序的核心理念与插入排序不同,它会首先比较距离较远的元素,而非相邻元素.通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔. 下图演示了希尔排序中间隔序列是如何运行的: 下面我们通过js来实现希尔排序,代码如下: <!DOCTYPE ht
JavaScript排序算法之希尔排序的2个实例

插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率.但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位.希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布.一些老版本教科书和参考手册把该算法命名为Shell-Metzner,即包含Marlene Metzner Norton的名字,但是根据Metzner本人的说法,"我没有为这种算法做任何事,我的名字不应该出现在算法的名字中." 希尔排序基本思想:先取一个小于n的
Java经典排序算法之希尔排序详解

一.希尔排序(Shell Sort) 希尔排序(Shell Sort)是一种插入排序算法,因D.L.Shell于1959年提出而得名. Shell排序又称作缩小增量排序. 二.希尔排序的基本思想希尔排序的中心思想就是:将数据进行分组,然后对每一组数据进行排序,在每一组数据都有序之后,就可以对所有的分组利用插入排序进行最后一次排序.这样可以显著减少交换的次数,以达到加快排序速度的目的. 希尔排序的中心思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数
基于JavaScript实现的插入排序算法分析

本文实例讲述了基于JavaScript实现的插入排序算法.分享给大家供大家参考,具体如下: 根据排序过程中使用的存储器不同,可以将排序方法分为两大类:内部排序和外部排序. 内部排序是指待排序记录存放在计算机随机存储器中进行的排序过程:外部排序指的是待排序的记录数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程. 下面介绍几种常见的内部排序方式: 插入排序插入排序是一种最简单的排序方法,它的基本操作是将一个记录插入已排好序的有序表中,从而得到一个新的.记录数加1的有
JavaScript希尔排序、快速排序、归并排序算法

以var a = [4,2,6,3,1,9,5,7,8,0];为例子. 1.希尔排序. 希尔排序是在插入排序上面做的升级.是先跟距离较远的进行比较的一些方法. function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap>0){ for (var k = 0; k < gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i
基于JavaScript实现评论框展开和隐藏功能

1.效果图如下所示, 点击评论会在对应的评论区域展开评论输入框,点击取消会取消对应的评论输入框 2.html代码:需要引入jQuery.js <div class="nr-comment"> <div class="nr-comment-con"> <div class="nr-comment-nav"> <div class="comment-number"> <span
细致解读希尔排序算法与相关的Java代码实现

希尔排序(Shell's sort)是一种非常"神奇"的排序算法.说它"神奇",是因为没有任何人能清楚地说明它的性能到底能到什么情况.希尔排序因DL．Shell于1959年提出而得名.自从C. A. R. Hoare在1962年提出快速排序后,由于其更为简单,一般采用快速排序.但是,不少数学家们还是孜孜不倦地寻找希尔排序的最佳复杂度.作为普通程序员,我们可以学习下希尔的思路. 顺便说一句,在希尔排序出现之前,计算机界普遍存在"排序算法不可能突破O(n2)&
Javascript中的常见排序算法

具体代码及比较如下所示: 复制代码代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">
基于JavaScript Array数组方法(新手必看篇)

Array类型是ECMAScript中最常用的引用类型.ECMAScript中的数据与其它大多数语言中的数组有着相当大的区别.虽然ECMAScript中的数据与其它语言中的数组一样都是数据的有序列表,但不同的是,ECMAScript数组中的每一项可以保存任何类型的数据,无论是数值.字符串或者是对象.同时,ECMAScript中的数组大小是可以动态调整的,即可以根据数据的添加自动增长以容纳新增的数据.下面总结一下JavaScript中数组常用的操作函数及用法. •创建数组创建数组主要有构造函数和

基于JavaScript实现的希尔排序算法分析

相关推荐

随机推荐