快捷導(dǎo)航

js算法中的排序、數(shù)組去重詳細(xì)概述

更新時(shí)間：2013年10月14日 17:15:17 作者：

在js中實(shí)現(xiàn)數(shù)組排序，采用數(shù)組中sort方法實(shí)現(xiàn)還是比較簡(jiǎn)單的，下面有個(gè)不錯(cuò)的示例大家可以參考下

其實(shí)在js中實(shí)現(xiàn)數(shù)組排序，采用數(shù)組中sort方法實(shí)現(xiàn)還是比較簡(jiǎn)單的：

一、排序

簡(jiǎn)單實(shí)現(xiàn)數(shù)組排序

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)

不能簡(jiǎn)單使用sort方法，默認(rèn)情況下 sort方法是按ascii字母順序排序的，而非我們認(rèn)為是按數(shù)字大小排序，

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

項(xiàng)作為參數(shù)傳遞給這個(gè)函數(shù)。當(dāng)函數(shù)返回值為1的時(shí)候就交換兩個(gè)數(shù)組項(xiàng)的順序，否則就不交換。

算法的數(shù)組排序

復(fù)制代碼代碼如下:

var arr = [];  
for(var i=0;i<20;i++){  
    arr.push(Math.floor(Math.random()*100))  
}  
//生成一個(gè)無(wú)序的arr數(shù)組  
function sort(arr,start,end){  
    //數(shù)組長(zhǎng)度為1  
    if(start == end ){  
        return [arr[start]]  
    }else if(start == end-1){  
        //數(shù)組長(zhǎng)度為2，根據(jù)數(shù)值大小 來(lái)排序  
        if(arr[start]>arr[end]){  
            return [arr[end],arr[start]]  
        }else{  
            return [arr[start],arr[end]]  
        }  
    }  
    // 數(shù)組長(zhǎng)度一半  
    var l = Math.floor((start+end)/2);  
    //左邊數(shù)組  
    var arrLeft = sort(arr, start,l);  
    //右邊數(shù)組  
    var arrRight = sort(arr,l+1,end);  
    //返回結(jié)果  
    var result = [];  
    //分割成兩部分 左右兩個(gè)數(shù)組 只比對(duì)數(shù)組中的第一個(gè)數(shù)，那個(gè)數(shù)值小就把誰(shuí)放到結(jié)果里面，并把小的數(shù)值刪除掉，固采用數(shù)組中的shift方法。一旦出現(xiàn)左邊數(shù)組或右邊數(shù)組，沒(méi)有數(shù)據(jù)的時(shí)候  
    //result數(shù)組就與還有數(shù)據(jù)的數(shù)組合并 采用 concat,并返回結(jié)果  
    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);//參數(shù) 數(shù)組，開始位置，結(jié)束位置  

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

講解：數(shù)組排序主要是采用將數(shù)組一拆為二，直到不能為之，最后只能是拆掉數(shù)組里面只能是一個(gè)或者是兩個(gè)，因?yàn)閿?shù)組的長(zhǎng)度有奇數(shù)偶數(shù)之分，拆到最后數(shù)組里面只有一個(gè)或者兩個(gè)之后開始排序并返回結(jié)果，并將這些結(jié)果在一一比對(duì) 進(jìn)行合并。這個(gè)方法可能大家覺得為什么要這么復(fù)雜，一直采用第一種不行嗎，其實(shí)當(dāng)然可以啦，但是這個(gè)世界上還有性能這個(gè)詞匯，當(dāng)數(shù)據(jù)之后幾個(gè) 幾十個(gè) 幾個(gè)百，大家的算出的結(jié)果時(shí)間是沒(méi)有什么區(qū)別的，如果當(dāng)數(shù)據(jù)龐大的幾億幾十億我們還有這種自信用第一種方法嗎，其實(shí)js的算法就是分而治之，將很多問(wèn)題劃分成小的來(lái)解決。

二、數(shù)組去掉重復(fù)

簡(jiǎn)單方法去掉重復(fù)：先聲明一個(gè)空的數(shù)組，將重復(fù)的數(shù)組 for 循環(huán)插入，重復(fù)的跳過(guò) 不重復(fù)的插入

復(fù)制代碼代碼如下:

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) 

算法數(shù)組去掉重復(fù)

復(fù)制代碼代碼如下:

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){  
        //分割就剩下一個(gè)  
        return [arr[s]]  
    }else if(s==e-1){  
        //為了優(yōu)化 剩下兩個(gè)就不用分割啦  
        if(arr[s]==arr[e]){  
            return [arr[s]]  
        }else{  
            return [arr[s],arr[e]];  
        }  
    }  
    //數(shù)組平分成兩段，  
    var l = Math.floor((s+e)/2);  
    //左邊  
    var arrL = removeDup(arr,s,l);  
    //右邊  
    var arrR = removeDup(arr,l+1,e);  
    //結(jié)果 先把左邊的復(fù)制進(jìn)去  
    var result = arrL;  
    //循環(huán) 將不重復(fù)的數(shù)據(jù)插入到結(jié)果里面  
    for(var i=0;i<arrR.length;i++){  
        if(result.indexOf(arrR[i])== -1 ) result.push(arrR[i])  
    }  
    return result; //返回結(jié)果  
}  
var arrDup = removeDup(arr, 0, arr.length-1);  
document.write(arr+'<br/>'+arrDup);