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

資訊專欄INFORMATION COLUMN

【30分鐘學會】用js玩點算法(1):排序基礎

Richard_Gao / 697人閱讀

摘要:如果今天這個比例降低了,可能的原因之一是如今的排序算法更加高效,而并非排序的重要性降低了。約定都是從小到大排序,當前項為。冒泡排序比較任何兩個相鄰的項,如果第一個比第二個大,則交換它們。

前言

前端工程師由于業務特點比較少接觸算法的東西,所以本系列也不會講太過深入的東西,更多的是作為知識擴展和思維邏輯的培養。
排序就是將一組對象按照某種邏輯順序重新排列的過程,本篇將介紹幾種金典的排序算法。

在計算時代早期,大家普遍認為30%的計算周期都用在了排序上。如果今天這個比例降低了,可能的原因之一是如今的排序算法更加高效,而并非排序的重要性降低了。

約定都是從小到大排序,當前項為i。swap是交換數組內位置的函數,實現如下:

function swap(_arr, index1, index2) {
  const arr = _arr;
  arr[index1] += arr[index2];
  arr[index2] = arr[index1] - arr[index2];
  arr[index1] -= arr[index2];
}
冒泡排序

學校里第一個學的排序方式總是冒泡排序,雖然它效率低,但最容易理解。冒泡排序比較任何兩個相鄰的項,如果第一個比第二個大,則交換它們。元素項向上移動至正確的順序,就好像氣泡升至表面一樣,冒泡排序因此得名。

一般方案

基本思路:

前一項(i)與后一項(i+1)項比較,如果前一項比后一項大就交換這兩項;

重復這個過程到最后;

一趟完成后再從頭開始重復上面的步驟,有多少項就要重復幾次。

代碼實現:

function bubbleSort(_arr) {
  const arr = [].slice.call(_arr);
  const len = arr.length;
  for (let i = 0; i < len; i += 1) {
    for (let f = 0; f < len - 1; f += 1) {
      if (arr[f] > arr[f + 1]) {
        swap(arr, f, f + 1);
      }
    }
  }
  return arr;
}

示例過程:

// 初始
5 4 9 5 3

// 第一趟
4 5 9 5 3  // 5>4,交換
^ ^
4 5 9 5 3  // 5<9,不變
  ^ ^
4 5 5 9 3  // 9>5,交換
    ^ ^
4 5 5 3 9  // 9>3,交換
      ^ ^

// 第二趟
4 5 5 3 9  // 4<5,不變
^ ^
4 5 5 3 9  // 5=5,不變
  ^ ^
4 5 3 5 9  // 5>3,交換
    ^ ^
4 5 3 5 9  // 5<9,不變
      ^ ^

// 第三趟
4 5 3 5 9  // 4<5,不變
^ ^
4 3 5 5 9  // 5>3,交換
  ^ ^
4 3 5 5 9  // 5=5,不變
    ^ ^
4 3 5 5 9  // 5<9,不變
      ^ ^

// 第四趟
3 4 5 5 9  // 4>3,交換
^ ^
3 4 5 5 9  // 4<5,不變
  ^ ^
3 4 5 5 9  // 5=5,不變
    ^ ^
3 4 5 5 9  // 5<9,不變
      ^ ^

// 第五趟
3 4 5 5 9  // 3<4,不變
^ ^
3 4 5 5 9  // 4<5,不變
  ^ ^
3 4 5 5 9  // 5=5,不變
    ^ ^
3 4 5 5 9  // 5<9,不變
      ^ ^

// 結果
3 4 5 5 9
改進方案

通過上面的排序過程,可以發現其實每一趟就可以確定最后一位的位置了,所以可以不用再比較最后的位置。代碼改造也很小,只要在內循環減去已經確定的位置數即可。

function modifiedBubbleSort(_arr) {
  const arr = [].slice.call(_arr);
  const len = arr.length;
  for (let i = 0; i < len; i += 1) {
    for (let f = 0; f < len - i - 1; f += 1) {
      if (arr[f] > arr[f + 1]) {
        swap(arr, f, f + 1);
      }
    }
  }
  return arr;
}

示例過程:

// 初始
5 4 9 5 3

// 第一趟
4 5 9 5 3  // 5>4,交換
^ ^
4 5 9 5 3  // 5<9,不變
  ^ ^
4 5 5 9 3  // 9>5,交換
    ^ ^
4 5 5 3 9  // 9>3,交換
      ^ ^

