冒泡排序

    function  BubbleSort(){
    const{length}=array
       for(let i=0;i<length;i++)
       {
        for (let j=0;j<length-1-i;j++){
          if(arr[j]>arr[j+1]){
          swap(arr,j,j+1)
          }
        }
       }
       console.log(arry);
    }
    function swap(arry, a, b) {
        const temp = arry[a]
        arry[a] = arry[b]
        arry[b] = temp
//或者用 [arry[b],arry[a]]=[arry[a],arry[b]]//es6中數(shù)組解構(gòu)

      }

    var arr= [1,2,3,4,5]

選擇排序

記錄并不斷更改索引值,找到最小的數(shù)后替換

假設(shè)數(shù)組為 [5, 3, 8, 4, 2]：

• 第一輪外部循環(huán)（i = 0）：
  • 內(nèi)部循環(huán)找到最小元素 2 在索引 4，交換后數(shù)組變?yōu)?nbsp;[2, 3, 8, 4, 5]。
• 第二輪外部循環(huán)（i = 1）：
  • 內(nèi)部循環(huán)找到最小元素 3 在索引 1（未移動），數(shù)組保持不變。
• 第三輪外部循環(huán)（i = 2）：
  • 內(nèi)部循環(huán)找到最小元素 4 在索引 3，交換后數(shù)組變?yōu)?nbsp;[2, 3, 4, 8, 5]。
• 第四輪外部循環(huán)（i = 3）：
  • 內(nèi)部循環(huán)找到最小元素 5 在索引 4，交換后數(shù)組變?yōu)?nbsp;[2, 3, 4, 5, 8]。

排序完成，最終數(shù)組為 [2, 3, 4, 5, 8]。

插入排序

記錄索引對于元素的值,就是把大的數(shù)往后面覆蓋,最后肯定右兩個重復(fù)的大數(shù),直接把當(dāng)前的temp覆蓋到排在前面的大數(shù)就行

function insertSort(){
  const {length}=arr
  let temp
  for(let i=1;i<length;i++){
    temp=arr[i]
    j=i
    while(j>0&&arr[j-1]>temp){
        arr[j]=arr[j-1]
        j--
    }
    arr[j]=temp
  }
  console.log(arr);
} 
insertSort=[5, 4, 3, 3, 1]

具體用實例說明

• 第一輪循環(huán)（i = 1）：

  • temp = arr[1] = 4
  • j = 1
  • 比較 arr[j-1] (5) 和 temp (4)，因為 5 > 4，所以進(jìn)入 while 循環(huán)。
  • 將 arr[j-1] (5) 后移一位，數(shù)組變?yōu)?nbsp;[5, 5, 3, 3, 1]
  • j--，現(xiàn)在 j = 0
  • while 循環(huán)結(jié)束，因為 j = 0
  • 將 temp (4) 插入到 arr[j]，數(shù)組變?yōu)?nbsp;[4, 5, 3, 3, 1]

• 第二輪循環(huán)（i = 2）：

  • temp = arr[2] = 3
  • j = 2
  • 比較 arr[j-1] (5) 和 temp (3)，因為 5 > 3，所以進(jìn)入 while 循環(huán)。
  • 將 arr[j-1] (5) 后移一位，數(shù)組變?yōu)?nbsp;[4, 5, 5, 3, 1]
  • j--，現(xiàn)在 j = 1
  • 比較 arr[j-1] (4) 和 temp (3)，因為 4 > 3，所以繼續(xù) while 循環(huán)。
  • 將 arr[j-1] (4) 后移一位，數(shù)組變?yōu)?nbsp;[4, 4, 5, 3, 1]
  • j--，現(xiàn)在 j = 0
  • while 循環(huán)結(jié)束，因為 j = 0
  • 將 temp (3) 插入到 arr[j]，數(shù)組變?yōu)?nbsp;[3, 4, 5, 3, 1]

