自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

程序員必備的幾種常見排序算法和搜索算法總結(jié)

作者：趣談前端
開發(fā) 前端 算法
最近為了鞏固一下自己的算法基礎(chǔ),又把算法書里的基本算法刷了一遍, 特地總結(jié)一下前端工程師需要了解的排序算法和搜索算法知識(shí)

 前言

最近為了鞏固一下自己的算法基礎(chǔ),又把算法書里的基本算法刷了一遍, 特地總結(jié)一下前端工程師需要了解的排序算法和搜索算法知識(shí),雖然還有很多高深算法需要了解, 但是基礎(chǔ)還是要好好鞏固一下的.本文將以圖文的形式為大家介紹如下算法知識(shí),希望在讀完之后大家能有所收獲: 冒泡排序及其優(yōu)化 選擇排序 插入排序 歸并排序 快速排序 順序搜索 * 二分搜索。

[[421699]]

正文

我想對(duì)于每個(gè)前端工程師來說, 最頭疼的就是算法問題, 但是算法往往也是衡量一個(gè)人編程能力的一個(gè)很重要的指標(biāo).目前很多主流框架和庫都應(yīng)用了大量的算法和設(shè)計(jì)模式,為了讓自己的段位更高,我們只能不斷的"打怪"(也就是刷算法)升級(jí),才能成為"最強(qiáng)王者".

其實(shí)前端發(fā)展這么多年, 越來越偏向于精細(xì)化開發(fā), 很多超級(jí)應(yīng)用(比如淘寶,微信)都在追求極致的用戶體驗(yàn), 時(shí)間就是金錢,這要求工程師們不能像以前那樣,開發(fā)的程序只要能用就行, 我們往往還要進(jìn)行更加細(xì)致的測試(包括單元測試, 性能測試等),就拿排序來說, 對(duì)于大規(guī)模數(shù)據(jù)量的排序, 我們采用冒泡排序肯定是要被瘋狂吐槽的,因?yàn)槊芭菖判虻男阅軜O差(復(fù)雜度為O(n^2).在真實(shí)項(xiàng)目中我們往往不會(huì)采用冒泡排序,更多的會(huì)用快速排序或者希爾排序.關(guān)于排序算法性能問題我在之前的文章中有詳細(xì)介紹, 感興趣可以參考一下.

接下來就讓我們來一起學(xué)習(xí)如何實(shí)現(xiàn)文章開頭的幾個(gè)常用排序和搜索算法吧.

冒泡排序及其優(yōu)化

我們?cè)趯W(xué)排序算法時(shí), 最容易掌握的就是冒泡排序, 因?yàn)槠鋵?shí)現(xiàn)起來非常簡單,但是從運(yùn)行性能的角度來看, 它卻是性能最差的一個(gè).

冒泡排序的實(shí)現(xiàn)思路是比較任何兩個(gè)相鄰的項(xiàng), 如果前者比后者大, 則將它們互換位置.

為了更方便的展示冒泡排序的過程和性能測試,筆者先寫幾個(gè)工具方法,分別為動(dòng)態(tài)生成指定個(gè)數(shù)的隨機(jī)數(shù)組, 生成元素位置序列的方法,代碼如下:

 

  1. // 生成指定個(gè)數(shù)的隨機(jī)數(shù)組 
  2. const generateArr = (num = 10) => { 
  3.   let arr = [] 
  4.   for(let i = 0; i< num; i++) { 
  5.     let item = Math.floor(Math.random() * (num + 1)) 
  6.     arr.push(item) 
  7.   } 
  8.   return arr 
  9. } 
  10.  
  11. // 生成指定個(gè)數(shù)的元素x軸坐標(biāo) 
  12. const generateArrPosX = (n= 10, w = 6, m = 6) => { 
  13.   let pos = [] 
  14.   for(let i = 0; i< n; i++) { 
  15.     let item = (w + m) * i 
  16.     pos.push(item) 
  17.   } 
  18.   return pos 
  19. } 

 

有了以上兩個(gè)方法,我們就可以生成任意個(gè)數(shù)的數(shù)組以及數(shù)組項(xiàng)坐標(biāo)了,這兩個(gè)方法接下來我們會(huì)用到.

