DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> JavaScript基礎知識 >> js基本算法:冒泡排序,二分查找的簡單實例
js基本算法:冒泡排序,二分查找的簡單實例
編輯:JavaScript基礎知識     

知識擴充:

時間復雜度:算法的時間復雜度是一個函數,描述了算法的運行時間。時間復雜度越低,效率越高。

自我理解:一個算法,運行了幾次時間復雜度就為多少,如運行了n次,則時間復雜度為O(n)。

1.冒泡排序

解析:1.比較相鄰的兩個元素,如果前一個比後一個大,則交換位置。

2.第一輪的時候最後一個元素應該是最大的一個。

3.按照步驟一的方法進行相鄰兩個元素的比較,這個時候由於最後一個元素已經是最大的了,所以最後一個元素不用比較。

function sort(elements){
 for(var i=0;i<elements.length-1;i++){
 for(var j=0;j<elements.length-i-1;j++){
  if(elements[j]>elements[j+1]){
  var swap=elements[j];
  elements[j]=elements[j+1];
  elements[j+1]=swap;
  }
 }
 }
}
 
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements);
console.log(' after: ' + elements);

2.快速排序

解析:快速排序是對冒泡排序的一種改進,第一趟排序時將數據分成兩部分,一部分比另一部分的所有數據都要小。然後遞歸調用,在兩邊都實行快速排序。

function quickSort(elements) {
 
  if (elements.length <= 1) { return elements; }
 
  var pivotIndex = Math.floor(elements.length / 2);
 
  var pivot = elements.splice(pivotIndex, 1)[0];
 
 
  var left = [];
 
  var right = [];
 
  for (var i = 0; i < elements.length; i++){
 
    if (elements[i] < pivot) {
 
      left.push(elements[i]);
 
    } else {
 
      right.push(elements[i]);
 
    }
 
  }
 
  return quickSort(left).concat([pivot], quickSort(right));
 
};
 
var elements=[5,6,2,1,3,8,7,1.2,5.5,4.5];
alert(quickSort(elements));

3.插入排序

解析:

(1) 從第一個元素開始,該元素可以認為已經被排序

(2) 取出下一個元素,在已經排序的元素序列中從後向前掃描

(3) 如果該元素(已排序)大於新元素,將該元素移到下一位置

(4) 重復步驟3,直到找到已排序的元素小於或者等於新元素的位置

(5)將新元素插入到下一位置中

(6) 重復步驟2

insertSort: function(elements) {

  var i = 1,
  j, step, key, len = elements.length;

  for (; i < len; i++) {

    step = j = i;
    key = elements[j];

    while (--j > -1) {
      if (elements[j] > key) {
        elements[j + 1] = elements[j];
      } else {
        break;
      }
    }

    elements[j + 1] = key;
  }

  return elements;
}

2.二分查找

解析:二分查找,也為折半查找。首先要找到一個中間值,通過與中間值比較,大的放又,小的放在左邊。再在兩邊中尋找中間值,持續以上操作,直到找到所在位置為止。

(1)遞歸方法

function binarySearch(data,item,start,end){
  var end=end || data.length-1;
  var start=start || 0;
  var m=Math.floor((start+end)/2);
  if(item==data[m]){
    return m;
  }else if(item<data[m]){
    return binarySearch(data,item,start,m-1) //遞歸調用
  }else{
    return binarySearch(data,item,m+1,end);
  }
  return false;
}

  var arr=[34,12,5,123,2,745,32,4];

  binary(arr,5);

(2)非遞歸方法

function binarySearch(data, item){
  var h = data.length - 1,
    l = 0;
  while(l <= h){
    var m = Math.floor((h + l) / 2);
    if(data[m] == item){
      return m;
    }
    if(item > data[m]){
      l = m + 1;
    }else{
      h = m - 1;
    }
  }
 
  return false;
}
var arr=[34,12,5,123,2,745,32,4];
binarySearch(arr,5);

以上就是小編為大家帶來的js基本算法:冒泡排序,二分查找的簡單實例全部內容了,希望大家多多支持~

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