javascript 的几种排序方法

简介:
< DOCTYPE html PUBLIC -WCDTD XHTML StrictEN httpwwwworgTRxhtmlDTDxhtml-strictdtd>

所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下:
输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn。
输出:Ril,Ri2,…,Rin,使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

    这里,我们简单介绍几种排序方法,直接插入排序、希儿排序、冒泡排序、快速排序、直接选择排序,文中所提及的代码在IE6下测试通过。

直接插入排序基本思想
    假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区。

    算法描述
function InsertSort(arr) { //插入排序->直接插入法排序
var st = new Date();
var temp, j;
for(var i=1; i<arr.length; i++) {
   if((arr[i]) < (arr[i-1])) {
    temp = arr[i];
    j = i-1;
    do {
     arr[j+1] = arr[j];
     j--;
    }
    while (j>-1 && (temp) < (arr[j]));
    arr[j+1] = temp;
   }//endif
}
status = (new Date() - st) + ' ms';
return arr;
}

希尔排序基本思想
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。

    算法描述


function ShellSort(arr) { //插入排序->希儿排序
var st = new Date();
var increment = arr.length;
do {
   increment = (increment/3|0) + 1;
   arr = ShellPass(arr, increment);
}
while (increment > 1)

status = (new Date() - st) + ' ms';
return arr;
}
function ShellPass(arr, d) { //希儿排序分段执行函数
var temp, j;
for(var i=d; i<arr.length; i++) {
   if((arr[i]) < (arr[i-d])) {
    temp = arr[i]; j = i-d;
    do {
     arr[j+d] = arr[j];
     j = j-d;
    }
    while (j>-1 && (temp) < (arr[j]));
    arr[j+d] = temp;
   }//endif
}
return arr;
}

冒泡排序基本思想
    将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。

    算法描述
function BubbleSort(arr) { //交换排序->冒泡排序
var st = new Date();
var temp;
var exchange;
for(var i=0; i<arr.length; i++) {
   exchange = false;
   for(var j=arr.length-2; j>=i; j--) {
    if((arr[j+1]) < (arr[j])) {
     temp = arr[j+1];
     arr[j+1] = arr[j];
     arr[j] = temp;
     exchange = true;
    }
   }
   if(!exchange) break;
}
status = (new Date() - st) + ' ms';
return arr;
}

快速排序基本思想
    将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
    在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。


    算法描述
function QuickSort(arr) { //交换排序->快速排序
if (arguments.length>1) {
   var low = arguments[1];
   var high = arguments[2];
} else {
   var low = 0;
   var high = arr.length-1;
}
if(low < high){
   // function Partition
   var i = low;
   var j = high;
   var pivot = arr[i];
   while(i<j) {
    while(i<j && arr[j]>=pivot)
     j--;
    if(i<j)
     arr[i++] = arr[j];
    while(i<j && arr[i]<=pivot)
     i++;
    if(i<j)
     arr[j--] = arr[i];
   }//endwhile
   arr[i] = pivot;
   // end function
   var pivotpos = i; //Partition(arr,low,high);
   QuickSort(arr, low, pivotpos-1);
   QuickSort(arr, pivotpos+1, high);
} else
   return;
   return arr;
}

直接选择排序基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
&#9312;初始状态:无序区为R[1..n],有序区为空。
&#9313;第1趟排序
    在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
&#9314;第i趟排序
第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换,使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
    这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

    算法描述
function SelectSort(arr) { //选择排序->直接选择排序
var st = new Date();
var temp;
for(var i=0; i<arr.length; i++) {
   var k = i;
   for(var j=i+1; j<arr.length; j++) {
    if((arr[j]) < (arr[k]))
     k = j;
   }
   if (k != i){
    temp = arr[i];
    arr[i] = arr[k];
    arr[k] = temp;
   }
}
status = (new Date() - st) + ' ms';
return arr;
}

本文转自 netcorner 博客园博客,原文链接:http://www.cnblogs.com/netcorner/archive/2007/12/05/2912246.html  ,如需转载请自行联系原作者

