蝙蝠岛资源网

JavaScript数据结构与算法之基本排序算法定义与效率比较【冒泡、选择、插入排序】
网络编程 2024/12/31 佚名
2 0
蝙蝠岛资源网 Design By www.hbtsch.com

本文实例讲述了JavaScript数据结构与算法之基本排序算法定义与效率比较。分享给大家供大家参考，具体如下：

javascript数据结构与算法--基本排序算法（冒泡、选择、排序）及效率比较

一、数组测试平台

javascript数据结构与算法--基本排序（封装基本数组的操作），封装常规数组操作的函数，比如：插入新数据，显示数组数据，还有交换数组元素等操作来调用不同的排序算法

function CArray(numElements) {
  this.dataStore = [];
  this.pos = 0;//是一个索引值，默认为0，从第一个开始
  this.numElements = numElements;//是保存所有的数组元素
  this.insert = insert;//向数组中插入一个元素的方法
  this.toString = toString;//显示数组中所有元素
  this.clear = clear;//清空数组数据
  this.setData = setData;//生成了存储在数组中的随机数字
  this.swap = swap;//交换数组中两个元素的位置
  this.bubbleSort = bubbleSort;
  /*将传入的数组，存储在datastore中*/
  for (var i = 0; i < numElements.length; ++i) {
    this.dataStore[i] = numElements[i];
  }
}
function setData() {
  for (var i = 0; i < this.numElements; ++i) {
    this.dataStore[i] = Math.floor(Math.random() *
      (this.numElements+1));
  }
}
function clear() {
  for (var i = 0; i < this.dataStore.length; ++i) {
    this.dataStore[i] = 0;
  }
}
function insert(element) {
  this.dataStore[this.pos++] = element;
}
function toString() {
  var retstr = "";
  for (var i = 0; i < this.dataStore.length; ++i) {
    retstr += this.dataStore[i] + " ";
    if (i > 0 && i % 10 == 0) {
      retstr += "\n";
    }
  }
  return retstr;
}
function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}
//测试生成一组数组数据（随机数）
var numElements = 100;
var myNums = new CArray(numElements);
myNums.setData();
console.log(myNums.toString());

17 94 81 80 25 24 73 76 24 35 81
63 81 59 4 76 30 47 73 98 18
54 36 53 47 22 60 88 41 66 24
73 94 40 45 72 74 14 61 92 48
36 12 42 11 12 82 24 84 60 1
17 98 63 36 84 13 18 50 89 26
98 1 6 54 52 69 6 52 98 14
79 28 19 69 76 99 97 100 10 7
24 54 81 73 18 21 45 73 66 30
28 56 54 21 88 31 20 86 48

二、冒泡排序算法

我们先来了解一下冒泡排序算法，它是最慢的排序算法之一，但也是一种最容易实现的排序算法。

之所以叫冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂浮到另一端。

假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。

之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换。

JS代码如下：

function CArray(numElements) {
  this.dataStore = [];
  this.pos = 0;//是一个索引值，默认为0，从第一个开始
  this.numElements = numElements;//是保存所有的数组元素
  this.insert = insert;//向数组中插入一个元素的方法
  this.toString = toString;//显示数组中所有元素
  this.clear = clear;//清空数组数据
  this.setData = setData;//生成了存储在数组中的随机数字
  this.swap = swap;//交换数组中两个元素的位置
  this.bubbleSort = bubbleSort;//冒泡算法
  /*将传入的数组，存储在datastore中*/
  for (var i = 0; i < numElements.length; ++i) {
    this.dataStore[i] = numElements[i];
  }
}
function setData() {
  for (var i = 0; i < this.numElements; ++i) {
    this.dataStore[i] = Math.floor(Math.random() *
      (this.numElements+1));
  }
}
function clear() {
  for (var i = 0; i < this.dataStore.length; ++i) {
    this.dataStore[i] = 0;
  }
}
function insert(element) {
  this.dataStore[this.pos++] = element;
}
function toString() {
  var retstr = "";
  for (var i = 0; i < this.dataStore.length; ++i) {
    retstr += this.dataStore[i] + " ";
    if (i > 0 && i % 10 == 0) {
      retstr += "\n";
    }
  }
  return retstr;
}
function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}
function bubbleSort() {
  var numElements = this.dataStore.length;
  for (var outer = numElements; outer >= 2; --outer) {
    for (var inner = 0; inner <= outer-1; ++inner) {
      if (this.dataStore[inner] > this.dataStore[inner+1]) {
        swap(this.dataStore, inner, inner+1);
      }
    }
    console.log("outer为" + outer + ": " + this.toString());
  }
}
//测试冒泡排序算法
var numElements = [2,4,1,3];
var myNums = new CArray(numElements);
console.log("原来的数组："+myNums.toString());
myNums.bubbleSort();
console.log("排序后的数组："+myNums.toString());