// 第二趟
4 5 5 3 9  // 4<5,不變
^ ^
4 5 5 3 9  // 5=5,不變
  ^ ^
4 5 3 5 9  // 5>3,交換
    ^ ^

// 第三趟
4 5 3 5 9  // 4<5,不變
^ ^
4 3 5 5 9  // 5>3,交換
  ^ ^

// 第四趟
3 4 5 5 9  // 4>3,交換
^ ^

// 結果
3 4 5 5 9
選擇排序

選擇排序算法是一種原址比較排序算法。這也是比較簡單的過程,只要不斷遍歷找到最小的數依次放入位置即可。
基本思路:

設定一個指針指向最小的數,從0號位開始;

遍歷數據,如果遇到比當前指針指向的數還小的數,就將指針重新指向這個新位置;

遍歷完成即得到了最小的數的位置,把0號位與這個位置的數交換;

接下來就是1號位,重復以上步驟直到全部位置都正確。

代碼實現:

function selectionSort(_arr) {
  const arr = [].slice.call(_arr);
  const len = arr.length;
  for (let i = 0; i < len - 1; i += 1) {
    let indexMin = i;
    for (let f = i + 1; f < len; f += 1) {
      if (arr[indexMin] > arr[f]) {
        indexMin = f;
      }
    }
    if (indexMin !== i) {
      swap(arr, indexMin, i);
    }
  }
  return arr;
}

示例過程:

// 初始
5 4 9 5 3

// 第一趟,指針指向0號位
5 4 9 5 3  // 4<5,指針指向1號位
  ^
5 4 9 5 3  // 9>4,指針不變
  ^
5 4 9 5 3  // 5>4,指針不變
  ^
5 4 9 5 3  // 3<4,指針指向4號位
        ^
3 4 9 5 5   // 遍歷結束,交換0號位和4號位

// 第二趟,指針指向1號位
3 4 9 5 5  // 9>4,指針不變
  ^
3 4 9 5 5  // 5>4,指針不變
  ^
3 4 9 5 5  // 5>4,指針不變
  ^
3 4 9 5 5  // 遍歷結束,1號位不變

// 第三趟,指針指向2號位
3 4 9 5 5  // 5<9,指針指向3號位
      ^
3 4 9 5 5  // 5=5,指針不變
      ^
3 4 5 9 5  // 遍歷結束,交換2號位和3號位

// 第四趟,指針指向3號位
3 4 5 9 5  // 5<9,指針指向4號位
        ^
3 4 5 5 9  // 遍歷結束,交換3號位和4號位

// 結果
3 4 5 5 9
插入排序

插入排序就是要把后面的數往前面插入。假定第一項已經排序了,接著從第二項開始,依次判斷當前項應該插入到前面的哪個位置。
基本思路:

從第二項開始(i=1),當前項(i),緩存其值和位置;

向前遍歷,指針f初始化為i位置,如果f-1大于當前項的值,則交換f和f-1(即f-1向后移動一位),并f--;

如果遇到f-1小于當前值,或f=0時停止循環,這時候f即是當前項的位置,將之前的緩存值寫入該位置。

代碼實現:

function insertionSort(_arr) {
  const arr = [].slice.call(_arr);
  const len = arr.length;
  for (let i = 1; i < len; i += 1) {
    let f = i;
    const temp = arr[i];
    while (f > 0 && arr[f - 1] > temp) {
      arr[f] = arr[f - 1];
      f -= 1;
    }
    arr[f] = temp;
  }
  return arr;
}

示例過程:

// 初始
5 4 9 5 3

// 第一趟,當前項是1號位,數字4
_ 5 9 5 3  // 4<5,5向后移動
^ ^
4 5 9 5 3  // 遍歷結束,寫入4
^

// 第二趟,當前項是2號位,數字9
4 5 9 5 3  // 9>5,不變
  ^
4 5 9 5 3  // 9>4,不變,遍歷結束
^

// 第三趟,當前項是3號位,數字5
4 5 _ 9 3  // 5<9,9向后移動
    ^ ^
4 5 _ 9 3  // 5=5,不變
  ^
4 5 _ 9 3  // 5>4,不變
^
4 5 5 9 3  // 遍歷結束,寫入5
    ^

// 第四趟,當前項是4號位,數字3
4 5 5 _ 9  // 3<9,9向后移動
      ^ ^
4 5 _ 5 9  // 3<5,5向后移動
    ^ ^
4 _ 5 5 9  // 3<5,5向后移動
  ^ ^
