【30分鐘學(xué)會(huì)】用js玩點(diǎn)算法(1)：排序基礎(chǔ)

Richard_Gao 發(fā)布于2019-08-22 16:30 / 707人閱讀

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

前言

前端工程師由于業(yè)務(wù)特點(diǎn)比較少接觸算法的東西，所以本系列也不會(huì)講太過深入的東西，更多的是作為知識(shí)擴(kuò)展和思維邏輯的培養(yǎng)。
排序就是將一組對(duì)象按照某種邏輯順序重新排列的過程，本篇將介紹幾種金典的排序算法。

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

約定都是從小到大排序，當(dāng)前項(xiàng)為i。swap是交換數(shù)組內(nèi)位置的函數(shù)，實(shí)現(xiàn)如下：

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

冒泡排序

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

一般方案

基本思路：

前一項(xiàng)(i)與后一項(xiàng)(i+1)項(xiàng)比較，如果前一項(xiàng)比后一項(xiàng)大就交換這兩項(xiàng)；

重復(fù)這個(gè)過程到最后；

一趟完成后再?gòu)念^開始重復(fù)上面的步驟，有多少項(xiàng)就要重復(fù)幾次。

代碼實(shí)現(xiàn)：

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，不變
      ^ ^

// 結(jié)果
3 4 5 5 9

改進(jìn)方案

通過上面的排序過程，可以發(fā)現(xiàn)其實(shí)每一趟就可以確定最后一位的位置了，所以可以不用再比較最后的位置。代碼改造也很小，只要在內(nèi)循環(huán)減去已經(jīng)確定的位置數(shù)即可。

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，交換
^ ^

// 結(jié)果
3 4 5 5 9

選擇排序

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

設(shè)定一個(gè)指針指向最小的數(shù)，從0號(hào)位開始；

遍歷數(shù)據(jù)，如果遇到比當(dāng)前指針指向的數(shù)還小的數(shù)，就將指針重新指向這個(gè)新位置；

遍歷完成即得到了最小的數(shù)的位置，把0號(hào)位與這個(gè)位置的數(shù)交換；

接下來就是1號(hào)位，重復(fù)以上步驟直到全部位置都正確。

代碼實(shí)現(xiàn)：

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號(hào)位
5 4 9 5 3  // 4<5，指針指向1號(hào)位
  ^
5 4 9 5 3  // 9>4，指針不變
  ^
5 4 9 5 3  // 5>4，指針不變
  ^
5 4 9 5 3  // 3<4，指針指向4號(hào)位
        ^
3 4 9 5 5   // 遍歷結(jié)束，交換0號(hào)位和4號(hào)位

// 第二趟，指針指向1號(hào)位
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  // 遍歷結(jié)束，1號(hào)位不變

// 第三趟，指針指向2號(hào)位
3 4 9 5 5  // 5<9，指針指向3號(hào)位
      ^
3 4 9 5 5  // 5=5，指針不變
      ^
3 4 5 9 5  // 遍歷結(jié)束，交換2號(hào)位和3號(hào)位

// 第四趟，指針指向3號(hào)位
3 4 5 9 5  // 5<9，指針指向4號(hào)位
        ^
3 4 5 5 9  // 遍歷結(jié)束，交換3號(hào)位和4號(hào)位

// 結(jié)果
3 4 5 5 9

插入排序

插入排序就是要把后面的數(shù)往前面插入。假定第一項(xiàng)已經(jīng)排序了，接著從第二項(xiàng)開始，依次判斷當(dāng)前項(xiàng)應(yīng)該插入到前面的哪個(gè)位置。
基本思路：

從第二項(xiàng)開始(i=1)，當(dāng)前項(xiàng)(i)，緩存其值和位置；

向前遍歷，指針f初始化為i位置，如果f-1大于當(dāng)前項(xiàng)的值，則交換f和f-1（即f-1向后移動(dòng)一位），并f--；

如果遇到f-1小于當(dāng)前值，或f=0時(shí)停止循環(huán)，這時(shí)候f即是當(dāng)前項(xiàng)的位置，將之前的緩存值寫入該位置。