冒泡算法代码分析如下：

原先数组为 [2,4,1,3];

1. outer为4的时候

    1. inner为0，值为2，inner+1为1，值为4，不符合，不交换。
    2. inner为1，值为4，inner+1为2，值为1，交换，数组变为[2,1,4,3]
    3. inner为2，值为4，inner+1为3，值为3，交换 数组变为[2,1,3,4]
    4. inner为3，值为4，inner+1为4，不符合 不交换。

2. outer为3的时候

    1. inner为0，值为2，inner+1为1，值为1,交换 数组变为[1,2,3,4]
    2. inner为1, 值为2，inner+1为2，值为3 不符合 不交换。
    3. inner为2, 值为3，inner+1为3，值为4，不符合 不交换。

再下面继续循环都不符合条件，所以如上就是最后一步了。这就是冒泡排序。

三、选择排序算法

选择排序从数组的开头开始，将第一个元素和其他元素进行比较。

检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。

这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。
选择排序会用到嵌套循环。

外循环从数组的第一个元素移动到倒数第二个元素；

内循环从第二个数组元素移动到最后一个元素，查找比当前外循环所指向的元素小的元素。

每次内循环迭代后，数组中最小的值都会被赋值到合适的位置。

JS代码如下：

function CArray(numElements) {
  this.dataStore = [];
  this.pos = 0;//是一个索引值，默认为0，从第一个开始
  this.numElements = numElements;//是保存所有的数组元素
  this.insert = insert;//向数组中插入一个元素的方法
  this.toString = toString;//显示数组中所有元素
  this.clear = clear;//清空数组数据
  this.setData = setData;//生成了存储在数组中的随机数字
  this.swap = swap;//交换数组中两个元素的位置
  this.selectionSort = selectionSort;//选择排序算法
  /*将传入的数组，存储在datastore中*/
  for (var i = 0; i < numElements.length; ++i) {
    this.dataStore[i] = numElements[i];
  }
}
function setData() {
  for (var i = 0; i < this.numElements; ++i) {
    this.dataStore[i] = Math.floor(Math.random() *
      (this.numElements+1));
  }
}
function clear() {
  for (var i = 0; i < this.dataStore.length; ++i) {
    this.dataStore[i] = 0;
  }
}
function insert(element) {
  this.dataStore[this.pos++] = element;
}
function toString() {
  var retstr = "";
  for (var i = 0; i < this.dataStore.length; ++i) {
    retstr += this.dataStore[i] + " ";
    if (i > 0 && i % 10 == 0) {
      retstr += "\n";
    }
  }
  return retstr;
}
function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}
function selectionSort() {
  var min, temp;
  for (var outer = 0; outer <= this.dataStore.length-2; ++outer) {
    min = outer;
    for (var inner = outer + 1;inner <= this.dataStore.length-1; ++inner) {
      if (this.dataStore[inner] < this.dataStore[min]) {
        min = inner;
      }
    }
    swap(this.dataStore, outer, min);
    console.log("第"+outer +"次："+myNums.toString());
  }
}
//测试排序算法
var numElements = [2,4,1,3];
var myNums = new CArray(numElements);
console.log("原来的数组："+myNums.toString());
myNums.selectionSort();
console.log("排序后的数组："+myNums.toString());

原来的数组：2 4 1 3
第0次：1 4 2 3
第1次：1 2 4 3
第2次：1 2 3 4
排序后的数组：1 2 3 4

四、插入排序算法

插入排序有两个循环。

外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它前面的那个元素进行比较。

如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为外循环中的这个元素腾出位置

