摘要：本文只是簡單理解算法，并不會深入的討論。大部分來自數組部分。如果數組中每個元素都不相同，則返回。示例輸入輸出加給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。盡量減少操作次數。

算法（algorithm），在數學（算學）和計算機科學之中，為任何良定義的具體計算步驟的一個序列，常用于計算、數據處理和自動推理。精確而言，算法是一個表示為有限長列表的有效方法。算法應包含清晰定義的指令用于計算函數。                                                - 來自維基百科

算法看起來在離我們一般的開發者不是很近，但是實際上又和我們的開發息息相關。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間復雜度與時間復雜度來衡量。現在想想大學的時候沒有好好的學習算法和數據結構真的是后悔的吐血。本文只是簡單理解算法，并不會深入的討論。畢竟每一個深入討論都夠喝一壺了。只是理解一下算法的思維和實現。 畢竟9月是個跳槽黃金時期，說不定能幫上你得忙呢？

算法在在我看來最直觀的作用就在于可以強化我們的編程思維邏輯。讓我么養成是用簡單的方式去解決問題的思維方式。下面我們一起來入算法的坑。本文中提到的相關的例子，都是相對比較簡單的。大部分來自leetcode數組部分。代碼都是我自己實現的，并不一定是最優解。歡迎各位大佬在issue中提交更好的實現方式。解析都寫到了代碼注釋中。

為了避免一些不必要的錯誤，文中的示例使用Typescript編寫，JavaScript 部分代碼在這兒,本文主要分了兩大部分 LeetCode/簡單算法

給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。

示例
給定數組 nums = [1,1,2],
函數應該返回新的長度 2, 并且原數組 nums 的前兩個元素被修改為 1, 2。
你不需要考慮數組中超出新長度后面的元素。

/**
 * 1 刪除排序數組中的重復項
 * 給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。
 * 不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。
 * 示例
 * 給定數組 nums = [1,1,2], 
 * 函數應該返回新的長度 2, 并且原數組 nums 的前兩個元素被修改為 1, 2。 
 * 你不需要考慮數組中超出新長度后面的元素。
 */
const removeDuplicates =  function(nums: number[]): number {
  let i: number = 0
  for (let j = 0; j < nums.length; j++) {
    if(nums[j] !== nums[i]) {
      i++
      nums[i] = nums[j]
    }
  }
  nums.splice(i+1)
  console.log(nums)
  console.log(nums.length)
  return i + 1
}
/**
 * 解析
 * 方法 雙指針法
 * i是慢指針，j是快指針 當我們遇到 nums[j] 
eq nums[i]nums[j]≠nums[i] 時，跳過重復項的運行已經結束，
 * 因此我們必須把它（nums[j]nums[j]）的值復制到 nums[i + 1]nums[i+1]。然后遞增 ii，接著我們將再次重復相同的過程，直到 jj 到達數組的末尾為止。
 * 復雜度分析：
 * 時間復雜度： O(n) 假設數組長度是n 那么i和j最多就是遍歷n步
 * 空間復雜度： O(1)
 */
removeDuplicates([0,0,1,1,1,2,2,3,3,4])

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例

輸入: [7,1,5,3,6,4]

輸出: 7

解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候
賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。

隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

/**
 * 2：  買賣股票的最佳時機
 * 給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
 * 設計一個算法來計算你所能獲取的最大利潤。你最多可以完成一次交易
 * 注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）
 * 
 * 輸入: [7,1,5,3,6,4]
 * 輸出: 7
 * 解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
 * 隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
 */
 // 第一種方式
const maxProfit = function (prices: number[]): number {
  if(prices.length < 2) return 0
  // 定義利潤
  let count: number = 0
  let PreMin:number =prices[0]
  // 獲取最大的單天利潤
  for (let i = 0; i < prices.length; i++) {
    count = Math.max(count, prices[i] - PreMin)
    PreMin = Math.min(PreMin, prices[i])
  }
  console.log(count)
  return count
}
/**
 * 解析： 貪心算法
 */