我們來直接寫個(gè)乞丐版的冒泡排序算法:

 

  1. bubbleSort(arr = []) { 
  2.     let len = arr.length 
  3.     for(let i = 0; i< len; i++) { 
  4.       for(let j = 0; j < len - 1; j++) { 
  5.         if(arr[j] > arr[j+1]) { 
  6.           // 置換 
  7.           [arr[j], arr[j+1]] = [arr[j+1], arr[j]] 
  8.         } 
  9.       } 
  10.     } 
  11.     return arr 
  12.   } 

 

接下來我們來測試一下, 我們用generateArr方法生成60個(gè)數(shù)組項(xiàng)的數(shù)組, 并動(dòng)態(tài)生成元素坐標(biāo):

 

  1. // 生成坐標(biāo) 
  2. const pos = generateArrPosX(60) 
  3. // 生成60個(gè)項(xiàng)的數(shù)組 
  4. const arr = generateArr(60) 

 

有關(guān)css部分這里就不介紹了,大家可以自己實(shí)現(xiàn).接下來我們就可以測試我們上面寫的冒泡排序了,當(dāng)我們點(diǎn)擊排序時(shí),結(jié)果如下:

可以看到數(shù)組已按照順序排好了,我們可以使用console.time來測量代碼執(zhí)行所用的時(shí)間,上面"乞丐版"冒泡排序耗時(shí)為0.2890625ms.

我們深入分析代碼就可以知道兩層for循環(huán)排序?qū)е铝撕芏喽嘤嗟呐判?如果我們從內(nèi)循環(huán)減去外循環(huán)中已跑過的輪數(shù),就可以避免內(nèi)循環(huán)中不必要的比較,所以我們代碼優(yōu)化如下:

 

  1. // 冒泡排序優(yōu)化版 
  2. bubbleSort(arr = []) { 
  3.   let len = arr.length 
  4.   // 優(yōu)化 
  5.   for(let i = 0; i< len; i++) { 
  6.     for(let j = 0; j < len - 1 - i; j++) { 
  7.       if(arr[j] > arr[j+1]) { 
  8.         // 置換 
  9.         [arr[j], arr[j+1]] = [arr[j+1], arr[j]] 
  10.       } 
  11.     } 
  12.   } 
  13.   return arr 
  14. } 

 

經(jīng)過優(yōu)化的冒泡排序耗時(shí):0.279052734375ms, 比之前稍微好了一丟丟, 但仍然不是推薦的排序算法.

選擇排序

選擇排序的思路是找到數(shù)據(jù)結(jié)構(gòu)中的最小值并將其放置在第一位,接著找到第二個(gè)最小值并將其放到第二位,依次類推.

我們還是按照之前的模式,生成一個(gè)60項(xiàng)的數(shù)組,

選擇排序代碼如下:

 

  1. selectionSort(arr) { 
  2.     let len = arr.length, 
  3.         indexMin 
  4.     for(let i = 0; i< len -1; i++) { 
  5.       indexMin = i 
  6.       for(let j = i; j < len; j++){ 
  7.         if(arr[indexMin] > arr[j]) { 
  8.           indexMin = j 
  9.         } 
  10.       } 
  11.       if(i !== indexMin) { 
  12.         [arr[i], arr[indexMin]] = [arr[indexMin], arr[i]] 
  13.       } 
  14.     } 
  15.     return arr 
  16. } 

 

點(diǎn)擊排序時(shí), 代碼運(yùn)行正常, 可以實(shí)現(xiàn)排序, 控制臺(tái)耗時(shí)為: 0.13720703125ms, 明顯比冒泡排序性能要好.

插入排序

插入排序 的思路是每次排一個(gè)數(shù)組項(xiàng),假定第一項(xiàng)已經(jīng)排序,接著它和第二項(xiàng)比較, 決定第二項(xiàng)的位置, 然后接著用同樣的方式?jīng)Q定第三項(xiàng)的位置, 依次類推, 最終將整個(gè)數(shù)組從小到大依次排序.