function CArray(numElements) {
  this.dataStore = [];
  this.pos = 0;//是一个索引值，默认为0，从第一个开始
  this.numElements = numElements;//是保存所有的数组元素
  this.insert = insert;//向数组中插入一个元素的方法
  this.toString = toString;//显示数组中所有元素
  this.clear = clear;//清空数组数据
  this.setData = setData;//生成了存储在数组中的随机数字
  this.swap = swap;//交换数组中两个元素的位置
  this.insertionSort = insertionSort;//插入排序算法
  /*将传入的数组，存储在datastore中*/
  for (var i = 0; i < numElements.length; ++i) {
    this.dataStore[i] = numElements[i];
  }
}
function setData() {
  for (var i = 0; i < this.numElements; ++i) {
    this.dataStore[i] = Math.floor(Math.random() *
      (this.numElements+1));
  }
}
function clear() {
  for (var i = 0; i < this.dataStore.length; ++i) {
    this.dataStore[i] = 0;
  }
}
function insert(element) {
  this.dataStore[this.pos++] = element;
}
function toString() {
  var retstr = "";
  for (var i = 0; i < this.dataStore.length; ++i) {
    retstr += this.dataStore[i] + " ";
    if (i > 0 && i % 10 == 0) {
      retstr += "\n";
    }
  }
  return retstr;
}
function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}
function insertionSort() {
  var temp, inner;
  //外循环将数组元素挨个移动
  for (var outer = 1; outer <= this.dataStore.length-1; ++outer) {
    temp = this.dataStore[outer];//外循环选中的元素temp
    inner = outer;
    //内循环对外循环中选中的元素temp与temp前面的元素一个个进行比较。
    //如果外循环中选中的元素temp比内循环中选中的元素小，那么数组元素会向右移动，为外循环中的这个元素腾出位置
    while (inner > 0 && (this.dataStore[inner-1] >= temp)) {
      this.dataStore[inner] = this.dataStore[inner-1];
      --inner;
    }
    this.dataStore[inner] = temp;
    console.log("第"+outer+"次："+myNums.toString());
  }
}
//测试排序算法
var numElements = [9,1,8,6,2,3,5,4];
var myNums = new CArray(numElements);
console.log("原来的数组："+myNums.toString());
myNums.insertionSort();
console.log("排序后的数组："+myNums.toString());

原来的数组：9 1 8 6 2 3 5 4 //先用1和1前面的对比，9比1大，所以9向右移动一个位置，给1腾位置
      第1次：1 9 8 6 2 3 5 4 //用8与8前面的对比，9比8大，所以9向右移动一个位置，给8腾位置
      第2次：1 8 9 6 2 3 5 4 //用6与6前面的对比,8，9比6大，所以8、9向右移动一个位置，给6腾位置
      第3次：1 6 8 9 2 3 5 4
      第4次：1 2 6 8 9 3 5 4
      第5次：1 2 3 6 8 9 5 4
      第6次：1 2 3 5 6 8 9 4
      第7次：1 2 3 4 5 6 8 9
排序后的数组：1 2 3 4 5 6 8 9

五、基本排序算法的效率比较