console.log("=================股票最佳購買時機貪心算法===================");
console.log(maxProfit([7,1,5,3,6,4]));
console.log("====================================");

// 第二種方式
const maxProfitMore = function (prices: number[]) :number{
  if(prices.length < 2) return 0
  let ret = 0
  for (let i = 0; i < prices.length; i++) {
    if (prices[i+1] > prices[i]) {
      ret += prices[i+1] - prices[i]
    }
  }
  return ret
}
/**
 * 解析： 非貪心算法 
 * 只要下一天的價錢 大于今天的價錢 那我們就賣出當前天的 最終的結果就是我們的利潤總和
 */
console.log("==================股票最佳購買時機非貪心算法==================");
console.log(maxProfitMore([7,1,5,8,3,6,4]))
console.log("=============================================");

給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。

示例
輸入: [1,2,3,4,5,6,7] 和 k = 3

輸出: [5,6,7,1,2,3,4]

解釋:

向右旋轉 1 步: [7,1,2,3,4,5,6]

向右旋轉 2 步: [6,7,1,2,3,4,5]

向右旋轉 3 步: [5,6,7,1,2,3,4]

要求

要求使用空間復雜度為 O(1) 的原地算法。

/**
 * 3： 給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。
 * 要求O(1)的空間復雜度，對原數組進行操作
 */
const rotate = function(nums: number[], k: number) {
  // 循環k,通過k我們可以確定需要移動的次數
  for (let i = 0; i < k; i++) {
    // 先在前面插入我們需要移動的地方
    nums.unshift(nums[nums.length -1 - i])
  }
  // 最后再去處理我們的數組
  nums.splice(nums.length - k, k)
}
rotate([1,2,3,4,5,6,7],3)

給定一個整數數組，判斷是否存在重復元素。如果任何值在數組中出現至少兩次，函數返回 true。如果數組中每個元素都不相同，則返回 false。

示例
輸入: [1,2,3,1]
輸出: true

/**
 * 4： 存在重復 
 * 給定一個整數數組，判斷是否存在重復元素。
 * 如果任何值在數組中出現至少兩次，函數返回 true。如果數組中每個元素都不相同，則返回 false。
 * 
 * 這個一定不是最優解
 */
const containsDuplicate = function (nums: number[]) :boolean{
    // 設置flag
    let judge = false
    // 容錯判斷
    if (nums.length <= 1) {
      return judge
    }
    // 通過最簡單直白的去重的思想去處理
    let current :number[] =[]
    for (let i = 0; i < nums.length; i++) {
      if (current.indexOf(nums[i]) === -1) {
        current.push(nums[i])
      } else {
        return judge = true
      }
    }
    return judge
}
console.log("================是否存在重復算法====================");
console.log(containsDuplicate([3,1]))
console.log("====================================");
// 這個其實是非常常見而且簡單得一個算法 但是要考慮到得情況多一點

給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。

示例

輸入: [2,2,1]

輸出: 1

要求
你的算法應該具有線性時間復雜度。 不適用額外的空間來實現

/**
 * 5: 只出現一次得數字
 * 給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。
 * 你的算法應該具有線性時間復雜度。 不使用額外空間來實現
 */
const singleNumber = function(nums: number[]) :number {
  let index= -1
  // 雙層進行比對 目的是當前key和數組中的每一個key進行比較
  nums.forEach((key, j)=> {
    //每次循環小游標
    let count = 0
    for (let k = 0; k < nums.length; k++) {
      if (key === nums[k]) {
        count += 1
      }
      // 循環完找出符合條件的下標
      if (k === nums.length -1 && count === 1) {
        index = j
      }
    }
  })
  return nums[index]
}
console.log("=================查找多帶帶數算法===================");
console.log(singleNumber([2,2,1,3,3]))
console.log("====================================");

給定兩個數組，編寫一個函數來計算它們的交集。

示例

輸入: nums1 = [1,2,2,1], nums2 = [2,2]

輸出: [2,2]

要求

輸出結果中每個元素出現的次數，應與元素在兩個數組中出現的次數一致。