_ 4 5 5 9  // 3<4,4向后移動
^ ^
3 4 5 5 9  // 遍歷結束,寫入3
^

// 結果
3 4 5 5 9
歸并排序

歸并排序是一種分治算法。其思想是將原始數組切分成較小的數組,直到每個小數組只有一個位置,接著將小數組歸并成較大的數組,直到最后只有一個排序完畢的大數組。
基本思路:

將數組從中間切成兩個數組;

如果切出來的數組長度不為1,則重復上一步,直到所有切分出來的數組的長度都為1;

以從小到大的順序合并小數組,先是兩個長度為1的數組合并成長度為2的數組;

再是兩個長度為2的數組合并為長度為4的數組,以此類推。

代碼實現:

function mergeSort(_arr) {
  const arr = [].slice.call(_arr);
  function merge(left, right) {
    const result = [];
    let iL = 0;
    let iR = 0;
    const lenL = left.length;
    const lenR = right.length;
    while (iL < lenL && iR < lenR) {
      if (left[iL] < right[iR]) {
        result.push(left[iL]);
        iL += 1;
      } else {
        result.push(right[iR]);
        iR += 1;
      }
    }
    while (iL < lenL) {
      result.push(left[iL]);
      iL += 1;
    }
    while (iR < lenR) {
      result.push(right[iR]);
      iR += 1;
    }
    return result;
  }
  return (function cut(_array) {
    const len = _array.length;
    if (len === 1) {
      return _array;
    }
    const mid = Math.floor(len / 2);
    const left = _array.slice(0, mid);
    const right = _array.slice(mid, len);
    return merge(cut(left), cut(right));
  }(arr));
}

示例過程:

// 初始
5 4 9 5 3

// 切分
[5 4] [9 5 3]  // 中間數是9
     ^
([5] [4]) [9 5 3]  // 進入左側數組,中間數是4
    ^
([5] [4]) ([9] [5 3])  // 左側切分完,進入右側數組,中間數是5
              ^
([5] [4]) ([9] ([5] [3]))  // 左側切分完,進入右側數組,中間數是3
                   ^

// 合并[5]和[3]
([5] [4]) ([9] [3 $])  // 3<5,入3
                ^
([5] [4]) ([9] [3 5])  // 入5,完畢
                  ^

// 合并[9]和[3 5]
([5] [4]) [3 $ $]  // 3<9,入3
           ^
([5] [4]) [3 5 $]  // 5<9,入5
             ^
([5] [4]) [3 5 9]  // 入9,完畢
               ^

// 合并[5]和[4]
[4 $] [3 5 9]  // 4<5,入4
 ^
[4 5] [3 5 9]  // 入5,完畢
   ^

// 合并[4 5]和[3 5 9]
[3 $ $ $ $]  // 4>3,入3
 ^
[3 4 $ $ $]  // 4<5,入4
   ^
[3 4 5 $ $]  // 5=5,入5
     ^
[3 4 5 5 $]  // 入5
       ^
[3 4 5 5 9]  // 入9,完畢
         ^

// 結果
3 4 5 5 9
快速排序

快速排序的思想跟歸并很像,都是分治方法,但它沒有像歸并排序那樣將它們分割開,而是使用指針游標來標記,每次會確定一個主元的位置。稍微會比前面的復雜一些。
基本思路:

取數組的第0項作為主元,緩存0號位的數。

設定一個從0號位開始的low指針,一個從末尾開始的high指針;

先從high指針開始移動,指針指向的數與主元做比較,如果大于或等于主元則繼續向前移動,如果小于主元則停下并把high指針指向的數替換到當前low指針指向的位置;

再從low指針開始移動,指針指向的數與主元做比較,如果小于或等于主元則繼續向后移動,如果大于主元則停下并把low指針指向的數替換到當前high指針指向的位置;

如此循環交替移動兩個指針,直到low指針的指向位高于或等于high的指向位;

至此low指向位即是主元的位置pivotloc,將主元寫入low指向的位置;

以此位置pivotloc為分割,在左右兩邊重復上述的步驟,直到排序完成。

代碼實現:

function quickSort(_arr) {
  const arr = [].slice.call(_arr);
  function partition(low, high) {
    const pivotkey = arr[low];
    let i = low;
    let j = high;
    while (i < j) {
      while (i < j && arr[j] >= pivotkey) {
        j -= 1;
      }
      arr[i] = arr[j];
      while (i < j && arr[i] <= pivotkey) {
        i += 1;
      }
      arr[j] = arr[i];
    }
    arr[i] = pivotkey;
    return i;
  }
  (function QSort(low, high) {
    if (low < high) {
      const pivotloc = partition(low, high);
      QSort(low, pivotloc - 1);
      QSort(pivotloc + 1, high);
    }
  }(0, arr.length - 1));
  return arr;
}