function CArray(numElements) {
  this.dataStore = [];
  this.pos = 0;//是一个索引值，默认为0，从第一个开始
  this.numElements = numElements;//是保存所有的数组元素
  this.insert = insert;//向数组中插入一个元素的方法
  this.toString = toString;//显示数组中所有元素
  this.clear = clear;//清空数组数据
  this.setData = setData;//生成了存储在数组中的随机数字
  this.swap = swap;//交换数组中两个元素的位置
  this.bubbleSort = bubbleSort;//冒泡排序算法
  this.selectionSort = selectionSort;//选择排序算法
  this.insertionSort = insertionSort;//插入排序算法
  /*将传入的数组，存储在datastore中*/
  for (var i = 0; i < numElements.length; ++i) {
    this.dataStore[i] = numElements[i];
  }
}
function setData() {
  for (var i = 0; i < this.numElements; ++i) {
    this.dataStore[i] = Math.floor(Math.random() *
      (this.numElements+1));
  }
}
function clear() {
  for (var i = 0; i < this.dataStore.length; ++i) {
    this.dataStore[i] = 0;
  }
}
function insert(element) {
  this.dataStore[this.pos++] = element;
}
function toString() {
  var retstr = "";
  for (var i = 0; i < this.dataStore.length; ++i) {
    retstr += this.dataStore[i] + " ";
    if (i > 0 && i % 10 == 0) {
      retstr += "\n";
    }
  }
  return retstr;
}
function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}
function bubbleSort() {
  var numElements = this.dataStore.length;
  for (var outer = numElements; outer >= 2; --outer) {
    for (var inner = 0; inner <= outer-1; ++inner) {
      if (this.dataStore[inner] > this.dataStore[inner+1]) {
        swap(this.dataStore, inner, inner+1);
      }
    }
//    console.log("outer为" + outer + ": " + this.toString());
  }
}
function selectionSort() {
  var min, temp;
  for (var outer = 0; outer <= this.dataStore.length-2; ++outer) {
    min = outer;
    for (var inner = outer + 1;inner <= this.dataStore.length-1; ++inner) {
      if (this.dataStore[inner] < this.dataStore[min]) {
        min = inner;
      }
    }
    swap(this.dataStore, outer, min);
//    console.log("第"+outer +"次："+this.toString());
  }
}
function insertionSort() {
  var temp, inner;
  //外循环将数组元素挨个移动
  for (var outer = 1; outer <= this.dataStore.length-1; ++outer) {
    temp = this.dataStore[outer];//外循环选中的元素
    inner = outer;
    //内循环则对外循环中选中的元素与它前面的那个元素进行比较。
    //如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为外循环中的这个元素腾出位置
    while (inner > 0 && (this.dataStore[inner-1] >= temp)) {
      this.dataStore[inner] = this.dataStore[inner-1];
      --inner;
    }
    this.dataStore[inner] = temp;
//    console.log("第"+outer+"次："+this.toString());
  }
}
/*测试冒泡、选择、插入算法的效率*/
var numElements = 10000;
var nums = new CArray(numElements);
nums.setData();
var start = new Date().getTime();
nums.bubbleSort();
var stop = new Date().getTime();
var elapsed = stop - start;
console.log("用冒泡算法，排序 " + numElements + " 个元素耗时 : " + elapsed + " milliseconds.");
start = new Date().getTime();
nums.selectionSort();
stop = new Date().getTime();
elapsed = stop - start;
console.log("用选择算法，排序 " + numElements + " 个元素耗时: " + elapsed + " milliseconds.");
start = new Date().getTime();
nums.insertionSort();
stop = new Date().getTime();
elapsed = stop - start;
console.log("用插入算法，排序 " + numElements + " 个元素耗时: " + elapsed + " milliseconds.");

运行结果：

JavaScript数据结构与算法之基本排序算法定义与效率比较【冒泡、选择、插入排序】

选择排序和插入排序要比冒泡排序快，插入排序是这三种算法中最快的。

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

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

标签：
JavaScript,数据结构与算法,基本排序算法,效率比较,冒泡,选择,插入排序
蝙蝠岛资源网 Design By www.hbtsch.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
蝙蝠岛资源网 Design By www.hbtsch.com

评论“JavaScript数据结构与算法之基本排序算法定义与效率比较【冒泡、选择、插入排序】”

暂无JavaScript数据结构与算法之基本排序算法定义与效率比较【冒泡、选择、插入排序】的评论...
www.hbtsch.com 蝙蝠岛资源网
139,976影音资源
144,792福利资源
21,817软件资源
631,128技术资源
一句话新闻
一口气升级7个大模型SaaS应用，百度智能云：突出一个“开箱即用” - 2024/12/31

这一波大模型产业落地浪潮里，不少企业其实处在 “干瞪眼“的状态。

一种情况是，很多大模型产品看得见却摸不着，在台上一个个遥遥领先——今天Sora技精四座，明天英伟达的机器人又赢得满堂彩，可是到了台下一问：啥时候能用上啊？答曰：遥遥无期。

另一种情况是，企业想用上大模型，却又难免瞻前顾后——既要考虑场景融合，又得兼顾安全性，还要考虑打通现有系统，再加上各种部署成本和繁琐的采购流程……最后只能拂袖：罢了，再等等吧。

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

昨天有一位朋友在大神群里分享，自己亚服账号被封号之后居然弹出了国服的封号信息对话框。

这里面让他访问的是一个国服的战网网址，com.cn和后面的zh都非常明白地表明这就是国服战网。

而他在复制这个网址并且进行登录之后，确实是网易的网址，也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情，因为以前都没有出现这样的情况，现在突然提示跳转到国服战网的网址，是不是说明了简体中文客户端已经开始进行更新了呢？

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接
蝙蝠岛资源网 Design By www.hbtsch.com