相关文章
|
18天前
|
JavaScript 前端开发
JavaScript遍历数组和对象常用方法总结
以上代码展示了数组和对象的多种遍历方法。对于数组,使用了传统的 `for` 循环、`for...in` 和 ES6 的 `for...of` 进行遍历;对于对象,则通过 `for...in`、`Object.keys()`、`Object.values()` 和 `Object.entries()` 来获取键值对。`for...of` 循环适用于遍历具有迭代协议的数据结构,如数组、字符串等,而对象遍历则更多地依赖于 `Object` 方法来获取其属性集合。
JavaScript遍历数组和对象常用方法总结
|
13天前
|
JavaScript 前端开发
JavaScript基础知识-方法
文章通过示例代码讲解了JavaScript中如何给对象添加方法以及如何调用这些方法。
17 2
JavaScript基础知识-方法
|
13天前
|
JavaScript 前端开发
JavaScript基础知识-数组的常用方法
关于JavaScript基础知识-数组的常用方法。
13 1
JavaScript基础知识-数组的常用方法
|
18天前
|
JavaScript 算法 前端开发
JS算法必备之String常用操作方法
这篇文章详细介绍了JavaScript中字符串的基本操作,包括创建字符串、访问特定字符、字符串的拼接、位置查找、大小写转换、模式匹配、以及字符串的迭代和格式化等方法。
JS算法必备之String常用操作方法
|
18天前
|
JavaScript 算法 前端开发
JS算法必备之Array常用操作方法
这篇文章详细介绍了JavaScript中数组的创建、检测、转换、排序、操作方法以及迭代方法等,提供了数组操作的全面指南。
JS算法必备之Array常用操作方法
|
11天前
|
前端开发 JavaScript
前端ES5 | js —添加元素方法
前端ES5 | js —添加元素方法
|
18天前
|
JavaScript 前端开发 索引
JS中常用的数组迭代方法(filter,forEach,map,every,some,find,findIndex)
这段代码和说明介绍了JavaScript中数组的一些常用方法。函数接收三个参数:`item`(数组项的值)、`index`(项的位置,可选)和`array`(数组本身,可选)。示例展示了如何使用`filter()`过滤非空项、`forEach()`遍历数组、`map()`处理并返回新数组、`every()`检查所有元素是否满足条件、`some()`检查是否存在满足条件的元素、`find()`获取首个符合条件的元素值以及`findIndex()`获取其索引位置。这些方法都不会修改原数组。
JS中常用的数组迭代方法(filter,forEach,map,every,some,find,findIndex)
|
16天前
|
Java 开发者 关系型数据库
JSF与AWS的神秘之旅:如何在云端部署JSF应用,让你的Web应用如虎添翼?
【8月更文挑战第31天】在云计算蓬勃发展的今天,AWS已成为企业级应用的首选平台。本文探讨了在AWS上部署JSF(JavaServer Faces)应用的方法,这是一种广泛使用的Java Web框架。通过了解并利用AWS的基础设施与服务,如EC2、RDS 和 S3,开发者能够高效地部署和管理JSF应用。文章还提供了具体的部署步骤示例,并讨论了使用AWS可能遇到的挑战及应对策略,帮助开发者更好地利用AWS的强大功能,提升Web应用开发效率。
40 0
|
16天前
|
移动开发 前端开发 JavaScript
前端表单验证的完美攻略:HTML5属性与JavaScript方法的无缝对接,让你的Web应用数据输入既安全又优雅
【8月更文挑战第31天】本文介绍前端表单验证的重要性及其实现方法,利用HTML5的内置属性如`required`、`pattern`和`minlength`进行基本验证,并借助JavaScript处理复杂逻辑,如密码确认。通过示例代码详细展示了如何结合两者实现高效且友好的表单验证,同时使用CSS增强用户体验。此方法简化开发流程并提升验证效果。
21 0
|
22天前
|
SQL JavaScript 前端开发
【Azure 应用服务】Azure JS Function 异步方法中执行SQL查询后,Callback函数中日志无法输出问题
【Azure 应用服务】Azure JS Function 异步方法中执行SQL查询后,Callback函数中日志无法输出问题