溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

JS實現(xiàn)常見的查找、排序、去重算法示例

發(fā)布時間：2020-08-20 09:17:26 來源：腳本之家 閱讀：134 作者：Jason齊齊 欄目：web開發(fā)

本文實例講述了JS實現(xiàn)常見的查找、排序、去重算法。分享給大家供大家參考，具體如下：

今天總結(jié)了下排序簡單的算法

【自定義排序】

先尋找一個最小的數(shù)，然后依次那這個數(shù)和數(shù)組中其他數(shù)字比較，如果發(fā)現(xiàn)比這個數(shù)字小的數(shù)就把這兩個數(shù)調(diào)換位置，然后再繼續(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));

【線性查找】：一個一個去查找

//不重復(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;
}
//測試性能
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)一偏左，向下取整

//不重復(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)，每次拿出兩個值，兩兩比較，如果下一個值比目前的小，那么交換位置

外層循環(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ù)大的放右邊，再把兩遍鏈接起來

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)空間不足的時候
  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：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

向AI問一下細節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手