我們可以不考慮輸出結果的順序。

/**
 * 6：求兩個數組的交集
 */
const intersect = function (nums1:number[], nums2:number[]) :number[]{
  let arr:number[] = []
  for (let i = 0; i < nums1.length; i++) {
    if (nums2.indexOf(nums1[i]) !== -1 ) {
      nums2.splice(nums2.indexOf(nums1[i]), 1)
      arr.push(nums1[i])
    }
  }
  return arr
}
/**
 * 解析： 在求交集的過程中。主要的思想是關于什么是交集。
 * 兩個數組的重合部分理論上來講就是交集
 * 循環其中一個數組nums1在后在另外一個數組nums2中比對是否出現，如果出現的話就刪除nums2中出現過的數組（注意是修改nums2）
 */
intersect([1,2,2,1], [2,2])

給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一.你可以假設除了整數 0 之外，這個整數不會以零開頭。

示例

輸入: [1,2,3]

輸出: [1,2,4]

/**
 * 7：加1
 * 給定一個由整數組成的非空數組所表示的非負整數，在該數的基礎上加一。
 * 你可以假設除了整數 0 之外，這個整數不會以零開頭。
 */
const plusOne =function (nums: number[]) :number[] {
  let j = nums.length - 1
  // js無法正常表示大于16位的整數【非科學計數】
  for (let i = nums.length - 1; i >=0; i--) {
    // 開始逐個進行加法運算
    if(i == j) {
      // 大于10的情況
      if(nums[i] + 1 >= 10){
        nums[i] = nums[i] + 1 -10
        j--
        // 最后一次循環
        if (i === 0) {
          nums.unshift(1)
        }
      } else {
        nums[j] ++
      }
    } else {
      break
    }
  }
  console.log(nums)
  return nums
}
/**
 * 解析： 如果使用太大的數的話轉成數字再加1是不行的，我們需要對數組中的的單個數據進行運算，同樣的是以輔助游標進行運算
 * 輔助游標j的主要作用是記錄需要+1的位置，如果當前的下標不等于j那么就跳出了循環：同時也提高了性能
 */
console.log("================加1算法====================");
console.log(plusOne([8,2,1,,1,2,2,2,3,5,5,5,5,5,2,3,4,2,3,4,5,5,5,5,2,9]))
console.log("====================================");

給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。

示例

輸入: [0,1,0,3,12]

輸出: [1,3,12,0,0]

要求

必須在原數組上操作，不能拷貝額外的數組。

盡量減少操作次數。

/**
 * 8: 移動零
 * 給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
 */
const moveZeroes = function(nums: number[]) {
  // 0出現的個數
  let j = 0
  nums.forEach((el: number, index: number, arr: number[]) => {
    if (nums[j] === 0) {
      nums.splice(j, 1)
      nums.push(0)
    } else {
      j++ 
    }
  })
  console.log(nums)
}
/**
 * 解析： 新建一個小游標j 這個是用來標識0出現的地方，每次移動完之后小游標是不變化的，因為原數組已經修改所以要固定一下游標
 * 雙游標法在算法真的很實用
 */
console.log("==================移動零算法==================");
moveZeroes([1,2,0,0,0,1])
console.log("====================================");

給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。你可以假設每個輸入只對應一種答案，且同樣的元素不能被重復利用。

示例

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

/**
 * 第一種解法
 * @param nums 
 * @param target 
 */
const twoSumA = function (nums: number[], target: number) :number[] {
  console.log("兩數求和第一種解法")
  let arr = [0,0] ,flag = false
  for (let i = 0; i < nums.length; i++) {
    compare(i)
    if (flag) {
      arr = [i, compare(i)]
      break
    }
  }
  /**
   * @param num 
   */
  function compare(index: number) :number {
    for (let j = 0; j < nums.length; j++) {
      if (j!== index && nums[index] + nums[j] === target) {
        flag = true
        return j
      }
    }
  }
  return arr
}
/**
 * 第二種解法
 */