代碼如下:

 

  1. insertionSort(arr) { 
  2.     let len = arr.length, 
  3.         j, 
  4.         temp; 
  5.     for(let i = 1; i< len; i++) { 
  6.       j = i 
  7.       temp = arr[i] 
  8.       while(j > 0 && arr[j-1] > temp) { 
  9.         arr[j] = arr[j-1] 
  10.         j-- 
  11.       } 
  12.       arr[j] = temp; 
  13.     } 
  14.  } 

 

執(zhí)行結(jié)果如下:

控制臺(tái)打印耗時(shí)為:0.09912109375ms.

歸并排序

歸并排序算法性能比以上三者都好, 可以在實(shí)際項(xiàng)目中投入使用,但實(shí)現(xiàn)方式相對(duì)復(fù)雜.

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

為了實(shí)現(xiàn)該方法我們需要準(zhǔn)備一個(gè)合并函數(shù)和一個(gè)遞歸函數(shù)，具體實(shí)現(xiàn)如下代碼：

 

  1. // 歸并排序 
  2. mergeSortRec(arr) { 
  3.  let len = arr.length 
  4.  if(len === 1) { 
  5.    return arr 
  6.  } 
  7.  let mid = Math.floor(len / 2), 
  8.      left = arr.slice(0, mid), 
  9.      right = arr.slice(mid, len) 
  10.  return merge(mergeSortRec(left), mergeSortRec(right)) 
  11. } 
  12. // 合并方法 
  13. merge(left, right) { 
  14.     let result = [], 
  15.         l = 0, 
  16.         r = 0; 
  17.     while(l < left.length && r < right.length) { 
  18.       if(left[l] < right[r]) { 
  19.         result.push(left[l++]) 
  20.       }else { 
  21.         result.push(right[r++]) 
  22.       } 
  23.     } 
  24.     while(l < left.length) { 
  25.       result.push(left[l++]) 
  26.     } 
  27.     while(r < right.length) { 
  28.       result.push(right[r++]) 
  29.     } 
  30.     return result 
  31. } 

 

以上代碼中的遞歸作用是將一個(gè)大數(shù)組劃分為多個(gè)小數(shù)組直到只有一項(xiàng)，然后再逐層進(jìn)行合并排序。如果有不理解的可以和筆者交流或者結(jié)合筆者畫的草圖進(jìn)行理解。

快速排序

快速排序是目前比較常用的排序算法，它的復(fù)雜度為O(nlog^n),并且它的性能比其他復(fù)雜度為O(nlog^n)的好，也是采用分治的思想，將原始數(shù)組進(jìn)行劃分，由于快速排序?qū)崿F(xiàn)起來比較復(fù)雜，這里講一下思路： 1. 從數(shù)組中選擇中間項(xiàng)作為主元 2. 創(chuàng)建兩個(gè)指針，左邊一個(gè)指向數(shù)組第一項(xiàng)，右邊一個(gè)指向數(shù)組最后一項(xiàng)，移動(dòng)左指針直到我們找到一個(gè)比主元大的元素，移動(dòng)右指針直到找到一個(gè)比主元小的元素，然后交換它們的位置，重復(fù)此過程直到左指針超過了右指針 3. 算法對(duì)劃分后的小數(shù)組重復(fù)1，2步驟，直到數(shù)組完全排序完成。

代碼如下：

 

  1. // 快速排序 
  2. quickSort(arr, left, right) { 
  3.     let index 
  4.     if(arr.length > 1) { 
  5.       index = partition(arr, left, right) 
  6.       if(left < index - 1) { 
  7.         quickSort(arr, left, index -1) 
  8.       } 
  9.       if(index < right) { 
  10.         quickSort(arr, index, right) 
  11.       } 
  12.     }  
  13.   } 
  14. // 劃分流程 
  15. partition(arr, left, right) { 
  16.     let part = arr[Math,floor((right + left) / 2)], 
  17.         i = left, 
  18.         j = right 
  19.     while(i <= j) { 
  20.       while(arr[i] < part) { 
  21.         i++ 
  22.       } 
  23.       while(arr[j] > part) { 
  24.         j-- 
  25.       } 
  26.       if(i <= j) { 
  27.         // 置換 
  28.         [arr[i], arr[j]] = [arr[j], arr[i]] 
  29.         i++ 
  30.         j-- 
  31.       } 
  32.     } 
  33.     return i 
  34. } 

 

