从开始排序算法之前，我们先创建一个方法用来生成原数组（指要被排序的数组）
我要评论function ArrayList() {
var array = []; // {1}
this.insert = function(item) { // {2}
array.push(item);
}
this.toString = function() { // {3}
return array.join();
}
ArrayList是一个简单的数据结构，它将项储存在数组中(行 { 1 })。只需要向ArrayList里插入一个insert方法来向数据结构中添加元素(行{ 2 }），用array.push方法像数组中添加元素,最后用join方法来拼接数组中的所有元素来生成一个单一的字符串，方便在浏览器的控制台打印结果。
冒泡排序：时间复杂度为O(n^2)
比较任意两个相邻的项,如果第一个比第二个大,则交换它们,元素向上移动至正确的顺序,就好像气泡升至表面上一样。
冒泡排序是排序算法中最简单的，然而，从运行事件的角度来看，冒泡排序是最差的一个, 首先我们来讲解一下思路吧:
function ArrayList() {
var array = []
this.insert = function(item) {
array.push(item)
}
this.toString = function() {
return array.join()
}
/**
* 冒泡排序
*/
this.bubbleSort = function() {
var length = array.length; //{1}
for (var i = 0; i < length; i++) { //{2}
for (var j = 0; j < length - 1; j++) { //{3}
if (array[j] > array[j + 1]) { //{4}
[array[j], array[j + 1]] = [array[j + 1], array[j]]; //{5}
}
}
}
}
}
这里为了让大家熟悉面向对象开发,所以选用了在构造函数里扩展方法的形式来编写代码
首先如行{ 1 }, 先声明一个名为length的变量,用来储存数组的长度;
接着如行{ 2 }, 从数组的第一位迭代至最后一位,他控制了在数组中经过多少轮排序(应该是数组中每项都经过一轮,轮数和数组的长度一致);
然后如行{ 3 }, 内循环从第一位迭代至倒数第二位, 因为内循环就不用和自己比较了直接与下一项比较, 所以遍历会少一位。
再如行{ 4 }, 内循环进行当前项与下一项的比较,如果当前项比下一项大,则交换它们 ( 如行{ 5 } )。
行{ 5 } 用到了ES6的解构赋值, 也可以封装一个函数来实现交换数组中的元素
如下:
function swap(array, index1, index2) {
var aux = array[index1];
array[index2] = array[index1];
array[index1] = aux;
}
*改进:
比如: 当外循环i=0; 第一个元素经过内循环找到了自己的对应位置, 那么i=1时, 就不必再去循环它了, 但上面的代码, 内循环还是把所有的项都遍历一遍, 显然是需要改进的。
this.modifiedBubbleSort = function() {
var length = array.length; //{1}
for (var i = 0; i < length; i++) { //{2}
for (var j = 0; j < length - 1 - i; j++) { //{3}
if (array[j] > array[j + 1]) { //{4}
swap(array, j, j+1) //{5}
}
}
}
}
在行{ 3 }中, 我们把内循环遍历的条件改了, 这样内循环把外循环已经跑过的轮数去掉了, 就可以避免内循环中所有不必要的比较。
好了, 冒泡排序今天就介绍到这里, 最好画画图好好理解, 比较一下改进与改进之前的算法, 加深理解。
有问题可以评论呦~
如对本文有疑问， 点击进行留言回复！！
offset、client、scroll (width,height、left,top、X,Y)
网友评论