代碼實(shí)現(xiàn)：

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

// 第一趟，當(dāng)前項(xiàng)是1號(hào)位，數(shù)字4
_ 5 9 5 3  // 4<5，5向后移動(dòng)
^ ^
4 5 9 5 3  // 遍歷結(jié)束，寫入4
^

// 第二趟，當(dāng)前項(xiàng)是2號(hào)位，數(shù)字9
4 5 9 5 3  // 9>5，不變
  ^
4 5 9 5 3  // 9>4，不變，遍歷結(jié)束
^

// 第三趟，當(dāng)前項(xiàng)是3號(hào)位，數(shù)字5
4 5 _ 9 3  // 5<9，9向后移動(dòng)
    ^ ^
4 5 _ 9 3  // 5=5，不變
  ^
4 5 _ 9 3  // 5>4，不變
^
4 5 5 9 3  // 遍歷結(jié)束，寫入5
    ^

// 第四趟，當(dāng)前項(xiàng)是4號(hào)位，數(shù)字3
4 5 5 _ 9  // 3<9，9向后移動(dòng)
      ^ ^
4 5 _ 5 9  // 3<5，5向后移動(dòng)
    ^ ^
4 _ 5 5 9  // 3<5，5向后移動(dòng)
  ^ ^
_ 4 5 5 9  // 3<4，4向后移動(dòng)
^ ^
3 4 5 5 9  // 遍歷結(jié)束，寫入3
^

// 結(jié)果
3 4 5 5 9

歸并排序

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

將數(shù)組從中間切成兩個(gè)數(shù)組；

如果切出來的數(shù)組長(zhǎng)度不為1，則重復(fù)上一步,直到所有切分出來的數(shù)組的長(zhǎng)度都為1；

以從小到大的順序合并小數(shù)組，先是兩個(gè)長(zhǎng)度為1的數(shù)組合并成長(zhǎng)度為2的數(shù)組；

再是兩個(gè)長(zhǎng)度為2的數(shù)組合并為長(zhǎng)度為4的數(shù)組，以此類推。

代碼實(shí)現(xiàn)：

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]  // 中間數(shù)是9
     ^
([5] [4]) [9 5 3]  // 進(jìn)入左側(cè)數(shù)組，中間數(shù)是4
    ^
([5] [4]) ([9] [5 3])  // 左側(cè)切分完，進(jìn)入右側(cè)數(shù)組，中間數(shù)是5
              ^
([5] [4]) ([9] ([5] [3]))  // 左側(cè)切分完，進(jìn)入右側(cè)數(shù)組，中間數(shù)是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，完畢
         ^

// 結(jié)果
3 4 5 5 9

快速排序

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

取數(shù)組的第0項(xiàng)作為主元，緩存0號(hào)位的數(shù)。

設(shè)定一個(gè)從0號(hào)位開始的low指針，一個(gè)從末尾開始的high指針；

先從high指針開始移動(dòng)，指針指向的數(shù)與主元做比較，如果大于或等于主元?jiǎng)t繼續(xù)向前移動(dòng)，如果小于主元?jiǎng)t停下并把high指針指向的數(shù)替換到當(dāng)前l(fā)ow指針指向的位置；

再?gòu)膌ow指針開始移動(dòng)，指針指向的數(shù)與主元做比較，如果小于或等于主元?jiǎng)t繼續(xù)向后移動(dòng)，如果大于主元?jiǎng)t停下并把low指針指向的數(shù)替換到當(dāng)前high指針指向的位置；

如此循環(huán)交替移動(dòng)兩個(gè)指針，直到low指針的指向位高于或等于high的指向位；

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

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

代碼實(shí)現(xiàn)：

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開始移動(dòng)，3<5，high停止
^L      ^H
3 4 9 5 3  // 將high指向數(shù)3寫入到low位置
^L      ^H
3 4 9 5 3  // low開始移動(dòng)，3<5，繼續(xù)前進(jìn)
^L      ^H
3 4 9 5 3  // 4<5，繼續(xù)前進(jìn)
  ^L    ^H
