当前位置： 移动技术网 > IT编程>开发语言>JavaScript > JavaScript数据结构与算法之基本排序算法定义与效率比较【冒泡、选择、插入排序】

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

2019年05月28日  | 移动技术网IT编程  | 我要评论

乔绍恒个人资料,迅雷综合下载,石家庄铁道大学四方学院怎么样

本文实例讲述了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.");

运行结果：

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

感兴趣的朋友可以使用在线html/css/javascript代码运行工具：测试上述代码运行效果。

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

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：

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

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

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网