• 第三輪循環(huán)（i = 3）：

  • temp = arr[3] = 3
  • j = 3
  • 比較 arr[j-1] (5) 和 temp (3)，因為 5 > 3，所以進(jìn)入 while 循環(huán)。
  • 將 arr[j-1] (5) 后移一位，數(shù)組變?yōu)?nbsp;[3, 4, 5, 5, 1]
  • j--，現(xiàn)在 j = 2
  • 比較 arr[j-1] (4) 和 temp (3)，因為 4 > 3，所以繼續(xù) while 循環(huán)。
  • 將 arr[j-1] (4) 后移一位，數(shù)組變?yōu)?nbsp;[3, 4, 4, 5, 1]
  • j--，現(xiàn)在 j = 1
  • 比較 arr[j-1] (3) 和 temp (3)，因為 3 == 3，所以 while 循環(huán)結(jié)束。
  • 將 temp (3) 插入到 arr[j]，數(shù)組變?yōu)?nbsp;[3, 3, 4, 5, 1]

• 第四輪循環(huán)（i = 4）：

  • temp = arr[4] = 1
  • j = 4
  • 比較 arr[j-1] (5) 和 temp (1)，因為 5 > 1，所以進(jìn)入 while 循環(huán)。
  • 將 arr[j-1] (5) 后移一位，數(shù)組變?yōu)?nbsp;[3, 3, 4, 5, 5]
  • j--，現(xiàn)在 j = 3
  • 比較 arr[j-1] (4) 和 temp (1)，因為 4 > 1，所以繼續(xù) while 循環(huán)。
  • 將 arr[j-1] (4) 后移一位，數(shù)組變?yōu)?nbsp;[3, 3, 4, 4, 5]
  • j--，現(xiàn)在 j = 2
  • 比較 arr[j-1] (3) 和 temp (1)，因為 3 > 1，所以繼續(xù) while 循環(huán)。
  • 將 arr[j-1] (3) 后移一位，數(shù)組變?yōu)?nbsp;[3, 3, 3, 4, 5]
  • j--，現(xiàn)在 j = 1
  • 比較 arr[j-1] (3) 和 temp (1)，因為 3 > 1，所以繼續(xù) while 循環(huán)。
  • 將 arr[j-1] (3) 后移一位，數(shù)組變?yōu)?nbsp;[3, 3, 3, 4, 5]
  • j--，現(xiàn)在 j = 0
  • while 循環(huán)結(jié)束，因為 j = 0
  • 將 temp (1) 插入到 arr[j]，數(shù)組變?yōu)?nbsp;[1, 3, 3, 4, 5]

歸并排序

火狐瀏覽器的sort就是基于這種排序,chrome用到快速排序

    function mergeSort(array){
    if(array.length>1){
   const {length}=array 
    const middle=Math.floor(length/2)
    const left=mergeSort(array.slice(0,middle))
    const right=mergeSort(array.slice(middle,length))
    array=merge(left,right)
    }
        }
        function merge(left,right){
          let i=0;
          let j=0;
    const result=[]
    while(i<left.length&&i<right.length){
      result.push(left[i]<right[i]?left[i++]:right[i++])
    }
    result.concat(i<left.length?left.slice(i):right.slice(j))
        }
        mergeSort([5,4,3,2,1])

用具體例子解釋一下執(zhí)行過程

• 第一次調(diào)用 mergeSort：

  • 數(shù)組長度大于 1，繼續(xù)執(zhí)行。
  • middle 是 2。
  • left 是 [5, 4]，right 是 [3, 2, 1]。
  • 遞歸調(diào)用 mergeSort 對 left 和 right 進(jìn)行排序。

  merge中執(zhí)行過程

  第一輪比較：

  left[i] (4) 與 right[j] (1) 比較，因為 1 < 4，所以將 1 添加到 result 中。

  j 增加 1，現(xiàn)在 j = 1。

  第二輪比較：

  left[i] (4) 與 right[j] (2) 比較，因為 2 < 4，所以將 2 添加到 result 中。

  j 增加 1，現(xiàn)在 j = 2。

  第三輪比較：

  left[i] (4) 與 right[j] (3) 比較，因為 3 < 4，所以將 3 添加到 result 中。

  j 增加 1，現(xiàn)在 j = 3。

  第四輪比較：

  left[i] (4) 與 right[j] (不存在) 比較，因為 right 數(shù)組已經(jīng)沒有更多元素，所以將 left 數(shù)組剩余的元素 [4, 5] 添加到 result 中。

