脚本宝典收集整理的这篇文章主要介绍了javascript数据结构与算法 --- 基本排序算法,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
基本排序算法总结
前言
随着node的兴起, 将javascript推向的一个前所未有的高度, node作为为建立高性能的服务端而创建的js运行平台随着时间的推移和生态链的完善已经不再局部于服务端,包括前端,后端,桌面,这篇文章介绍的传统的散打排序方法,并用javascript实现其功能,如有需要可以对其封装,在随后会介绍高级排序算法---(希尔排序,归并排序,快速排序),下面给出链接
-
冒泡排序
冒泡排序是最常见的一种排序方法,他采用类似于逐轮沉淀的方法每次找到队列中的最大值并放置与最后, 在每轮中使前一个元素与后一个元素比较,如果前者与后者就交换次序,如下图所示.
function @H_406_46@bubbleSort(array) {
for (let i = 0; i < array.length-1; i++) {
for (let j = 0; j < array.length-1-i ; j++) {
if (array[j] > array[j+1]) {
//1. es6
[array[j+1], array[j]] = [array[j], array[j+1]];
}
}
}
return array;
}
1 可以采用es6最新的解构语法交换数据
[array[j+1], array[j]] = [array[j], array[j+1]];
2 为引入变量的交换
array[j] = array[j] + array[j+1];
array[j+1] = array[j] - array[j+1];
array[j] = array[j] - array[j+1];
-
选择排序
function selectionSort(array) {
for (let i = 0; i < array.length - 1; i++) {
for (let j = i+1; j < array.length; j++) {
if (array[i] > array[j]) {
// es6
[array[j], array[i]] = [array[i], array[j]];
}
}
}
return array
}
-
插入排序
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let temp = array[i];
let j = 0;
for (j = i - 1; (j >= 0) && (temp < array[j]); j--) {
array[j + 1] = array[j];
}
array[j + 1] = temp;
console.LOG(array);
}
return array;
}
实验对比
-
创建随机生成数组:
let CArray = (function(params) {
function CArray(numElements) {
this.dataStore = [];
this.pos = 0;
this.numElements = numElements;
this.insert = insert;
this.toString = toString;
this.clear = clear;
this.setData = setData;
this.swap = swap;
for (var i = 0; i < numElements; ++i) {
this.dataStore[i] = 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;
}
return CArray;
})()
-
结论:
var numElements = 10000;
var myNums = new CArray(numElements);
myNums.setData();
var start = new Date().getTime();
bubbleSort(myNums.dataStore).toString()
var stop = new Date().getTime();
var between = stop - start;
console.log('冒泡排序执行时间:' + between);
start = new Date().getTime();
selectionSort(myNums.dataStore).toString()
stop = new Date().getTime();
between = stop - start;
console.log('选择排序执行时间:' + between);
start = new Date().getTime();
insertionSort(myNums.dataStore).toString()
stop = new Date().getTime();
between = stop - start;
console.log('插入排序执行时间:' + between);
console.log(new Date().getTime());
可知对于执行效率: 选择排序 > 插入排序要 > 冒泡
排序快,插入排序是这三种算法中最快的
以上是脚本宝典为你收集整理的javascript数据结构与算法 --- 基本排序算法全部内容,希望文章能够帮你解决javascript数据结构与算法 --- 基本排序算法所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。