const twoSumB = function (nums: number[], target: number) :number[] {
  let arr = [0,0]
  console.log("兩數求和第二種解法")
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (j!== i && nums[i] + nums[j] === target) {
        return arr = [i,j]
      }
    }
  }
  return arr
}
// 在進行一個數組中兩個數得比較中：一定要注意在相加得時候要排除自身去進行相加。
console.log("=================兩數之和算法===================");
console.log(twoSumA([3,2,4],6))
console.log(twoSumB([2, 7, 11, 15],9))
console.log("====================================");

判斷一個 9x9 的數獨是否有效。只需要根據以下規則，驗證已經填入的數字是否有效即可。

數字 1-9 在每一行只能出現一次。

數字 1-9 在每一列只能出現一次。

數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。

示例

給定

[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

輸出 js true

說明

一個有效的數獨（部分已被填充）不一定是可解的。

只需要根據以上規則，驗證已經填入的數字是否有效即可。

給定數獨序列只包含數字 1-9 和字符 "." 。

給定數獨永遠是 9x9 形式的。

/**
 * 10：有效得數獨
 */
let board = /* [
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"] 
]*/
[["7",".",".",".","4",".",".",".","."],
 [".",".",".","8","6","5",".",".","."],
 [".","1",".","2",".",".",".",".","."],
 [".",".",".",".",".","9",".",".","."],
 [".",".",".",".","5",".","5",".","."],
 [".",".",".",".",".",".",".",".","."],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".",".",".",".",".",".","."],
 [".",".",".",".",".",".",".",".","."]
]
const isValidSudoku = function (board: string[][]): boolean {
  let isPass = true
  const sudokuDeep = 9 // 數獨深度
  // 判斷行和列
  for (let i = 0; i < sudokuDeep; i++) {
    let row:any = {}
    let col:any = {}
    for (let j = 0; j < sudokuDeep; j++) {
      // 判斷行
      /**
       * 判斷方式
       * 首先判斷不為"." => 然后判斷是否存在row對象中 
       */
      if (board[i][j] !== ".") {
        if (row[board[i][j]]) {
          console.log(board[i][j])
          return isPass = false
        } else {
          row[board[i][j]] = board[i][j]
        }
      }
      // 判斷列
      if (board[j][i] !== ".") {
        if (col[board[j][i]]) {
          console.log(board[j][i]);
          return isPass = false
        } else {
          col[board[j][i]] = board[j][i]
        }
      }
      // 判斷九宮格 通過余數的形式判斷出來當前所處的9宮格
      // 先計算出位置
      let c = Math.floor(i/3)  // col位置
      let r = Math.floor(j/3) // row 位置
      // 勾勒出九宮格
      for (let m = c*3; m < c*3 + 3; m++) {
        for (let n = r * 3; n < r * 3 + 3; n++) {
          if (m === i && n === j) {
            // m === i && n === j 這時指向同一個位置
            continue
          } else {
            // 最重要的一次求值判斷
            if(board[m][n] != "." && board[i][j]!== "." && (board[i][j]) === board[m][n]) {
              return isPass = false
            } 
          }
        }
      }
      
    }
  }
  return isPass
}
console.log("=================有效數獨算法結果===================");
console.log(isValidSudoku(board))
console.log("====================================");

給定一個 n × n 的二維矩陣表示一個圖像。將圖像順時針旋轉 90 度。

示例

給定

