JS實現(xiàn)常見的查找、排序、去重算法示例
更新時間：2018年05月21日 10:21:11 作者：Jason齊齊
這篇文章主要介紹了JS實現(xiàn)常見的查找、排序、去重算法,結合實例形式總結分析了JavaScript線性查找、二分查找、遞歸查找、數(shù)組去重、冒泡拍戲、快速排序實現(xiàn)技巧,需要的朋友可以參考下
本文實例講述了JS實現(xiàn)常見的查找、排序、去重算法。分享給大家供大家參考，具體如下：
今天總結了下排序簡單的算法
【自定義排序】
先尋找一個最小的數(shù)，然后依次那這個數(shù)和數(shù)組中其他數(shù)字比較，如果發(fā)現(xiàn)比這個數(shù)字小的數(shù)就把這兩個數(shù)調換位置，然后再繼續(xù)尋找下一個最小的數(shù)字進行下一輪比較
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));
【線性查找】：一個一個去查找
//不重復 有序
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;
}
//測試性能
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);
【二分查找】：不停的分成兩個部分，分部分查找
是一種萬能方法，不一定是最好的，但是個保底的方法。（分治法）
***中間值 相加除以二，統(tǒng)一偏左，向下取整
//不重復 有序
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ù)組不重復有順序\
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));
應用
【查找最小值】
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;
}
//調用
document.write(mySort(0, arr.length - 1));
冒泡排序 BubbleSort
循環(huán)，每次拿出兩個值，兩兩比較，如果下一個值比目前的小，那么交換位置
外層循環(huán)是循環(huán)取數(shù)，內層循環(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ù)大的放右邊，再把兩遍鏈接起來
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常用用的結構
添加
var arr = [];
arr.length = 0;
var cont = 0;
function hash_add(n) {
var pos = n % arr.length;
//當空間不足的時候
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;
}
//空間不足的時候的擴建
if (cont == arr.length) {
//d等唄擴建
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：這里再為大家推薦一款關于排序的演示工具供大家參考：
在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數(shù)學運算用法總結》、《JavaScript數(shù)據(jù)結構與算法技巧總結》、《JavaScript數(shù)組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
相關文章
增強的 JavaScript 的 trim 函數(shù)的代碼
增強的 JavaScript 的 trim 函數(shù)的代碼...2007-08-08
這篇文章主要介紹了JS數(shù)組扁平化(flat)方法總結詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，,需要的朋友可以參考下2019-06-06
JavaScript原型和原型鏈與構造函數(shù)和實例之間的關系詳解
這篇文章主要介紹了JavaScript原型和原型鏈與構造函數(shù)和實例之間的關系，每個對象都連接到一個原型對象，并且它可以從中繼承屬性。所有通過對象字面量創(chuàng)建的對象都連接到object.prototype，它是JavaScript中的標配對象2022-07-07
JavaScript實現(xiàn)字符串與日期的互相轉換及日期的格式化
這篇文章主要介紹了JavaScript實現(xiàn)字符串與日期的互相轉換及日期的格式化的方法,這里格式化使用的是正則表達式來替換日期后進行格式化,需要的朋友可以參考下2016-03-03
JavaScript Set與Map數(shù)據(jù)結構詳細分析
大家心里是否產生過這樣的疑問,JS中既然已經(jīng)有對象這種數(shù)據(jù)結構,我們?yōu)槭裁催€要再單獨去使用Set或者Map呢?下面這篇文章主要給大家介紹了關于ES6中Set和Map數(shù)據(jù)結構的相關資料,需要的朋友可以參考下2022-11-11
本文主要介紹了JavaScript雙向鏈表實現(xiàn)LFU緩存算法，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要介紹了javascript實現(xiàn)頁面的實時時鐘顯示示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-08-08
所謂的提升用戶體驗,其實就是把所有用戶視為懶鬼,比如JavaScript自動完成(Autocomplete)腳本, 常用于表單,用戶只需輸入一兩個字母,就為你擴展、聯(lián)想、匹配和供君選擇,2009-10-10
這篇文章主要介紹了微信小程序之數(shù)據(jù)綁定原理解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-08-08
js中setTimeout()與clearTimeout()用法實例淺析
這篇文章主要介紹了js中setTimeout()與clearTimeout()用法,以實例形式分析了setTimeout()與clearTimeout()的功能與使用技巧,需要的朋友可以參考下2015-05-05