算法—js实现

一直以来打算用js实现常见的一些算法问题，用js实现排序 测试用例[45,56,89,44,63,74,23,89];

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;
}

var str = [45,89];

console.log(Select_sort(str));

/*
希尔排序，不稳定，时间复杂度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 = arr.splice(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] < arr[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));

js 去重

数组去重的几种实现方式

/*方式一：常规解法， 时间复杂度 O(n^2)每次与新添加的数组比较，假如不在新数组里面，就push进来
*/
function uniqArray1(arr){
    var res = [];
    var len = arr.length;
    console.time("uniqArray1");
    for(var i=0; i

/*
方法二，使用数组原型上的方法 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}

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");