順序搜索

搜索算法也是我們經(jīng)常用到的算法之一，比如我們需要查找某個(gè)用戶或者某條數(shù)據(jù)，不管是在前端還是在后端，都會(huì)使用搜索算法。我們先來介紹最簡單也是效率最低的順序搜索，其主要思想是將每一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素和我們要查詢的元素做比較，然后返回指定元素的索引。

之所以說順序搜索效率低是因?yàn)槊看味家獜臄?shù)組的頭部開始查詢，直到查找到要搜索的值，整體查詢不夠靈活和動(dòng)態(tài)性。順序搜索代碼實(shí)現(xiàn)如下：

 

  1. sequentialSearch(arr, item) { 
  2.     for(let i = 0; i< arr.length; i++) { 
  3.       if(item === arr[i]) { 
  4.         return i 
  5.       } 
  6.     } 
  7.     return -1 
  8. } 

 

接下來我們看下面一種比較常用和靈活的搜索算法——二分搜索。

二分搜索

二分搜索的思想有點(diǎn)“投機(jī)學(xué)”的意思，但是它是一種有理論依據(jù)的“投機(jī)學(xué)”。首先它要求被搜索的數(shù)據(jù)結(jié)構(gòu)已排序，其次進(jìn)行如下步驟： 1. 找出數(shù)組的中間值 2. 如果中間值是待搜索的值，那么直接返回中間值的索引 3. 如果待搜索的值比中間值小，則返回步驟1，將區(qū)間范圍縮小，在中間值左邊的子數(shù)組中繼續(xù)搜索 4. 如果待搜索的值比選中的值大，則返回步驟1，將區(qū)間范圍縮小，在中間值右邊的子數(shù)組中繼續(xù)搜索 5. 如果沒有搜到，則返回-1

由上圖大家可以很容易的理解二分搜索的實(shí)現(xiàn)過程，接下來我們看下代碼實(shí)現(xiàn)：

 

  1. binarySearch(arr, item) { 
  2.     // 調(diào)用排序算法先對(duì)數(shù)據(jù)進(jìn)行排序 
  3.     this.quickSort(arr) 
  4.  
  5.     let min = 0, 
  6.         max = arr.length - 1, 
  7.         mid, 
  8.         el 
  9.     while(min <= max) { 
  10.       mid = Math.floor((min + max) / 2) 
  11.       el = arr[mid] 
  12.       if(el < item) { 
  13.         min = mid + 1 
  14.       }else if(el > item) { 
  15.         max = mid -1 
  16.       }else { 
  17.         return mid 
  18.       } 
  19.     } 
  20.     return -1 
  21.   } 

 

其實(shí)還有很多搜索算法，我在之前的文章中都有介紹, 感興趣的可以學(xué)習(xí)參考一下。

責(zé)任編輯：華軒 來源： 今日頭條
算法程序員前端
相關(guān)推薦

2022-09-24 09:03:55

前端單元測試冒泡排序

2021-11-10 09:17:18

程序員排序算法搜索算法

2023-02-09 07:39:01

2011-01-04 11:02:08

程序員

2019-03-29 09:40:38

數(shù)據(jù)結(jié)構(gòu)算法前端

2012-08-20 09:26:17

程序員算法排列算法

2020-10-14 08:32:08

算法遞歸面試

2011-02-17 09:11:40

JavaScript算法

2014-07-01 09:43:55

程序員算法

2009-01-07 21:00:05

2023-05-30 07:58:01

谷歌搜索算法

2018-06-04 12:41:50

程序員貪心算法分析

2025-02-26 05:00:00

DFS算法遞歸

2020-12-08 05:52:28

js前端算法

2023-11-30 08:09:05

2018-10-12 15:15:45

電商搜索算法

2022-12-07 10:21:19

谷歌搜索技巧

2012-02-29 13:32:28

Java

2020-11-25 10:40:58

程序員技能開發(fā)者

2019-01-21 14:13:51

程序員技能開發(fā)者
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)