前言
隨著前端的飛速發展，前端業務開發給前端工程師提出了更高的要求，因而演算法題也越來越高頻次的出現在前端面試中，有很多的小伙伴找胡哥苦訴，在前端實際開發中（除了涉及游戲開發方面），演算法使用有很多嗎？大廠的面試是故意要自我標榜下嗎？其實不然，考核演算法還是相當有必要的，來來來，讓胡哥給你拯救世界的理由，哦，不，是考核演算法的理由，
為啥要考演算法？
- 演算法是通用技能，包含了諸多邏輯和相關的技術點，優秀的演算法方案會體現出優秀的邏輯思維和和解決問題的能力，
- 扎實的演算法有助于我們在解決復雜問題時獲得更優的解決方案，
演算法的實作基于不同的語言有不同的形式，對于JavaScript來說，演算法的實作也有很多種不同的方式，本文基于JS最新的ES6語法來實作，各位小伙伴在領略演算法魅力的同時也能掌握到ES6的語法，
一、冒泡演算法
冒泡演算法，聞名而知其意，使用類似于水中氣泡自下而上逐漸變大的原理（這個原理要是有不清楚的童鞋，可咨詢物理老師壓強問題，看看老師會不會把你打出shi來...）來對陣列進行排序，
排序規則
- 每次回圈，比較當前位置項與下一個位置項的大小，如果當前項 > 后一項，則交換兩者的位置，每次回圈比較都能選擇出一個最大值，放在末尾，剩余待篩選的比較項就減少一項，
- 如果陣列存在n項，那么需要回圈執行篩選的次數為n次
二、冒泡演算法代碼實作
function bubbleSort ([...arr]) {
for (let i = 0; i < arr.length; i++) {
// 第j和j+1項比較，故j的最大值為 = 最大長度 - 1 - 減去已經執行篩選的輪數i
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交換陣列元素的位置
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
}
}
}
return arr
}
let arr = [4, 3, 2, 1]
// 輸出排序結果
let sortArr = bubbleSort(arr)
console.log(sortArr) // [1, 2, 3, 4]
// 輸出原陣列
console.log(arr) // [4, 3, 2, 1]
ES6語法結構
- 函式定義時形參：[...arr]
解構賦值和擴展運算子，為不影響原陣列，使用該方式接收原陣列元素 - [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]運算式
利用陣列的解構賦值，交換兩個位置的值 [a, b] = [b, a] 這樣就不必借助于第三個變數來交換值
三、冒泡演算法優化
使用上面的方式來實作冒泡演算法排序時，時間平均復雜度為O(n^2)，那最壞的情況是什么呢？傳入的陣列完全是逆序的，即[4, 3, 2, 1]，但是如果傳入的陣列[1, 2, 3, 4]是完全正序的呢？如果還按該方式，那在執行時是性能浪費的，那該如何優化呢？
優化方案
如果陣列是完全順序的，那就說明在執行一次回圈比較時，沒有陣列元素被交換位置，所以我們來設定一個標志flag，初始化為true，如果存在交換則賦值為false，在一次回圈后，如果標志為true，則表示為無交換，已經是完全順序了，則可以break停止外層回圈了，下面我們來看下代碼實作，
function bubbleSort ([...arr]) {
for (let i = 0; i < arr.length; i++) {
// 設定標記，標記當前輪篩選時是否有交換位置元素，默認為true，如果有交換設定為false
let flag = true
// 第j和j+1項比較，故j的最大值為 最大長度 - 1 - 減去已經執行篩選的輪數i
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交換陣列元素的位置
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
// 有交換位置，設定標記為false
flag = false
}
}
// 如果當前輪比較時沒有交換位置，說明已經排序完成了
if (flag) {
break
}
}
return arr
}
let arr = [1, 2, 3, 4]
// 輸出排序結果
let sortArr = bubbleSort(arr)
console.log(sortArr) // [1, 2, 3, 4]
// 輸出原陣列
console.log(arr) // [1, 2, 3, 4]
此時在完成排序時，只執行了一次回圈，此刻的時間復雜度為O(n)
后記
以上就是胡哥今天給大家分享的內容，喜歡的小伙伴記得收藏、轉發、點擊右下角按鈕在看，推薦給更多小伙伴呦，歡迎多多留言交流...
胡哥有話說，一個有技術，有情懷的胡哥！現任京東前端攻城獅一枚，
胡哥有話說，專注于大前端技術領域，分享前端系統架構，框架實作原理，最新最高效的技術實踐！
長按掃碼關注，更帥更漂亮呦！關注胡哥有話說公眾號，可與胡哥繼續深入交流呦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/124758.html
標籤：JavaScript