国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

js數值排序中冒泡算法的4種簡單實現

wean / 1049人閱讀

摘要:實現數組排序的算法很多其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數進行比較按照排序的條件進行互換例如對數值從小到大排序隨著不斷的互換最大的那個值會慢慢冒泡到數組的末端基于這個原理我們就可以寫冒泡排序了為了簡單起見下面的例子都是對數值

實現數組排序的算法很多,其中冒泡算法是比較簡單的
冒泡的基本原理是相鄰的兩個數進行比較,按照排序的條件進行互換,例如對數值從小到大排序,
隨著不斷的互換,最大的那個值會慢慢冒泡到數組的末端
基于這個原理我們就可以寫冒泡排序了

為了簡單起見下面的例子都是對數值數組進行從小到大排序,先模擬一個20個字符的數組

function getRandomArr(n) {
  let arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(~~(Math.random() * 100));
  }
  return arr
}
let randomArr = getRandomArr(20);

第一種冒泡算法
從原理可知,冒泡算法最少是需要2層循環的,當其中一個數值冒泡到末端時,這個數值下次就不需要參與循環了,這樣循環的范圍就會慢慢縮小,最后數組完成排序

function bubbleSort(arr) {
  let len = arr.length;
  let temp;
  let i = len - 1;
  while(i > 0) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    i--;//不斷縮小范圍
  }
  return arr;
}
console.log(randomArr)//[ 93, 72, 29, 17, 82, 26, 56, 71, 35, 48, 37, 42, 3, 11, 33, 66, 81, 53, 59, 53 ]
console.log("bubbleSort", bubbleSort(randomArr.concat()));//bubbleSort [ 3, 11, 17, 26, 29, 33, 35, 37, 42, 48, 53, 53, 56, 59, 66, 71, 72, 81, 82, 93 ]

在冒泡的過程中,我們可以發現,如果數組后面部分已經排好序了,也就是不用再交換雙方的位置時,只要記錄好最后一次交換的位置,就有很大的可能縮小下次循環的范圍,這樣就能提高冒泡的性能(這只是猜想)
第二種冒泡算法

function bubbleSort2(arr) { 
  let len = arr.length;
  let i = len - 1;
  let temp;
  let pos;//用來記錄位置的
  while (i > 0) {
    pos = 0;//初始為0如果數組一開始已經排好序了,那么就可以很快終止冒泡
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        pos = j;
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    i = pos;
  }
  return arr;
}
console.log(randomArr)//[47, 31, 85, 65, 44, 56, 54, 5, 67, 44, 76, 13, 90, 12, 83, 72, 2, 69, 58, 60]
console.log("bubbleSort2", bubbleSort2(randomArr.concat()));//bubbleSort2 [2, 5, 12, 13, 31, 44, 44, 47, 54, 56, 58, 60, 65, 67, 69, 72, 76, 83, 85, 90]

其實對于第一種循環,是從左到右進行冒泡,我們也可以從右到左冒泡,但是從右到左的方法和第一種基本就一樣了,但是我們可以在內層循環中實現先向左冒泡,再向右冒泡
第三種冒泡方法