快速排序

以一個元素為基準(zhǔn)（可以是middle，0，length-1）把比它小的放一堆，比它大的放一堆，在以第一堆的元素中挑一個基準(zhǔn)，比它大的挑一堆，比它小的調(diào)一堆，分到最后把這幾堆和一起。

    function quickStore(){
      const {length}=arr
      if(length<2){
        return arr
      }
      let base=arr[0]
      let minArr=arr.slice(1).filter(item=>item>=base)
      let maxArr=arr.slick(1).filter(item=>item<base)
      return quickStore(minArr).contact(base).contact(quickStore(maxArrft))
    }

計數(shù)排序

但是會占據(jù)空間

找到最大值

const maxValue = findMax(arr)
// const maxValue = Math.max(...arr)

• 調(diào)用 findMax 函數(shù)來找到數(shù)組中的最大值。
• findMax 函數(shù)遍歷數(shù)組，比較每個元素，找到最大值。

:初始化計數(shù)數(shù)組

const counts = new Array(maxValue + 1)

• 創(chuàng)建一個長度為 maxValue + 1 的數(shù)組 counts，用于存儲每個元素的出現(xiàn)次數(shù)。
• 由于最大值是 9，所以 counts 的長度為 10。

  : 計數(shù)每個元素的出現(xiàn)次數(shù)

• 例如遍歷到數(shù)組中數(shù)字5出現(xiàn)2次，就把counts計數(shù)數(shù)組的下標(biāo)為5的位置計為1，再白能力一遍還有就++計為2。所以count數(shù)組中索引值為5的地方數(shù)值為2，意思是5出現(xiàn)了兩次。

• arr.forEach(item => {
    if(!counts[item]){
      counts[item] = 0
    }
    counts[item]++
  })

  構(gòu)建新的排序數(shù)組

  let newarr = []
  let sortIndex = 0
  counts.forEach((item, index) => {
    while(item > 0){
      newarr[sortIndex++] = index
      item--
    }
  })
  

• 初始化一個新的空數(shù)組 newarr。
• 遍歷 counts 數(shù)組，根據(jù)計數(shù)構(gòu)建新的排序數(shù)組。
• 對于 counts 中的每個非零元素，將其索引（即原數(shù)組中的元素值）添加到 newarr 中相應(yīng)次數(shù)。例如：遍歷到5前面數(shù)字都沒有出現(xiàn)就不會進(jìn)入while循環(huán)，知道索引值index為5時，就將newarr 中sortIndex=0索引值為0的位置計為index5，sortIndex++變?yōu)?，迎接下一個元素，counts 數(shù)組中索引值5的item減一也就是減少出現(xiàn)次數(shù)后再遍歷是否還出現(xiàn)，如果還有就把count下標(biāo)1的位置再計為5.出現(xiàn)次數(shù)減一。
• 完整代碼

•     var arr=[5,7,5,4,9,1]
      function countSort(arr){
        if(arr.length<2){
          return arr
        }
        const maxValue=findMax(arr)
        // const maxValue=Math.max(...arr)也可以用js內(nèi)置方法
        const counts=new Array(maxValue+1)
        arr.forEach(item => {
          if(!counts[item]){
            counts[item]=0
          }
          counts[item]++
        })
        let newarr=[]
        let sortIndex=0
        counts.forEach((item,index)=>{
          while(item>0){
            newarr[sortIndex++]=index
            item--
          }
        })
  
      }
      countSort(arr)
      function findMax(arr){
        let max=arr[0]
        for(let i=0;i<length;i++){
          if(arr[i]>max){
            maax=arr[i]
          }
        }
        return newarr
      }
  

  桶排序