[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

輸出

[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

要求

你必須在原地旋轉圖像，這意味著你需要直接修改輸入的二維矩陣。請不要使用另一個矩陣來旋轉圖像。

/**
 * 11： 旋轉圖像
 **/
const matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]
// 
/* const matrix = [
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
] */
const rotateMaps = function (matrix:number[][]) {
  const n = matrix.length
  // 倒敘循環進行90度的反轉
  for (let i = n-1; i >= 0; i--) {
    // 新數組補位到原數組中，為了是實現原地的旋轉操作，如果不需要
    for (let j = 0; j < n ; j++) {
      // console.log(`當前坐標[${i},${j}]`)
      const current = matrix[i][j]
      matrix[j].push(current)
      // 沒完成一組的賦值操作，就刪除旋轉前數組
      if(j === n - 1) {
        matrix[i].splice(0, n)
      }
    }
  }
  console.log(matrix)
  // return matrix
}

console.log("================旋轉圖像算法====================");
console.log(rotateMaps(matrix));
console.log("====================================");

這一部分先出demo，后面的代碼中的解析注釋會慢慢加上

fid為0代表一級，fid如果和fid為0的cid相等的話代表二級 以此類推...

/**
 * 10：找父親節點
 * fid為0代表一級，fid如果和fid為0的cid相等的話代表二級 以此類推...
 */
const findArr = [
  {"fid":0,"cid":3,"flag":"最外層3"},
  {"fid":0,"cid":4,"flag":"最外層4"},
  {"fid":4,"cid":5,"flag":"最外層-4"},
  {"fid":5,"cid":6,"flag":"最外層-4-1"},
  {"fid":0,"cid":7,"flag":"最外層7"},
  {"fid":7,"cid":8,"flag":"最外層-7"},
  {"fid":0,"cid":9,"flag":"最外層9"},
  {"fid":9,"cid":10,"flag":"最外層9-1"},
  {"fid":9,"cid":11,"flag":"最外層9-2"},
  {"fid":11,"cid":12,"flag":"最外層9-2-1"}
]
/**
 * 第一種方法：雙遞歸方式
 * @param arr 
 */
const findfid  = function (arr: any[]): any[] {
  let newArr:any[] = []
  for (let i = 0; i < arr.length; i++) {
    let flagId = arr[i].cid // 取出來一個flag 這個是用于和下一個級別匹配的
    for (let j = 0; j < arr.length; j++) {
      const elJ = arr[j]
      if (elJ.fid === flagId) { // fid 和 上級id 匹配
        (arr[i].children = []).push(elJ)
      }
    }
    // 只存入第一等級
    arr[i].fid === 0 && newArr.push(arr[i])
  }
  return newArr
}
/**
 * 第二種方法： 使用對象存儲id 然后和fid進行對比
 * @param arr 
 */
const findfidByObj = function (arr: any[]): any[] {
  let newArr:any[] = []
  let flagObj: any = {}
  arr.forEach(v => {
    flagObj[v.cid] = v
  })
  arr.forEach (item => {
    // 根據當前遍歷對象的fid,去map對象中找到對應索引的id
    const top = flagObj[item.fid]
    if (top) {
      // 如果找到索引，那么說明此項不在頂級當中,那么需要把此項添加到，他對應的父級中
      (top.children || (top.children = [])).push(item)
    } else {
      // 如果沒有在map中找到對應的索引ID,那么直接把當前的item添加到newData結果集中作為頂級
      newArr.push(item)
    }
  })
  return newArr
}
console.log("====================================");
console.log("找父親節點方式");
console.log(findfid(findArr))
console.log(findfidByObj(findArr))
console.log("====================================");

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

/**
 * 交換參數
 * @param {*} arr 
 * @param {*} a 
 * @param {*} b 
 */
const swap = function(arr: number[], a:number, b:number) {
  let curr = arr[a]
  arr[a] = arr[b]
  arr[b] = curr
}
/**
 * 
 * @param {選擇排序算法} arr 
 */
const sort = function (arr: number[]) {
  console.time()
  for (let i = 0; i < arr.length; i++) {
    //假設遍歷的當前第一個是最小的
    let minIndex = i
    //第二次遍歷把arr[minIndex]和數組中的其他的值進行遍歷
    for (let j = 0; j < arr.length; j++) {
      if(arr[minIndex] > arr[j]){
        minIndex = j
      }
    }
    //外層循環做交換
    swap(arr,minIndex,i)
  }
  console.log(arr)
  console.timeEnd()
}
sort([3,6,28,123,34])

冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。它重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素已經排序完成。

/**
 * @param {*冒泡排序算法} arr 
 */
const bubbleSort = function (arr: number[]){
  console.log("冒泡算法開始時間:")
  console.time()
  for (let i = 0; i < arr.length; i++) {
    // 這個循環時獲取到之后的項進行比較
    for (let j = i+1; j > 0; j--) {
      // 這個核心就是 如果當前項小于前一項那么當前項向上冒泡
      if(arr[i] < arr[j-1]){
        // 冒泡交換
        swap(arr,j,j-1)
      }
    }
  }
  console.timeEnd()
  console.log(arr)
}
bubbleSort([3,123,6,28,34])

插入排序是基于比較的排序。所謂的基于比較，就是通過比較數組中的元素，看誰大誰小，根據結果來調整元素的位置。

//插入排序算法
/**
 * 
 * @param {插入排序} arr 
 */
const insertSort = function (arr: number[]){
  console.time()
  for (let i = 0; i < arr.length; i++) {
    // 在一次循環的時候首先緩存下來當前的值和上一個index 緩存上一個index用來比較
    let compareIndex = i -1
    let currentValue = arr[i]
    // 在當前位置可以比較并且當前的值小于前一項的值的時候插入緩存的值然后修改index
    while (compareIndex >=0 && arr[compareIndex] > currentValue) {
      arr[compareIndex + 1] = arr[compareIndex]
      compareIndex--
    }
    arr[compareIndex + 1 ] = currentValue
  }
  console.timeEnd()
  console.log(arr)
}
insertSort([3,2,1])

二分查找也稱為折半查找。是指在有序的數組里找出指定的值，返回該值在數組中的索引。

/**
 * 二分查找算法 
 * 什么叫二分查找？ 二分查找也稱為折半查找。是指在有序的數組里找出指定的值，返回該值在數組中的索引。
 * （1）從有序數組的最中間元素開始查找，如果該元素正好是指定查找的值，則查找過程結束。否則進行下一步; 
 * （2）如果指定要查找的元素大于或者小于中間元素，則在數組大于或小于中間元素的那一半區域查找，然后重復第一步的操作; 
 * （3）重復以上過程，直到找到目標元素的索引，查找成功;或者直到子數組為空，查找失敗。
 * 注意： 這個先要把數組排序一下 在有序數組中查找
 * 優點是比較次數少，查找速度快，平均性能好；
 * 其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。
 */
/**
 * 非遞歸實現
 * @param {*} arr 
 * @param {*} target 
 */
function binarySearcNoRecursive(arr: number[], target: number){
  let low: number = 0, high: number = arr.length-1
  while(low <= high) {
    // 首先找到中間位置
    let middle = ((high + low ) / 2)
    if( target === arr[middle]){
      return middle
    } else if (target > arr[middle]){
      low = middle + 1
    } else if ( target < arr[middle] ){
      high = middle -1
    }else { 
      return -1
    }
  }
}
const result = binarySearcNoRecursive( [1,2,3,4,5,6,7,8,9,10,11,23,44,86], 23)
console.log(`二分查找不用循環找到的位置:${result}`)
/**
 * 遞歸實現 循環調用自身
 * @param {*} arr 
 * @param {*} target 
 */
function binarySearcRecursive(arr: number[], low:number, high: number, target:number){
  if(low > high){
    return -1
  }
  let middle = ((high + low ) / 2)
  if(arr[middle] === target){
    return middle
  } else if(arr[middle] > target){
    high = middle -1
    binarySearcRecursive(arr, low, high, target)
  } else if(arr[middle] < target){
    low = middle + 1
    binarySearcRecursive(arr, low, high, target)
  }
}
const  recursiveRes = binarySearcNoRecursive( [1,2,3,4,5,6,7,8,9,10,11,23,44,86], 3)
console.log(`二分查找不用循環找到的位置:${recursiveRes}`)

算法再編程中占據著相當重要的地位，語言的技術都可以速成。但是算法需要扎實的理論知識作為地基。本文只是根據leetcode中的題目，簡單的實現一下。感受一下算法的魅力。學習的話我建議還是系統深入的學。

代碼地址

相應的JavaScript示例代碼地址

原文地址 如果覺得有用得話給個?吧