大佬教程收集整理的这篇文章主要介绍了算法—js实现,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
冒泡排序,每次排序,将大的数据排到最后,
时间复杂度O(n^2)
算法是稳定的
*/
function Bubble_sort(a){
var arr = a;
for (var i = 1; i < arr.length;="" i++)="" {="" for="" (var="" j="0;" j="">< arr.length="" -="" i;="" j++)="" {="" if(arr[j]=""> arr[j+1]){
var t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
}
}
return arr;
}
var str = [45,89];
console.log(Bubble_sort(str));
/*
插入排序
时间复杂度O(n^2)
算法是稳定的
*/
function Insert_sort(a){
var arr = a;
for(var i = 1; i < arr.length;="" i++){="" var="" privot="arr[0];" if(arr[i]="">< arr[i-1]){="" var="" j="i-1;" privot="arr[i];" while(j="">= 0 && arr[j] > privot){
a[j+1] = a[j];
j--;
}
arr[j+1] = privot;
}
}
return arr;
}
var str = [45,89];
console.log(Insert_sort(str));
/*
*/
选择排序
时间复杂度O(n^2)
算法是不稳定的
*/
function SELEct_sort(a){
var arr = a;
for(var i = 0; i < arr.length-1;="" i++){="" for(var="" j="i+1;" j="">< arr.length;="" j++){="" var="" privot="i;" if(arr[j]="">< arr[i]){="" privot="j;" }="" var="" tmp="arr[privot];" arr[privot]="arr[i];" arr[i]="tmp;" }="" }="" return="" arr;="">
/*
希尔排序,不稳定,时间复杂度O(nlogn)
思路:通过设定一个间隔,不断缩小间隔,直至为1,此时基本有序
*/
function sHell_sort(a) {
var arr = a;
var len = arr.length;注意下取整的问题
//设置间隔,这里
for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (var i = 0; i < len;="" i="" +="gap)" {="" var="" tmp="arr[i];" for="" (var="" j="i;" j="">= gap && tmp < arr[j="" -="" gap];="" j="" -="gap)" {="" arr[j]="arr[j" -="" gap];="" }="" arr[j]="tmp;" }="" }="" return="" arr;="" }="">var str = [23,43,12,76,42,3,6,89];
console.log(sHell_sort(str));
/*
归并排序,稳定,时间复杂度O(nlogn)
思路:递归,将待排序数组分为两部分,直至每一部分的长度为1,
最后将左右两边连接。
*/
function merge(left,right) {
var arr = [];
while (left.length && right.length) {
if (left[0] <= right[0])="" {="">=>left.shift()删除left数组第一个元素,并返回第一个元素
arr.push(left.shift());
} else {
arr.push(right.shift());
}
}
return arr.concat(left,right);
}
function merge_sort(a) {
var len = a.length;
//递归终止条件
if (len === 1) {
return a;
}
//~~相当于MAth.floor()
var mID = ~~(len / 2),left = a.slice(0,mID),right = a.slice(mID);
return merge(merge_sort(left),merge_sort(right));
}
var tmp = [23,89];
console.log(merge_sort(tmp));
/*
快速排序,不稳定,时间复杂度O(nlogn)
找一个比较值,一般取中间值,小的在左,大的在右,
递归进行,直至有序
*/
function quick_sort(arr) {
var len = arr.length;
if (len <= 1)="" {="" return="" arr;="" }="" 选取比较值="" var="" privotindex="Math.floor(len" 2);="" var="" privot="">=>lice(privoTindex,1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length;="" i++)="" {="" if="" (arr[i]="">< privot)="" {="">left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quick_sort(left).concat([privot],quick_sort(right));
}
var str = [23,21,30,89];
console.log(quick_sort(str));
/*
堆排序,不稳定,时间复杂度O(nlog(n));
先建立大根堆,首尾交换,调整为大根堆
*/
/*建立大根堆*/
var len; //全局变量
function build_bigheap(arr) {
len = arr.length;
//从尾部开始调整
for (var i = Math.floor(len / 2); i >= 0; i--) {
adjustHeap(arr,i);
}
}
/*交换位置*/
function swap(arr,i,j) {
var tmp;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
return arr;
}
/*调整堆*/
function adjustHeap(arr,i) {
var left = 2 * i + 1,right = 2 * i + 2,index = i;
if (left < len="" &&="" arr[index]=""><>left]) {
index = left;
}
if (right < len="" &&="" arr[index]="">< arr[right])="" {="" index="right;" }="">if (index != i) {
swap(arr,indeX);
adjustHeap(arr,indeX);
}
}
function heap_sort(a) {
build_bigheap(a); //建立大根堆
for (var i = a.length - 1; i > 0; i--) {
//首尾交换
swap(a,i);
len--;
//重新调整
adjustHeap(a,0);
}
return a;
}
var str = [23,30];
console.log(heap_sort(str));
/*方式一:常规解法, 时间复杂度 O(n^2)每次与新添加的数组比较,假如不在新数组里面,就push进来
*/
function uniqArray1(arr){
var res = [];
var len = arr.length;
console.time("uniqArray1");
for(var i=0; i ole.timeEnd("uniqArray1");
return res;
}
var a = [1,'1',2,{'1':1,'2':2}];//uniqArray1: uniqArray1: 0.082ms
console.log(uniqArray1(a));//[1,"1",Object]
/*
方法二,使用数组原型上的方法 indexof
*/
function uniqArray2(arr){
var res = [];
var len = arr.length;
console.time("uniqArray2");
for(var i = 0; i < arr.length;="" i++){="" var="" item="arr[i];" if((res.indexof(item)="==" -1)="" &&="" res.push(arr[i])){};="">使用短路运算符,假如在新数组里面找不到为真
}
console.timeEnd("uniqArray2");
return res;
}
var a = [1,'2':2}];//uniqArray2: 0.115ms
console.log(uniqArray2(a));//[1,Object]
/*方式三*/
function uniqArray3(arr){
return arr.filter(function(item,index,array){
return array.indexOf(item) === index;
});
}
var a = [1,'2':2}];//uniqArray1: uniqArray1: 1.218ms
console.time("uniqArray3");
console.log(uniqArray3(a));//[1,Object]
console.timeEnd("uniqArray3");
/*方式四:上面几种解法时间复杂度都比较高,可以考虑先将数组排序,再来进行选择
该方法只适用于都是数值的情况*/
function uniqArray4(arr){
var res = [];
var len = arr.length;
for(var i = 0; i .sort().filter(function(item,array){
return !index || item != arraY[index-1];
});
}
}
var a = [1,8,5,4,7,9]; //uniqArray4: 1.517ms
console.time("uniqArray4");
console.log(uniqArray4(a));//[1,9]
console.timeEnd("uniqArray4");
方法五 ES6 新方法,性能不太好
function uniqArray5(arr){
return Array.from(new Set(arr));
}
var a = [1,9]; //uniqArray5: 7.596ms
console.time("uniqArray5");
console.log(uniqArray5(a));//[1,9]
console.timeEnd("uniqArray5");
split() //将字符串分割成数组
ncodeURIComponent("12321=aaa&2133+@") //"12321%3Daaa%262133%2B%40"
decodeURIComponent("12321%3Daaa%262133%2B%40"); //"12321=aaa&2133+@"
reduce() //方法 从左到右依次回调,最后返回最后一次回调的值
以上是大佬教程为你收集整理的算法—js实现全部内容,希望文章能够帮你解决算法—js实现所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。