javascript 的几种排序方法

javascript|排序

所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
　　输入：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趟直接选择排序得到有序结果：
 ①初始状态：无序区为R[1..n]，有序区为空。
 ②第1趟排序
    在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
　　……
 ③第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;
 }
运行代码框

<style>
fieldset {
 font-size:12px;
 padding:10px;
 width:80%;
 margin:auto;
}
input {
 font-size:12px;
 font-family:Tahoma;
}
</style>
<title>排序</title>
<h3 align="center">排序</h3>
<fieldset>
<legend>插入排序</legend>

<p><b>直接插入排序</b>
请输入一段要排序的字符，用半角逗号隔开
<input name=insert type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k">
<br><input type=button value=" 排序 " >

<p><b>希儿排序</b><br>
  <input name=Shell type=text size=100 value="g,v,u,f,p,o,i,a,t,j">
<br><input type=button value=" 排序 " >

</fieldset>
<p>
<fieldset>
<legend>交换排序</legend>

<b>冒泡排序</b><br>
<input name=bubble type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k">
<br><input type=button value=" 排序 " >

<p><b>快速排序<br>
</b>
  <input name=quick type=text size=100 value="3,1,5,4,6">
<br><input type=button value=" 排序 " >

</fieldset>
<p>
<fieldset>
<legend>选择排序</legend>

<b>直接选择排序</b><br>
<input name=select1 type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k">
<br><input type=button value=" 排序 " >

<p>... ...

</fieldset>

<script>
 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;
 }

 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;
 }

 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;
 }

 function QuickSortDemo(arr) {
  var st = new Date();
  var result = QuickSort(arr);
  status = (new Date() - st) + ' ms';
  return result;
 }

 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;
 }
 
 /*function Partition(arr, i, j) { //快速排序, 对待排序的数组进行划分
  var pivot = arr[i];
  while(i<j) {
   while(arr[j]>=pivot)
    j--;
   if(i<j)
    arr[i++] = arr[j];
   while(arr[i]<=pivot)
    i++;
   if(i<j)
    arr[j--] = arr[i];
  }
  arr[i] = pivot;
  return arr;
 }*/

 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;
 }
 

 function unicode(str) {//求字符串的unicode码
  var uni=0;
  for(var i=0; i<str.length; i++){
   uni += str.charCodeAt(i)/6553.5 * Math.pow(10, str.length-i);
  }
  return uni;
 }
</script>

时间： 2024-09-28 13:20:28

javascript 的几种排序方法的相关文章

&amp;#106avascript 的几种排序方法

排序|排序 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来.其确切定义如下: 输入:n个记录R1,R2,-,Rn,其相应的关键字分别为K1,K2,-,Kn. 输出:Ril,Ri2,-,Rin,使得Ki1≤Ki2≤-≤Kin.(或Ki1≥Ki2≥-≥Kin). 这里,我们简单介绍几种排序方法,直接插入排序.希儿排序.冒泡排序.快速排序.直接选择排序,文中所提及的代码在IE6下测试通过. 直接插入排序基本思想 假设待排序的记录存放在数组R[1..n]中.初始时,R[1]自成

TreeSet的两种排序方法

TreeSet的两种排序方法:自然排序和定义比较器,推荐使用定义比较器方法. [java] view plain copy  print? <span style="color:#333333;">import java.util.*;   class treeset    {       public static void main(String[] args)        {           TreeSet t = new TreeSet();   //    

c-指针数组两种排序方法结果大相径庭，求大神指导

问题描述 指针数组两种排序方法结果大相径庭,求大神指导 #include #include int main() { void rankArr(char *pr[]); char *p[]={"china","japan","tokyo","pairs","narry"}; int i; for(i=0;i printf("%sn",p[i]); rankArr(p); for(i=0;

三种排序方法

   今天想给大家分享三种排序方法:选择排序,直接排序,还有冒泡排序,对于这些排序方法,我的感觉是有些模糊,也对比了一下,不是很懂直接排序法,如果有懂得,给我讲一下.这几个方法主要是排序,有的不重复,有的重复.          方法一:选择排序法 Option Explicit Option Base 1 Private Sub cmdsort_Click()                    Dim a(10) As Integer, temp As Integer           

javascript的几种继承方法介绍_基础知识

1.原型链继承:构造函数.原型和实例的关系:每个构造函数都有一个原型对象,原型对象都包含一个指向构造函数的指针,而实例都包含一个指向原型对象的内部指针.确认原型和实例之间的关系用instanceof. 原型链继承缺点:字面量重写原型会中断关系,使用引用类型的原型,并且子类型还无法给超类型传递参数 function Parent(){ this.name='mike'; } function Child(){ this.age=12; } //儿子继承父亲(原型链) Child.prototype

JavaScript中几种排序算法的简单实现_基础知识

排序算法的实现 我的JS水平就是渣渣,所以我就用类似于JAVA和C的方式来写JavaScript的排序算法了. 而且这里我不讲算法原理,仅仅只是代码实现,可能会有Bug,欢迎大家博客评论指导.插入排序 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排

C语言常用的三种排序方法总结与探讨

排序是程序设计中非常重要的内容,它的功能是将一组无序的的数据,排列成有序的数据序列,经过排列后的数据,要么是从大到小排列,要么是从小到大排列.一般也只有这两种情况. 例如我们统计班级学生的成绩,那么一般是按照学号来进行统计,原来成绩是无序排列的,这样的话非常不适合于我们对成绩的查询,那么一般我们进行成绩查询之前,先进行排序,如按照高分到低分的排序,这样可以很快地查出本班的最高分和最低分,和成绩比较靠前或靠后的学生. 排序有很多种方法,常用的有三种:冒泡排序.选择排序.插入排序等,下面我们就对这三

PHP中数组的三种排序方法分享_php技巧

一.冒泡排序法 说明:找到最大的数,排列到最后面,然后继续找 例: 复制代码 代码如下: $arr = array(3,5,-1,0,2); for($i=0;$i<count($arr)-1;$i++){ for($j=0;$j<count($arr)-1-$i;$j++){ if($arr[$j]>$arr[$j+1]){ $temp = $arr[$j]; $arr[$j]=$arr[$j+1]; $arr[$j+1]=$temp; } } } 理解: 3,5,-1,0,2 //从

JavaScript 冒泡排序和选择排序的实现代码_javascript技巧

废话不多说了,直接给大家贴代码了,具体代码如下所述: var array = [1,2,3,4,5]; // ---> 服务 //效率 ---> 针对一个有序的数组 效率最高 //标志 true false for(var j = 0; j < array.length - 1;j++ ){ //- j 每次排序完成之后 后面减少比较的次数 var isTrue = true; //如果数组本身就是升序,则直接输出 for(var i = 0; i < array.length -