本文實(shí)例講述了JS實(shí)現(xiàn)常見(jiàn)的查找、排序、去重算法。分享給大家供大家參考，具體如下：
今天總結(jié)了下排序簡(jiǎn)單的算法
【自定義排序】
先尋找一個(gè)最小的數(shù)，然后依次那這個(gè)數(shù)和數(shù)組中其他數(shù)字比較，如果發(fā)現(xiàn)比這個(gè)數(shù)字小的數(shù)就把這兩個(gè)數(shù)調(diào)換位置，然后再繼續(xù)尋找下一個(gè)最小的數(shù)字進(jìn)行下一輪比較
var arr = [31, 6, 19, 8, 2, 3];function findMin(start, arr) { var iMin = arr[start]; var iMinIndex = start; for (var i = start + 1; i < arr.length; i++) { if (arr[i] < iMin) { iMin = arr[i]; iMinIndex = i; } } return iMinIndex;}function sort1(arr) { for (var i = 0; i < arr.length; i++) { var iMinIndex = findMin(i, arr); var car; car = arr[i]; arr[i] = arr[iMinIndex]; arr[iMinIndex] = car; } return arr;}document.write(sort1(arr));【線性查找】：一個(gè)一個(gè)去查找
//不重復(fù) 有序var arr = [0];for (var i = 1; i < 100000; i++) { arr[i] = arr[i - 1] + Math.floor(Math.random() * 4 + 1);}function find1(n, arr) { for (var i = 0; i < arr.length; i++) { if (arr[i] == n) { return true; } } return false;}//測(cè)試性能var t1 = new Date().getTime();for (var i = 0; i < 10000; i++) { var n = Math.random() * 10000; find2(n, 0, arr.length - 1)}alert(new Date().getTime() - t1);【二分查找】：不停的分成兩個(gè)部分，分部分查找
是一種萬(wàn)能方法，不一定是最好的，但是個(gè)保底的方法。（分治法）
***中間值 相加除以二，統(tǒng)一偏左，向下取整
//不重復(fù) 有序var arr = [12, 17, 23, 34, 45, 76, 89];function find2(n, s, e) { //邊界處理 if (s > e) { return false; } else if (s == e) { if (arr[s] == n) { return true; } else { return false; } } var c = Math.floor((s + e) / 2); if (arr[c] == n) { return true; } else { if (n < arr[c]) { return find2(n, s, c); } else { return find2(n, c + 1, e); } }}alert(find2(34, 0, arr.length - 1)); //true false【邊界處理】-----遞歸，一層一層往下找
//要求數(shù)組不重復(fù)有順序/var arr = [12, 23, 34, 45, 56, 67, 78]function find2(n, s, e) { if (s > e) { return fasle; } else if (s == e) { if (arr[s] == e) { return true; } else { return false; } } var c = Math.floor((s + e) / 2); if (arr[c] == n) { return true; } else { if (n < arr[c]) { return find2(n, s, c); } else { return find2(n, c + 1, e); } }}alert(find2(12, arr.length + 1, 78));應(yīng)用
【查找最小值】
var arr = [12, 54, 32, 9, 5, 3, 1, 101, -100, -1000];function findMin(s, e) { if (s > e) { return []; } else if (s == e) { return arr[s]; } else if (s == e - 1) { if (arr[s] < arr[e]) { return arr[s]; } else { return arr[e]; } } var c = Math.floor((s + e) / 2); var l = findMin(s, c); var r = findMin(c + 1, e); if (l < r) { return l; } else { return r; }}alert(findMin(0, arr.length - 1));【數(shù)組去重】
var arr = [1, 2, 3, 4, 5, 4, 3, 4, 5, 2, 1, 4, 2, 1, 5, 7];function findInArr(n, arr) { for (var i = 0; i < arr.length; i++) { if (arr[i] == n) { return true; } } return false;}function removeCopy(s, e) { if (s > e) { return []; } else 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 c = Math.floor((s + e) / 2); var l = removeCopy(s, c); var r = removeCopy(c + 1, e); for (var i = 0; i < r.length; i++) { if (!findInArr(r[i], l)) { l.push(r[i]); } } return l;}document.write(removeCopy(0, arr.length - 1));【數(shù)組排序】
var arr = [34, 32, 1, 76, 55, -100, 99, 101];function mySort(s, e) { //邊界處理 if (s > e) { return []; } else if (s == e) { return [arr[s]] } else if (s == e - 1) { if (arr[s] < arr[e]) { return [arr[s], arr[e]]; } else { return [arr[e], arr[s]]; } } //1.切中間值 var c = Math.floor((s + e) / 2); //2.分半處理 var l = mySort(s, c); var r = mySort(c + 1, e); var res = []; while (l.length > 0 || r.length > 0) { if (l[0] < r[0]) { res.push(l.shift()); } else { res.push(r.shift()); } } if (l.length == 0) { res = res.concat(r); } else if (r.length == 0) { res = res.concat(l); } return res;}//調(diào)用document.write(mySort(0, arr.length - 1));冒泡排序 BubbleSort
循環(huán)，每次拿出兩個(gè)值，兩兩比較，如果下一個(gè)值比目前的小，那么交換位置
外層循環(huán)是循環(huán)取數(shù)，內(nèi)層循環(huán)是兩兩交換比較
var arr = [ - 122, -2, 5, 6, 73, 34, 5, 2];function BubbleSort(arr) { for (var i = 0; i < arr.length; i++) { for (var j = 0; j < arr.length - 1; j++) { if (arr[j] > arr[j + 1]) { var tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp } } } return arr;}document.write(BubbleSort(arr));【快速排序】 -------quickSort
取數(shù)組中間的數(shù)，比中間數(shù)小的房中間數(shù)左邊，比中間數(shù)大的放右邊，再把兩遍鏈接起來(lái)
function quickSort(arr, s, e) { //邊界處理 參與流程 if (arr.length == 0) { return []; } var c = Math.floor((s + e) / 2); var arrC = arr.splice(c, 1); var l = []; var r = []; for (var i = 0; i < arr.length; i++) { if (arr[i] < arrC) { l.push(arr[i]); } else { r.push(arr[i]); } } return quickSort(l).concat(arrC, quickSort(r));}var arr = [5, 5, 12, 56, 1, 67, -1, -23 - 1];document.write(quickSort(arr, 0, arr.length - 1));【散列】 hash 哈希 數(shù)組 ------js常用用的結(jié)構(gòu)
添加
var arr = [];arr.length = 0;var cont = 0;function hash_add(n) { var pos = n % arr.length; //當(dāng)空間不足的時(shí)候 if (arr[pos]) { while (arr[pos]) { cont++; if (arr[pos] == n) { return; } else { pos++; if (pos == arr.length) { pos = 0; } } } arr[pos] = n; } else { arr[pos] = n; } //空間不足的時(shí)候的擴(kuò)建 if (cont == arr.length) { //d等唄擴(kuò)建 var oldArr = arr; arr.length = oldArr.length * 2; arr = []; for (var i = 0; i < oldArr.length; i++) { arr.push(oldArr[i]); count = 0; } }}hash_add();PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：
在線動(dòng)畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過(guò)程工具：
http://tools.VeVB.COm/aideddesign/paixu_ys
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