3 4 9 5 3  // 9>5，low停止
    ^L  ^H
3 4 9 5 9  // 將low指向數(shù)9寫入到high位置
    ^L  ^H
3 4 9 5 9  // high開始移動(dòng)，9>5，繼續(xù)后退
    ^L  ^H
3 4 9 5 9  // high開始移動(dòng)，5=5，繼續(xù)后退
    ^L^H
3 4 5 5 9  // 兩指針重合，結(jié)束，確定主元5的位置，寫入
    *

// 第二趟，主元為3
3 4 5 5 9  // high開始移動(dòng)，4>3，繼續(xù)后退
^L^H*
3 4 5 5 9  // 兩指針重合，結(jié)束，確定主元3的位置，寫入
*   *

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

// 第四趟，主元為5
3 4 5 5 9  // high開始移動(dòng)，9>5，繼續(xù)后退
* * * ^L^H
3 4 5 5 9  // 兩指針重合，結(jié)束，確定主元5的位置，寫入
* * * *

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

// 結(jié)果
3 4 5 5 9

簡(jiǎn)易性能測(cè)試

上述的這么多種排序算法哪個(gè)比較快？這是我們比較好奇的問題，我們隨機(jī)生成10000個(gè)數(shù)據(jù)來測(cè)試一下吧。
兩個(gè)輔助函數(shù)：getRandomArray用來生成隨機(jī)數(shù)的數(shù)組，costClock用來統(tǒng)計(jì)耗時(shí)。

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,
  };
}

測(cè)試用例如下：

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);

結(jié)果如下圖，可見快速排序不愧是快速排序，不需要交互數(shù)據(jù)以及分治方法是其高效的主要原因。

云服務(wù)器 GPU云服務(wù)器分鐘學(xué)會(huì)python JS排序算法 30分鐘云服務(wù)器網(wǎng)絡(luò)電話免費(fèi)30分鐘

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/94405.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

Richard_Gao

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

基于javaweb+jsp的酒店管理系統(tǒng)

閱讀 2997·2021-11-23 09:51
分享幾個(gè)YYDS的Pycharm插件

閱讀 2820·2021-11-11 16:55
python實(shí)現(xiàn)——處理Excel表格（超詳細(xì)）

閱讀 2934·2021-10-14 09:43
蘋果全體員工大會(huì)信息泄密給媒體，庫(kù)克表示將全力追查

閱讀 1403·2021-09-23 11:22
Vue Router history模式的配置方法及其原理

閱讀 1045·2019-08-30 11:04
深入理解 flex-grow & flex-shrink & flex-basis

閱讀 1674·2019-08-29 11:10
log4j日志級(jí)別

閱讀 968·2019-08-27 10:56
前端報(bào)表數(shù)據(jù)處理【去重、行轉(zhuǎn)列、交叉、聚合】

閱讀 3124·2019-08-26 12:01

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

【30分鐘學(xué)會(huì)】用js玩點(diǎn)算法(1)：排序基礎(chǔ)

相關(guān)文章

數(shù)據(jù)庫(kù)

數(shù)據(jù)庫(kù)

發(fā)表評(píng)論

0條評(píng)論

Richard_Gao

男|高級(jí)講師

TA的文章

基于javaweb+jsp的酒店管理系統(tǒng)

分享幾個(gè)YYDS的Pycharm插件

python實(shí)現(xiàn)——處理Excel表格（超詳細(xì)）

蘋果全體員工大會(huì)信息泄密給媒體，庫(kù)克表示將全力追查

Vue Router history模式的配置方法及其原理

深入理解 flex-grow & flex-shrink & flex-basis

log4j日志級(jí)別

前端報(bào)表數(shù)據(jù)處理【去重、行轉(zhuǎn)列、交叉、聚合】

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

【30分鐘學(xué)會(huì)】用js玩點(diǎn)算法(1)：排序基礎(chǔ)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！