资讯专栏INFORMATION COLUMN

算法笔记(JavaScript版)——排序

ctriptech / 787人阅读

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

算法笔记(JavaScript版)——排序 本文内容根据Rebert Sedgewick和Kevin Wayne的《算法(第四版)》整理,原代码为java语言,自己修改为JavaScript版本,仅供参考。 排序算法模版
function sort(arr){
  //此处添加不同的排序算法实现
}
//比较两个数的大小
function less(a, b){
  return a < b
} 
//交换数组中两个数的位置
function exch(arr, i, j){
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
//判断数组是否是有序的
function isSorted(arr){
  var len = arr.length;
  for(var i = 1; i < len; i++){
    if(less(arr[i], arr[j])){
      return false;
    }
  }
  return true;
}

选择排序

对于长度为N的数组,选择排序需要大约(N^2/2)次比较和N次交换

运行时间和输入无关(仅与输入的长度有关)

数据移动是最少的

function selectionSort(arr){
  var len = arr.length;
  for(var i = 0; i < len; i++){
    var min = i;
    for(var j = i+1; j < len; j++){
      if(less(arr[j], arr[min])){
        min = j;
      }      
    }
    exch(arr, i, min)
  }
}

插入排序

插入排序所需的时间依赖于输入中元素的初始顺序。

对于随机排列的长度为N且主键不重复的数组,平局情况下插入排序需要~(N^2/4)次比较和~(N^2/4)次交换。最坏情况下需要~(N^2/2)次比较和~(N^2/4)次交换,最好情况下需要(N-1)次比较和0次交换。

插入排序对于部分有序的数组很有效,下面是几种典型的部分有序的数组:

数组中每个元素距离它最终的位置都不远。

一个有序的大数组接一个小数组。

数组中只有几个元素的位置不正确。

function insertionSort(arr){
  var len = arr.length;
  for(var i = 1; i < len; i++){
    for(var j = i; j > 0; j--){
      if(less(arr[j], arr[j-1])){
        exch(arr, j, j-1)
      }
    }
  }
}

希尔排序

希尔排序是基于插入排序的快速排序算法。

希尔排序的思想是:使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。在进行排序时,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便。

使用递增序列1,4,13,40,121,364…的希尔排序所需的比较次数不会超过N的若干倍乘以递增序列的长度。

function shellSort(arr){
  var len = arr.length,
      h = 1;
  while(h < len/3){
    h = 3*h+1;
  }
  while(h >=1){
    for(var i = h; i < len; i++){
      for(var j = i; j >= h; j-=h){
        if(less(arr[j], arr[j-h])){
          exch(arr, j, j-h)
        }
      }
    }
    h = (h-1)/3;
  }
}

归并排序

要将一个数组排序,可以先(递归地)将它分成两半分别排序,然后将结果归并起来。

归并排序最吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比,主要缺点是它所需的额外空间和N成正比。

//原地归并的抽象方法
function merge(arr, lo, mid, hi){
  var aux = [],
      i = lo,
      j = mid+1;
  for(var k = lo; k <= hi; k++){
    aux[k] = arr[k]
  }
  
  for(var m = lo; m <= hi; m++){
    if(i > mid){
      arr[m] = aux[j++];
    }else if(j > hi){
      arr[m] = aux[i++];
    }else if(less(aux[j], aux[i])){
      arr[m] = aux[j++];
    }else{
      arr[m] = aux[i++];
    }
  }  
}
//自顶向下的归并排序
function mergeSort(arr, lo, hi){
  if(hi <= lo){
    return;
  }
  var mid = Math.floor(lo + (hi - lo)/2);
  mergeSort(arr, lo, mid);
  mergeSort(arr, mid+1, hi);
  merge(arr, lo, mid, hi);
}

对于长度为N的任意数组,自顶向下的归并排序需要(1/2)NlgNNlgN次比较。

对于长度为N的任意数组,自顶向下的归并排序最多需要访问数组6NlgN次。

通过一些细致的思想可以大幅度缩短归并排序的运行时间:

对小规模子数组使用插入排序

测试数组是否已经有序

不将元素复制到辅助数组

//自底向上的归并排序
function mergeSortBU(arr){
  var len = arr.length;
  for(var sz = 1; sz < len; sz = sz+sz){
    for(var lo = 0; lo < len-sz; lo += sz+sz){
      merge(arr, lo, lo+sz-1, Math.min(lo+sz+sz-1, len-1));
    }
  }
}

对于长度为N的任意数组,自底向上的归并排序需要(1/2)NlgNNlgN次比较,最多访问数组6NlgN次。

当数组长度为2的幂时,自顶向下和自底向上的归并排序所用的比较次数和数组访问次数相同,其他时候两种方法的比较和数组访问次序会有所不同。

自底向上的归并排序比较适合用链表组织的数据。

快速排序

快速排序是一种分治的排序算法。

将长度为N的无重复数组排序,快速排序平均需要(~2NlnN)次比较(以及1/6的交换)

快速排序最多需要约(N^2/2)次比较,但随机打乱数组能够预防这种情况。

//快速排序
function quickSort(arr, lo, hi){
  if(hi <= lo){
    return;
  }
  var j = partition(arr, lo, hi);
  quickSort(arr, lo, j-1);
  quickSort(arr, j+1, hi);
}
//快速排序的切分
function partition(arr, lo, hi){
  var i = lo,
      j = hi + 1,
      v = arr[lo];
  while(true){
    while(less(arr[++i], v)){
      if(i === hi){
        break;
      }
    }
    while(less(v, arr[--j])){
      if(j === lo){
        break;
      }
    }
    if(i >= j){
      break;
    }
    exch(arr, i, j);
  }
  exch(arr, lo, j);
  return j;    
}

快速排序改进方法:

切换到插入排序

//快速排序
function quickSort(arr, lo, hi){
  //if(hi <= lo){
  //  return;
  //}
  if(hi <= lo + M){
  //转换参数M的最佳值与系统相关
  //大多数情况下5~15之间的任意值都能令人满意
    insertionSort(arr, lo, hi);
    return;
  }
  var j = partition(arr, lo, hi);
  quickSort(arr, lo, j-1);
  quickSort(arr, j+1, hi);
}

三取样切分,使用子数组的一小部分元素的中位数来切分数组

熵最优的排序

对于存在大量重复元素的数组,三向切分的快速排序比标准的快速排序的效率高得多。

对于大小为N的数组,三向切分的快速排序需要~(2ln2)NH次比较,其中H为由主键值出现频率定义的香农信息量。

//三向切分的快速排序
function quick3WaySort(arr, lo, hi){
  if(hi <= lo){
    return;
  }
  var lt = lo,
      i = lo + 1,
      gt = hi;
  var v = arr[lo];
  while(i <= gt){
    if(less(arr[i], v)){
      //arr[i]小于v时,交换arr[lt]和arr[i],将lt和i加1
      exch(arr, lt++, i++);
    }else if(less(v, arr[i])){
      //arr[i]大于v时,交换arr[i]和arr[gt],将gt减1
      exch(arr, i, gt--);
    }else{
      //arr[i]等于v时,将i加1
      i++;
    }
  }
  quick3WaySort(arr, lo, lt-1);
  quick3WaySort(arr, gt+1, hi);
}

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

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

相关文章

  • javaScript排序算法学习笔记

    摘要:排序算法学习笔记用于创建数组冒泡排序冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们。归并排序归并排序是一种分治算法。完成下列操作的前提是数组均已经完成。 javaScript排序算法学习笔记 // 用于创建数组 function createNonSortedArray(size) { var array = new ArrayList(); for( ...

    lentoo 评论0 收藏0
  • JavaScript学习笔记 - 基础排序算法

    摘要:本文记录了我在学习前端上的笔记,方便以后的复习和巩固。冒泡排序算法步骤比较相邻的元素。这步做完后,最后的元素会是最大的数。重复第二步,直到所有元素均排序完毕。得到序列第二趟,,和进行交换。 本文记录了我在学习前端上的笔记,方便以后的复习和巩固。推荐大家去看看这一本gitBook上的书十大经典排序算法本文就是看这本书记录的笔记。 冒泡排序 1.算法步骤 1.比较相邻的元素。如果第一个比第...

    mindwind 评论0 收藏0
  • 优秀程序员都应该学习的 GitHub 上开源的数据结构与算法项目

    摘要:强烈推荐上值得前端学习的数据结构与算法项目,包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构,提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法为王。想学好前端,先练好内功,内功不行,就算招式练的再花哨,终究成不了高手;只有内功深厚者,前端之路才会走得...

    cheukyin 评论0 收藏0
  • 【程序员必备】知识点 持续更新

    TCP/IP HTTP和HTTPS有何区别? httpbin 一个简单的HTTP请求和响应服务。 TCP的三次握手与四次挥手 通俗易懂版,详细版本 MySQL CHAR和VARCHAR存取的差别 《高性能MySQL》笔记 - MySQL 锁的基本类型 MySQL中的锁之一:锁的必要性及分类 MySQL中的锁之二:行锁、页锁、表锁 MySQL Like与Regexp的区别 数据结构 数...

    hellowoody 评论0 收藏0

发表评论

0条评论

ctriptech

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<