js算法中的排序、數組去重詳細概述

2019-11-20 21:53:40

字體：大中小

來源：轉載

供稿：網友

其實在js中實現數組排序，采用數組中sort方法實現還是比較簡單的：

一、排序

簡單實現數組排序

var arr = [];  
for(var i=0;i<20;i++){  
    arr.push(Math.floor(Math.random()*100))  
}  
arr.sort(function(a,b){  
    return a>b?1:-1;  
})  
alert(arr)

不能簡單使用sort方法，默認情況下 sort方法是按ascii字母順序排序的，而非我們認為是按數字大小排序，

sort() 方法可以接受一個方法為參數，這個方法有兩個參數。分別代表每次排序比較時的兩個數組項。sort()排序時每次比較兩個數組項都回執行這個參數，并把兩個比較的數組

項作為參數傳遞給這個函數。當函數返回值為1的時候就交換兩個數組項的順序，否則就不交換。

算法的數組排序

復制代碼代碼如下:

var arr = [];  
for(var i=0;i<20;i++){  
    arr.push(Math.floor(Math.random()*100))  
}  
//生成一個無序的arr數組  
function sort(arr,start,end){  
    //數組長度為1  
    if(start == end ){  
        return [arr[start]]  
    }else if(start == end-1){  
        //數組長度為2，根據數值大小 來排序  
        if(arr[start]>arr[end]){  
            return [arr[end],arr[start]]  
        }else{  
            return [arr[start],arr[end]]  
        }  
    }  
    // 數組長度一半  
    var l = Math.floor((start+end)/2);  
    //左邊數組  
    var arrLeft = sort(arr, start,l);  
    //右邊數組  
    var arrRight = sort(arr,l+1,end);  
    //返回結果  
    var result = [];  
    //分割成兩部分 左右兩個數組 只比對數組中的第一個數，那個數值小就把誰放到結果里面，并把小的數值刪除掉，固采用數組中的shift方法。一旦出現左邊數組或右邊數組，沒有數據的時候  
    //result數組就與還有數據的數組合并 采用 concat,并返回結果  
    while(arrLeft.length>0 || arrRight.length>0){  
        if(arrLeft.length==0){  
            result = result.concat(arrRight);  
            break;  
        }else if(arrRight.length==0){  
            result = result.concat(arrLeft);  
            break;  
        }  
        if(arrLeft[0]<arrRight[0]){  
            result.push(arrLeft.shift())  
        }else{  
            result.push(arrRight.shift());  
        }  
    }  
    return result;  
}  
var arrSort = sort(arr,0,arr.length-1);//參數 數組，開始位置，結束位置  

document.write(arr+'<br/>'+arrSort);

講解：數組排序主要是采用將數組一拆為二，直到不能為之，最后只能是拆掉數組里面只能是一個或者是兩個，因為數組的長度有奇數偶數之分，拆到最后數組里面只有一個或者兩個之后開始排序并返回結果，并將這些結果在一一比對進行合并。這個方法可能大家覺得為什么要這么復雜，一直采用第一種不行嗎，其實當然可以啦，但是這個世界上還有性能這個詞匯，當數據之后幾個幾十個幾個百，大家的算出的結果時間是沒有什么區別的，如果當數據龐大的幾億幾十億我們還有這種自信用第一種方法嗎，其實js的算法就是分而治之，將很多問題劃分成小的來解決。

二、數組去掉重復

簡單方法去掉重復：先聲明一個空的數組，將重復的數組 for 循環插入，重復的跳過不重復的插入

復制代碼代碼如下:

var arr = [];  
for(var i=0;i<20;i++){  
    arr.push(parseInt(Math.random()*10));  
}  
Array.prototype.indexOf = function(n){  
    for(var i=0;i<this.length;i++){  
        if(this[i] == n){  
            return i;  
        }  
    }  
    return -1;  
}  
function removeDup(arr){  
    var result = [];  
    for(var i=0;i<arr.length;i++){  
        if(result.indexOf(arr[i]) == -1){  

            result.push(arr[i]);  
        }  
    }  
    return result;   
}  
var arr2 = removeDup(arr)  
document.write(arr+'<br/>'+arr2) 

算法數組去掉重復

復制代碼代碼如下:

var arr = [];  
for(var i=0;i<20;i++){  
    arr.push(parseInt(Math.random()*10));  
}  
Array.prototype.indexOf = function(n){  
    for(var i=0;i<this.length;i++){  
        if(this[i] == n){  
            return i;  
        }  
    }  
    return -1;  
}  
function removeDup(arr,s,e){  
    if(s==e){  
        //分割就剩下一個  
        return [arr[s]]  
    }else if(s==e-1){  
        //為了優化 剩下兩個就不用分割啦  
        if(arr[s]==arr[e]){  
            return [arr[s]]  
        }else{  
            return [arr[s],arr[e]];  
        }  
    }  
    //數組平分成兩段，  
    var l = Math.floor((s+e)/2);  
    //左邊  
    var arrL = removeDup(arr,s,l);  
    //右邊  
    var arrR = removeDup(arr,l+1,e);  
    //結果 先把左邊的復制進去  
    var result = arrL;  
    //循環 將不重復的數據插入到結果里面  
    for(var i=0;i<arrR.length;i++){  
        if(result.indexOf(arrR[i])== -1 ) result.push(arrR[i])  
    }  
    return result; //返回結果  
}  
var arrDup = removeDup(arr, 0, arr.length-1);  
document.write(arr+'<br/>'+arrDup);