function bubbleSort3(arr) {
  let len = arr.length;
  let low = 0;
  let higth = len - 1;
  let temp;
  while (low < higth) {
    for (let j = low; j < higth; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    higth--;
    for (let j = higth; j > low; j--) {
      if (arr[j] < arr[j - 1]) {
        temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }
    }
    low++;
  }
  return arr;
}
console.log(randomArr)//[40, 78, 16, 97, 38, 27, 66, 44, 45, 31, 12, 1, 99, 68, 36, 42, 40, 54, 6, 42]
console.log("bubbleSort3", bubbleSort3(randomArr.concat()));//bubbleSort3 [1, 6, 12, 16, 27, 31, 36, 38, 40, 40, 42, 42, 44, 45, 54, 66, 68, 78, 97, 99]

最后可以結合第三種和第二種方法
第四種冒泡的方法

function bubbleSort4(arr) { 
  let len = arr.length;
  let low = 0;
  let higth = len - 1;
  let temp;
  while (low < higth) {
    let hPos = 0;
    let lPos = higth;
    for (let j = low; j < higth; j++) {
      if (arr[j] > arr[j + 1]) {
        hpos = j;
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    heigth = hPos;
    for (let j = higth; j > low; j--) {
      if (arr[j] < arr[j - 1]) {
        lPos = j;
        temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }
    }
    low = lPos;
  }
  return arr;
}
console.log(randomArr)//[40, 78, 16, 97, 38, 27, 66, 44, 45, 31, 12, 1, 99, 68, 36, 42, 40, 54, 6, 42]
console.log("bubbleSort4", bubbleSort4(randomArr.concat()));//[1, 6, 12, 16, 27, 31, 36, 38, 40, 40, 42, 42, 44, 45, 54, 66, 68, 78, 97, 99]

下面對這4種方法在chrome控制臺下進行一個簡單的性能測試

var randomArr = getRandomArr(10000);
console.time("1");
bubbleSort(randomArr.concat());
console.timeEnd("1");
console.time("2");
bubbleSort2(randomArr.concat());
console.timeEnd("2");
console.time("3");
bubbleSort3(randomArr.concat());
console.timeEnd("3");
console.time("4");
bubbleSort4(randomArr.concat());
console.timeEnd("4");
VM371:4 1: 329.705ms
VM371:7 2: 379.501ms
VM371:10 3: 310.843ms
VM371:13 4: 306.847ms

在經過多次測試發現一個有趣的現象執行最快的是第4種方法,最慢的是第2種,沒錯最慢的是我認為可以提高性能的第2種方法,這就相當尷尬了,不知道有哪位小伙伴可以解釋一下

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/94619.html

相關文章

  • js數值排序冒泡算法4簡單實現

    摘要:實現數組排序的算法很多其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數進行比較按照排序的條件進行互換例如對數值從小到大排序隨著不斷的互換最大的那個值會慢慢冒泡到數組的末端基于這個原理我們就可以寫冒泡排序了為了簡單起見下面的例子都是對數值 實現數組排序的算法很多,其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數進行比較,按照排序的條件進行互換,例如對數值從小到大排序,隨著不斷的互...

    zacklee 評論0 收藏0
  • js數值排序冒泡算法4簡單實現

    摘要:實現數組排序的算法很多其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數進行比較按照排序的條件進行互換例如對數值從小到大排序隨著不斷的互換最大的那個值會慢慢冒泡到數組的末端基于這個原理我們就可以寫冒泡排序了為了簡單起見下面的例子都是對數值 實現數組排序的算法很多,其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數進行比較,按照排序的條件進行互換,例如對數值從小到大排序,隨著不斷的互...

    zzzmh 評論0 收藏0
  • Github標星2w+,熱榜第一,如何用Python實現所有算法

    摘要:歸并排序歸并排序,或,是創建在歸并操作上的一種有效的排序算法,效率為大符號。以此類推,直到所有元素均排序完畢。與快速排序一樣都由托尼霍爾提出的,因而也被稱為霍爾選擇算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);編譯:周素云、蔣寶尚 學會了Python基礎知識,想進階一下,那就來點算法吧!畢竟編程語言只...

    zxhaaa 評論0 收藏0
  • 一些前端算法詳解 --- (不定時更新)

    摘要:也稱縮小增量排序,是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因於年提出而得名。 前言 因為比較隨心所欲,所以我不按難度分享算法,所以你們會看到有時候順序有變化,因為我發表的時候會按照難度修改下位置,盡量讓你們看的時候能從簡單開始,以后每次更新都加個更新時間好了,讓你們知道我進度.新增計時函數直觀對比效率并且因為資料比較雜,很多都是我個人理解說法,如果有發...

    Baaaan 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<