示例過程:

// 初始
5 4 9 5 3

// 第一趟,主元為5
5 4 9 5 3  // high開始移動,3<5,high停止
^L      ^H
3 4 9 5 3  // 將high指向數3寫入到low位置
^L      ^H
3 4 9 5 3  // low開始移動,3<5,繼續前進
^L      ^H
3 4 9 5 3  // 4<5,繼續前進
  ^L    ^H
3 4 9 5 3  // 9>5,low停止
    ^L  ^H
3 4 9 5 9  // 將low指向數9寫入到high位置
    ^L  ^H
3 4 9 5 9  // high開始移動,9>5,繼續后退
    ^L  ^H
3 4 9 5 9  // high開始移動,5=5,繼續后退
    ^L^H
3 4 5 5 9  // 兩指針重合,結束,確定主元5的位置,寫入
    *

// 第二趟,主元為3
3 4 5 5 9  // high開始移動,4>3,繼續后退
^L^H*
3 4 5 5 9  // 兩指針重合,結束,確定主元3的位置,寫入
*   *

// 第三趟,主元為4
3 4 5 5 9  // 兩指針重合,結束,確定主元4的位置,寫入
* * *

// 第四趟,主元為5
3 4 5 5 9  // high開始移動,9>5,繼續后退
* * * ^L^H
3 4 5 5 9  // 兩指針重合,結束,確定主元5的位置,寫入
* * * *

// 第五趟,主元為9
3 4 5 5 9  // 兩指針重合,結束,確定主元9的位置,寫入
* * * * *

// 結果
3 4 5 5 9
簡易性能測試

上述的這么多種排序算法哪個比較快?這是我們比較好奇的問題,我們隨機生成10000個數據來測試一下吧。
兩個輔助函數:getRandomArray用來生成隨機數的數組,costClock用來統計耗時。

function getRandomArray(len = 10000, min = 0, max = 100) {
  const array = [];
  const w = max - min;
  for (let i = 0; i < len; i += 1) {
    array.push(parseInt((Math.random() * w) + min, 10));
  }
  return array;
}

function costClock(fn) {
  const now = new Date().getTime();
  const data = fn();
  const pass = new Date().getTime() - now;
  return {
    data,
    cost: pass,
  };
}

測試用例如下:

const array = getRandomArray(10000);
const result1 = costClock(() => bubbleSort(array));
const result2 = costClock(() => modifiedBubbleSort(array));
const result3 = costClock(() => selectionSort(array));
const result4 = costClock(() => insertionSort(array));
const result5 = costClock(() => mergeSort(array));
const result6 = costClock(() => quickSort(array));
console.log(result1);
console.log(result2);
console.log(result3);
console.log(result4);
console.log(result5);
console.log(result6);

結果如下圖,可見快速排序不愧是快速排序,不需要交互數據以及分治方法是其高效的主要原因。

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

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

相關文章

  • 數據庫

    摘要:編輯大咖說閱讀字數用時分鐘內容摘要對于真正企業級應用,需要分布式數據庫具備什么樣的能力相比等分布式數據庫,他們條最佳性能優化性能優化索引與優化關于索引與優化的基礎知識匯總。 mysql 數據庫開發常見問題及優化 這篇文章從庫表設計,慢 SQL 問題和誤操作、程序 bug 時怎么辦這三個問題展開。 一個小時學會 MySQL 數據庫 看到了一篇適合新手的 MySQL 入門教程,希望對想學 ...

    mengbo 評論0 收藏0
  • 數據庫

    摘要:編輯大咖說閱讀字數用時分鐘內容摘要對于真正企業級應用,需要分布式數據庫具備什么樣的能力相比等分布式數據庫,他們條最佳性能優化性能優化索引與優化關于索引與優化的基礎知識匯總。 mysql 數據庫開發常見問題及優化 這篇文章從庫表設計,慢 SQL 問題和誤操作、程序 bug 時怎么辦這三個問題展開。 一個小時學會 MySQL 數據庫 看到了一篇適合新手的 MySQL 入門教程,希望對想學 ...

    shuibo 評論0 收藏0

發表評論

0條評論

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