DIV CSS 佈局教程網

JavaScript 五大經典演算法整理:查找、排序與字串反轉
編輯:關於JavaScript     

演算法並不是某個語言的專利。下面整理的這幾個基礎案例用 JavaScript 描述,但它們的思路放在 Java、C、Python 裡同樣成立,適合剛入門或想複習資料結構的朋友收藏起來慢慢看。

一、線性查找(Linear Search)

最直觀的一種查找:從頭到尾逐個比對,找到就回傳索引,全部掃完沒命中則回傳 -1。它是理解「時間複雜度」最好的起點。

 //A為數組,x為要搜索的值
function linearSearch(A, x) {
  for (var index = 0; index < A.length; index++) {
    if (A[index] == x) {
      return index;
    }
  }
  return -1;
}

二、二分查找(Binary Search)

又稱折半查找,前提很關鍵:資料必須已經排好序。每次拿中間元素與目標比較,把範圍砍掉一半,因此在大量資料上遠快於線性查找。實作時記得取整,並小心 low、high 的邊界。

 //A為已按"升序排列"的數組,x為要查詢的元素
 //返回目標元素的下標
function binarySearch(A, x) {
  var low = 0, high = A.length - 1;
  while (low <= high) {
    var mid = Math.floor((low + high) / 2); //下取整
    if (x == A[mid]) {
      return mid;
    }
    if (x < A[mid]) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

三、冒泡排序(Bubble Sort)

相鄰兩兩比較、把大的往後推,每一輪都能把當前最大值「浮」到尾端。這裡有兩個小細節值得學:內層迴圈是倒著走的,另外用一個 sorted 旗標做提前結束的優化——如果某一輪完全沒有發生交換,代表資料已經有序,可以直接收工。

 //冒泡排序
function bubbleSort(A) {
  for (var i = 0; i < A.length; i++) {
    var sorted = true; //注意:內循環是倒著來的
    for (var j = A.length - 1; j > i; j--) {
      if (A[j] < A[j - 1]) {
        swap(A, j, j - 1);
        sorted = false;
      }
    }
    if (sorted) {
      return;
    }
  }
}

四、插入排序(Insertion Sort)

像整理撲克牌一樣:假設左邊已經排好,先把自己手上的牌空出一個位置,前面比它大的元素依次往後挪,直到讓出一個「坑」,再把目標元素放進去。資料量小或接近有序時,它的表現往往比更複雜的排序更好。

 //插入排序
 //假定當前元素之前的元素已經排好序,先把自己的位置空出來,
 //然後前面比自己大的元素依次向後移,直到空出一個"坑",
 //然後把目標元素插入"坑"中
function insertSort(A) {
  for (var index= 1; index< A.length; index++) {
    var x = A[index];
    for (var j = index- 1; j >= 0 && A[j] > x; j--) {
      A[j + 1] = A[j];
    }
    if (A[j + 1] != x) {
      A[j + 1] = x;
      println(A);
    }
  }
  return A;
}

五、字串反轉

把字串切成陣列,用左右兩個指標向中間靠攏、邊走邊交換,最後再合併回字串。相比 split('').reverse().join('') 這種一行流,雙指標寫法更能看出「交換」這件事本質上發生了什麼。

 //字符串反轉(比如:ABC -> CBA)
function inverse(s) {
  var arr = s.split('');
  var index= 0, j = arr.length - 1;
  while (index< j) {
    var t = arr[index];
    arr[index] = arr[j];
    arr[j] = t;
    index++;
    j--;
  }
  return arr.join('');
}

以上就是五個常見演算法的整理。把這些寫熟之後,再去看更進階的排序(快速排序、歸併排序)會順暢很多。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved