`
caocao
  • 浏览: 271699 次
  • 来自: 上海
社区版块
存档分类
最新评论

JavaScript版快速排序增强版

阅读更多

作者:caocao(网络隐士),http://www.caocao.namehttp://www.caocao.mobi
转载请注明来源:http://caocao.iteye.com/blog/123721

对于某些只读的HTML collection来说,普通排序方法无法对其进行排序,于是隐士想到了编写一个增强版的JavaScript版快速排序程序。该排序除了接收可读写的一个数组外,还接收一个实现了compare, swap接口的变量。可读写的数组由调用者根据只读collection生成,具体的交换过程在swap中由用户自行实现,这样可以改善系统提供的排序的局限性。至于debug接口,可以选择不实现,在不实现debug的情况下,不会造成排序性能损失。

java 代码
  1. var sortContainer=   
  2. {   
  3.     compare: function(v1, v2)   
  4.     {   
  5.         if (v1==v2)   
  6.             return 0;   
  7.         else if (v1<v2)   
  8.             return -1;   
  9.         else  
  10.             return 1;   
  11.     },   
  12.   
  13.     swap: function(i1, i2)   
  14.     {   
  15.     },   
  16.        
  17.     debug: function(message)   
  18.     {   
  19.         document.getElementById("DebugDiv").innerHTML+=message+"<br/>";   
  20.     }   
  21. }   
  22.   
  23. function quickSort(a, container)   
  24. {   
  25.     if (a==null)   
  26.         return;   
  27.     var length=a.length;   
  28.     if (length<2)   
  29.         return;   
  30.     function internalQuickSort(lowIndex, highIndex, a, container)   
  31.     {   
  32.         if (lowIndex<highIndex)   
  33.         {   
  34.             var pos=internalPartition(lowIndex, highIndex, a, container);   
  35.             internalQuickSort(lowIndex, pos-1, a, container);   
  36.             internalQuickSort(pos+1, highIndex, a, container);   
  37.         }   
  38.     }   
  39.     function internalPartition(lowIndex, highIndex, a, container)   
  40.     {   
  41.         var pivot=a[lowIndex];   
  42.         var lowI=lowIndex;   
  43.         var highI=highIndex;   
  44.         while (true)   
  45.         {   
  46.             do {lowI++;} while (container.compare(a[lowI], pivot)<0);   
  47.             while (container.compare(a[highI], pivot)>0) {highI--;}   
  48.             if (lowI>=highI) break;   
  49.             var tmp=a[lowI];   
  50.             a[lowI]=a[highI];   
  51.             a[highI]=tmp;   
  52.             container.swap(lowI, highI);   
  53.             if (container.debug) container.debug("* "+lowI+"("+a[highI]+") -&gt; "+highI+"("+a[lowI]+") ["+a.join(",")+"]");   
  54.         }   
  55.         if (lowIndex!=highI)   
  56.         {   
  57.             a[lowIndex]=a[highI];   
  58.             a[highI]=pivot;   
  59.             container.swap(lowIndex, highI);   
  60.             if (container.debug) container.debug(lowIndex+"("+a[highI]+") -&gt; "+highI+"("+a[lowIndex]+") ["+a.join(",")+"]");   
  61.         }   
  62.         return highI;   
  63.     }   
  64.     if (container.debug) container.debug("["+a.join(",")+"]");   
  65.     internalQuickSort(0, length-1, a, container);   
  66.     if (container.debug) container.debug("["+a.join(",")+"]");   
  67. }   
  68.   
  69. var a=new Array(1,3,8,2,4,6,5,7,40,35,67,82,23,31,2,3,45);   
  70. quickSort(a, sortContainer);  

分享到:
评论

相关推荐

    JavaScript中常见排序算法详解共19页.pdf.z

    4. 快速排序(Quick Sort):由C.A.R. Hoare提出的,采用分治策略。选取一个基准值,将数组分为小于和大于基准值两部分,再对这两部分递归进行快速排序。平均时间复杂度为O(n log n),最坏情况下为O(n^2)。 5. 归并...

    javascript可拖动排序源码

    本压缩包提供的“javascript可拖动排序源码”应该包含实现这一功能的JavaScript代码,帮助开发者快速集成到自己的项目中。 首先,我们要理解JavaScript可拖动排序的基本原理。它是基于HTML5的`dragstart`、`drag`、...

    33种Javascript 表格排序控件收集

    5. Sorting Tables with Object Oriented JavaScript QuickSort(5):使用面向对象的JavaScript实现快速排序算法,适用于需要高性能排序的场景。 6. Standardista Table Sorting(6):一个模块化的客户端表格排序...

    javascript快速集成表格编辑功能插件升级版

    "javascript快速集成表格编辑功能插件升级版"提供了一种高效的方法,使得开发者能够快速地在网页中实现表格的编辑功能。这个插件是基于JavaScript语言,并且可能利用了Prototype库来增强其功能,使得表格的编辑操作...

    javascipt排序算法可视化.rar

    在这个名为"javascipt排序算法可视化.rar"的压缩包中,包含了JavaScript实现的几种常见排序算法的可视化示例,如冒泡排序、选择排序、快速排序和希尔排序。 **冒泡排序**: 冒泡排序是一种基础的交换排序,它通过...

    JavaScript_《Grokking算法》一书的代码.zip

    书中可能涵盖的算法包括排序(如冒泡排序、选择排序、快速排序)、查找(线性查找、二分查找)、图论(深度优先搜索、广度优先搜索)以及动态规划等。 排序算法是数据处理的基础,冒泡排序是一种简单的交换排序,...

    javascript深入编程 网页收藏(续集)

    2. **数据结构与算法**:介绍JavaScript中如何实现常见的数据结构(如数组、链表、栈、队列、哈希表等)和算法(如快速排序、二分查找、Dijkstra算法等)。 3. **框架实战**:通过实际项目案例,演示如何使用React、...

    JS排序插件

    2. **性能优化**:对于大型数组,原生的`sort()`方法可能会有性能问题,插件可能提供了更高效的排序算法,如快速排序、归并排序等。 3. **多类型支持**:不仅限于数字排序,可能还包括字符串、日期、自定义对象等...

    Drupal6 JavaScript jQuery

    在Drupal6中,JavaScript可以用来增强用户体验,实现更流畅的页面导航,动态加载内容等。通过合理运用JavaScript,开发者可以提高网站的性能和响应速度。 #### 3. **jQuery的作用** jQuery是一个快速、简洁的...

    S2 项目 Javascript项目实战

    S2,作为一款数据可视化工具,可能是Apache Superset的一个分支或增强版,专为构建复杂的表格和图表而设计。它允许开发者以灵活的方式展示大量数据,同时支持多种数据源集成,如数据库、API等。在JavaScript项目实战...

    prettyalgorithms用JavaScript实现的各种算法示例

    这个项目可能包含了排序算法(如快速排序、归并排序、冒泡排序等)、搜索算法(如二分查找、广度优先搜索等)、图论算法(如最短路径算法Dijkstra、拓扑排序等)以及动态规划和回溯法等经典问题的解决方案。...

    边学边干加强版(不错)

    《边学边干加强版》是一本以实践为导向的IT技术图书,主要针对希望在学习过程中结合实际操作提升技能的读者。"边学边干"的教育理念强调理论与实践相结合,通过动手实践来加深对知识的理解和掌握。这本书之前的版本...

    arcgis api for Javascript4.7下载

    - **第三方库集成**:4.7版本增强了与其他JavaScript库的兼容性,如Bootstrap、React等,方便开发者构建复杂的应用架构。 - **自定义扩展**:API允许开发者创建自定义扩展和模块,满足特定项目需求。 7. **安装与...

    Javascript 常见效果 雅虎

    3. **动画效果**:JavaScript可以创建各种动态效果,增强用户体验。YUI的Animation模块允许开发者轻松创建平滑的CSS属性过渡、基于时间轴的复杂动画序列,甚至包括3D转换和硬件加速功能。 4. **Ajax通信**:Ajax...

    jqueryUI,jqueryapi1.8,网页特效手册,javascript手册,网页兼容手册,全中文文档打包

    网页特效是指通过JavaScript和CSS实现的各种动态视觉效果,可以增强用户体验和网站的吸引力。这可能包括页面过渡、图片轮播、滑动面板、滚动动画等。利用jQuery库,开发者可以轻松实现这些特效,比如使用 `.fadeIn()...

    siphash24用纯JavaScript和WebAssembly实现SipHash24

    通过理解SipHash24的算法原理,以及如何在JavaScript和WebAssembly中实现,开发者可以增强其应用程序的安全性,特别是在处理用户输入或数据排序时,避免遭受诸如“哈希洪水”攻击之类的威胁。同时,结合WebAssembly...

    JavaScript示例导学(书籍)

    综上所述,《JavaScript示例导学》是一本非常实用的学习资料,不仅能够帮助初学者快速掌握JavaScript的基本概念和编程技巧,还能引导读者深入探索JavaScript的高级功能,非常适合希望在网页编程领域有所发展的读者。

    zTree_v3-master.zip_javascript

    7. **节点排序**:可以对节点进行排序,提供升序、降序等多种排序方式。 8. **数据绑定**:灵活的数据绑定方式,可以绑定JSON、XML等格式的数据源。 zTree_v3-master压缩包内包含的主要文件和目录可能有: - `css`...

    lazylinq是LINQ的一个完整JavaScript移植

    4. **数据操作**:lazylinq可能提供了诸如筛选(Where)、选择(Select)、分组(GroupBy)、连接(Join)、排序(OrderBy)、聚合(Sum, Count等)等常见的数据操作方法。 5. **适用场景**:lazylinq适用于需要...

Global site tag (gtag.js) - Google Analytics