JS折半插入排序算法实例

本文实例讲述了JS折半插入排序算法。分享给大家供大家参考，具体如下：

function pushArrayWithIndex(arr, index, value) { // 将元素添加到数组的指定位置
  var temArr = arr.slice(0, index);
  temArr.push(value);
  return temArr.concat(arr.slice(index));
}
/* test for pushArrayWithIndex
var arr = [1, 2, 3, 4, 5];
arr = pushArrayWithIndex(arr, 1, 9);
console.log(arr);*/
function sortInsert(arr) { // 插入排序
  var temArr = []; // 临时数组，存储已排序项
  function getSortTmpIndex(subArr, num) {
    var len = subArr.length;
    if(0 == len) return 0; // 当数组为空时，返回最开始位置
    var cpmIndex = Math.ceil(len / 2); // 计算中间元素所在位置
    if(cpmIndex > len - 1) cpmIndex = len - 1;
    if(num == subArr[cpmIndex]) { // 相等时直接返回
      return cpmIndex;
    }
    if(num > subArr[cpmIndex]) { // 向后折半查找
      cpmIndex++;
      return cpmIndex + getSortTmpIndex(subArr.slice(cpmIndex), num);
    }
    if(num < subArr[cpmIndex]) { // 向前折半查找
      return getSortTmpIndex(subArr.slice(0, cpmIndex), num);
    }
  }
  for (var i in arr) {
    var index = getSortTmpIndex(temArr, arr[i]); // 查找arr[i]在temArr中的位置
    console.log('index:', index, ' num:', arr[i], ' arr:', temArr);
    temArr = pushArrayWithIndex(temArr, index, arr[i]); // 将元素插入到查找位置
  }
  return temArr;
}
var arr = [3, 7, 6, 5, 9, 1, 2, 3, 1, 7, 4];
console.log(arr);
arr = sortInsert(arr);
console.log(arr);

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

赞 (0)

相关推荐

  • JavaScript中几种常见排序算法小结

    说明 写这个主要是为了锻炼自己,并无实际意义. 每个浏览器测试得出的数据会不一样.比如我用chrome 测试 一般快速排序都会最快,IE 则根据数组长度有可能希尔最快. 不要用太大数据去测试冒泡排序(浏览器崩溃了我不管) 如果有兴趣可以 下载测试页面 个人理解 冒泡排序:最简单,也最慢,貌似长度小于7最优 插入排序: 比冒泡快,比快速排序和希尔排序慢,较小数据有优势 快速排序:这是一个非常快的排序方式,V8的sort方法就使用快速排序和插入排序的结合 希尔排序:在非chrome下数组长度小于10

  • js三种排序算法分享

    复制代码 代码如下: /** * 值交换操作 * arr 被操作的数组 * i 被操作元素索引值 * j 被操作两元素的距离 */ function refer(arr, i, j){ var change = (arr[i] - arr[i - j]) < 0 ? true : false, value; if (change) { value = arr[i]; arr[i] = arr[i - j]; arr[i - j] = value; return arguments.callee(

  • javascript算法学习(直接插入排序)

    1.基本思想 假设待排序的记录存放在数组R[1..n]中.初始时,R[1]自成1个有序区,无序区为R[2..n].从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区. 复制代码 代码如下: <!doctype html> <html> <head><title>javascript直接插入排序</title> <meta charset = "utf-8" /> &

  • JavaScript实现链表插入排序和链表归并排序

    本篇文章详细的介绍了JavaScript实现链表插入排序和链表归并排序,链表的归并排序就是对每个部分都进行归并排序,然后合并在一起. 1.链表 1.1链表的存储表示 //链表的存储表示 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; 1.2基本操作 创建链表: /* * 创建链表. * 形参num为链表的长度,函数返回链表的头指针. */ Link

  • js算法中的排序、数组去重详细概述

    其实在js中实现数组排序,采用数组中sort方法实现还是比较简单的: 一.排序 简单实现数组排序 复制代码 代码如下: var arr = [];  for(var i=0;i<20;i++){      arr.push(Math.floor(Math.random()*100))  }  arr.sort(function(a,b){      return a>b?1:-1;  })  alert(arr) 不能简单使用sort方法,默认情况下 sort方法是按ascii字母顺序排序的,

  • JavaScript实现经典排序算法之插入排序

    插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂.像排序一手扑克牌,开始时,我们的左手为空并且桌子上的牌面向下.然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置.为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较,拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌. 1)算法原理 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序

  • JS实现冒泡排序，插入排序和快速排序并排序输出

    JS实现冒泡排序，插入排序和快速排序并排序输出

    在一次面试中被问到了此问题,但是真是懵了,没能回答上来,后来通过JS整理了一下,在结合html代码做了一个文本框,把输入的内容从文本框排序输出,再次不做叙述了,下面通过一段代码给大家展示下: 以下是代码: index.html <!DOCTYPE html> <html> <head> <title>Sorting</title> <link rel="stylesheet" type="text/css&qu

  • 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">

  • js排序动画模拟-插入排序

    0 && (t > 0; } //--> [Ctrl+A 全选 注:如需引入外部Js需刷新才能执行]

  • 基于JavaScript实现的插入排序算法分析

    基于JavaScript实现的插入排序算法分析

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

  • 学习javascript，实现插入排序实现代码

    插入排序 插入排序是这样实现的: 首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表"). 从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态. 重复2号步骤,直至原数列为空. 插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现.它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度. (引自百度百科) javascript代码 复制代码 代码如下: <script ty

  • js交换排序 冒泡排序算法（Javascript版）

    比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. function sort(elements){ for(var i=0;i<elements.length-1;i++){ for(var j=0;j<elements.length-i-1;j++){ if(elemen

  • javascript数据结构之双链表插入排序实例详解

    本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t

随机推荐