• 數(shù)據(jù)稀疏桶會少，數(shù)據(jù)龐大桶多

      function bucketSort(arr, bucketSize=3){
        if(arr.length<2){
          return arr
        }
        //創(chuàng)建幾個小桶
        const buckets=createBucket(arr,buckdetSize)
  //小桶排序（插入算法）合并concat
  return sortBucket(buckets)
      }
      function createBucket(arr,buckdetSize){
  //找最大值和最小值
  let minValue=Math.min(...arr)
  let maxValue=Math.max(...arr)
  //桶數(shù)量
  const bucetCount=Math.floor((maxValue-minValue)/ buckdetSize)+1//+1是為了如果最大值正好等于某個桶的邊界值，
  // 那么按照簡單的除法計算，最大值可能會被分配到超出桶的范圍之外。
        // //創(chuàng)建桶子
        // const buckets = []
        // for (let i = 0; i < bucketCount; i++) {
        //   buckets[i] = []
        // }
        // ES6
        const buckets=[...Array(bucetCount)].map(()=>[])
        //判斷每個元素應(yīng)該進(jìn)哪個桶子
        for (let i = 0; i < arr.length; i++) {
          const index = Marh.floor((arr[i] - minValue) / bucketSize)
          buckets[index].push(arr[i])
        }
   return  buckets
      }
      function sortBucket(){
        const sortArr=[]
        for(let i=0;i<arr.length;i++){
          if(arr[i]){
            insertSort(arr[i])
            sortArr.push(...arr[i])
          }
        }
      }
      function insertSort() {
          const { length } = arr
          let temp
          for (let i = 1; i < length; i++) {
            temp = arr[i]
            j = i
            while (j > 0 && arr[j - 1] > temp) {
              arr[j] = arr[j - 1]
              j--
            }
            arr[j] = temp
          }
          console.log(arr);
        } 
  
      bucketSort([5,4,3,2,6,1,7,10,9,8])
  

  缺點是如果最大數(shù)為100，中間會創(chuàng)造很多無效桶

• 基數(shù)排序

• 填補(bǔ)了計數(shù)排序和桶排序的缺點

• 給定桶子的數(shù)量。一般是10，將數(shù)組里的數(shù)字先按照個位排序，再按十位，再百位~

• 再掌握這個思想

•     //Math.floor(x/diveder)%base
      //divider*=base
  

  以35舉例：x是35，diveder事先定義為1，base為10

• 得到十位35/1=35%10=5，得到個位35/10=3%10=3

•     let maxVal=Math.max(...arr)
      while(divider<=maxVal){
        //構(gòu)建二維數(shù)組
        const buckets = [...Array(10)].map(() => [])
        for (let val of arr) {
          buckets[Math.floor(val / divider) % base].push(val)
  //把取得個位數(shù)，十位數(shù)百位數(shù)推到bukets中
        }
        arr = [].concat(...buckets)
        divider *= base
      }
  

  去最大值作為循環(huán)結(jié)束的條件

• 用array和map的方法創(chuàng)建10個空數(shù)組。遍歷arr中元素，用Math方法取出個十百位數(shù)，推到buckets中，如：bucket[3]=3

        arr = [].concat(...buckets)
        divider *= base
  

  表示將arr數(shù)組中所有個位數(shù)取出來排好后，用concat連成數(shù)組，再排新數(shù)組中每個元素的十位數(shù)，divider*10后變成10.....

• 完整代碼

•     const arr=[35,2,26,2,5,8,34,1,56,99,33]
      function radixSort(arr){
      const  base=10
      let divider=1
      //Math.floor(x/diveder)%base//得到十位35/1=35%10=5，得到個位35/10=3%10=3
      //divider*=base
      let maxVal=Math.max(...arr)
      while(divider<=maxVal){
        //構(gòu)建二維數(shù)組
        const buckets = [...Array(10)].map(() => [])
        for (let val of arr) {
          buckets[Math.floor(val / divider) % base].push(val)//把取得個位數(shù)，十位數(shù)百位數(shù)推到bukets中
        }
        arr = [].concat(...buckets)
        divider *= base
      }
      return arr
    }

總結(jié) 

到此這篇關(guān)于js數(shù)據(jù)結(jié)構(gòu)排序的文章就介紹到這了,更多相關(guān)js數(shù)據(jù)結(jié)構(gòu)排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論