作为一个非科班生的伪程序员、数据结构和算法一直是弱项,得以有时间来研究.

冒泡排序

/**
* 冒泡排序
*
* @export bubbleSort
* @param {*} arr
* @returns
*/
function bubbleSort(arr) {
let i = arr.length - 1;
while (i > 0) {
let pos = 0;
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
pos = j;
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
i = pos;
}
return arr;
}

数组交集

以空间换时间。

/**
* @param params 需要求交集的数组,例如 intersectionSortArr([2, 3, 7, 8], [3, 7, 9, 12, 18, 20], [7, 16, 18])
*/
function intersection(...params) {
if (!params || params.length === 0) { return []; }

if (params.length === 1) {
return params[0];
}

const result = [];
const map = Object.create(null);
const [arr1, arr2, ...arrs] = params;
if (params.length > 2) {
return intersection(arr1, intersection(arr2, ...arrs));
}
let m = -1;
let n = -1;

while (++m < arr1.length) {
const value = arr1[m];
if (map[value]) {
map[value]++;
} else {
map[value] = 1;
}
}

while (++n < arr2.length) {
const value = arr2[n];
if (map[value] > 0) {
result.push(value);
map[value]--;
}
}
return result;
}

splice插入

平常开发过程中,操作数组插入大多数都是splice、push、unshift…加上for循环或者是forEach之类的,应付日常开发是没有问题,但是如果遇到数据量大的数组,再使用这几种方式,弊端就呈现出来了。
比如,需要给一个数组插入十万条数据。

var arr = [1,2,3]
console.time("insert");
for(var i = 0; i < 100000; i++) {
arr.splice(0,0,i)
}
console.timeEnd("insert");
console.log(arrInsert.length);

// insert: 1042.30615234375ms

超过一秒…
这还不是恐怖的,

再往里插十万条试试…

console.time("insert");
for(var i = 100000; i < 200000; i++) {
arr.splice(0,0,i)
}
console.timeEnd("insert");
console.log(arr.length);

// insert: 5970.119873046875ms

为什么会相差这么大?

js需要不同的键值顺序,每次都得重新计算,如果储存的数据进行了修改或者删除,这个索引也得重新计算。

链表

var arrInsert = [1, 2, 3];
var arrList = new LinkedList();
arrList.append(1);
arrList.append(2);
arrList.append(3);

console.time("arrList");
for (var k = 0; k < 10000; k++) {
arrList.insert(2, 0);
}
console.timeEnd("arrList");
console.log(arrList.size());


function LinkedList() {
var Node = function (element) {
this.element = element;
this.next = null;
};

var length = 0;
var head = null;

this.append = function (element) {
var node = new Node(element);
var current
if (head === null) {
head = node;
} else {

current = head;

while (current.next) {
current = current.next;
}

current.next = node;
}

length++;
};

this.insert = function (position, element) {

if (position >= 0 && position <= length) {

var node = new Node(element),
current = head,
previous,
index = 0;

if (position === 0) {

node.next = current;
head = node;

} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}

length++;

return true;

} else {
return false;
}
};

this.getHead = function () {
return head;
};

this.size = function () {
return length;
};
}

先插入十万条

console.time("arrList");
for (var k = 0; k < 100000; k++) {
arrList.insert(2, k);
}
console.timeEnd("arrList");
console.log(arrList.size());
// arrList: 5.231689453125ms

恩,有意思,再来一百万条试试。

console.time("arrList");
for (var k = 100000; k < 1100000; k++) {
arrList.insert(2, k);
}
console.timeEnd("arrList");
console.log(arrList.size());
// arrList: 213.933837890625ms