Javascript常見排序算法的筆記

617035918 發布于2019-08-22 18:11 / 780人閱讀

摘要：排序算法主要針對的是數組，所以，在開始學習之前，我們先自己新建一種數據結構來方便我們的學習。統計執行次數冒泡排序比較相鄰兩個數的大小，如果前面的數大于后面，則交換這兩個數的位置。所以我們把數列分割成不超過兩個元素的數組，然后將其合并。

??排序算法主要針對的是數組，所以，在開始學習之前，我們先自己新建一種數據結構來方便我們的學習。

function ArrayData () {
  let ret = []
  this.times = 0  // 統計執行次數
  this.push = (item) => {
    ret.push(item)
  }
  this.toString = () => {
    return ret.join()
  }
}

const arr = [34, 11, 45, 22, 31, 99, 68, 54]

冒泡排序

??比較相鄰兩個數的大小，如果前面的數大于后面，則交換這兩個數的位置。要排序n個數字，需要經歷n-1次的遍歷。

??按照字面要求，我們寫出來的代碼是這樣的

function ArrayData () {
    // ......
    this.bubbleSort = function () {
        let length = ret.length;
        for (let i = 0; i < length; i++) {
          for (let j = 0; j < length - 1; j++) {
            this.times++
            if (ret[j] > ret[j + 1]) {
              [ret[j], ret[j + 1]] = [ret[j + 1], ret[j]]
            }
          }
        }
    }
}

let tmp = new ArrayData()
arr.forEach((item) => {
    tmp.push(item)
})
tmp.bubbleSort()
console.log(tmp.times)    //  56

??顯然這種簡單粗暴的排序方式有很大的提升空間，比如，我們可以檢測每次排序，如果順序已經排列成功，就沒必要執行之后的循環了。

function ArrayData () {
    // ......
    this.bubbleSort = function () {
        let length = ret.length;
        for (let i = 0; i < length; i++) {
          let change = false
          for (let j = 0; j < length - 1; j++) {
            this.times++?
            if (ret[j] > ret[j + 1]) {
              [ret[j], ret[j + 1]] = [ret[j + 1], ret[j]]
              change = true
            }
          }
          if (!change) {
            break
          }
        }
    }
}

let tmp = new ArrayData()
arr.forEach((item) => {
    tmp.push(item)
})
tmp.bubbleSort()
console.log(tmp.times)    //  21

??其實還是有優化的空間的。舉個例子，假設一共8個數，第一輪循環，會把最大的數冒泡排到第8位，第二輪循環，會把第二大的數排到第7位，所以，本輪循壞其實沒必要考慮最后一位了。同理，下一輪循環就不需要考慮后兩位。改進后的代碼如下:

function ArrayData () {
    // ......
    this.bubbleSort = function () {
        let length = ret.length;
        for (let i = 0; i < length; i++) {
          let change = false
          for (let j = 0; j < length - 1 - i; j++) {
            this.times++
            if (ret[j] > ret[j + 1]) {
              [ret[j], ret[j + 1]] = [ret[j + 1], ret[j]]
              change = true
            }
          }
          if (!change) {
            break
          }
        }
    }
}

let tmp = new ArrayData()
arr.forEach((item) => {
    tmp.push(item)
})
tmp.bubbleSort()
console.log(tmp.times)    //  18

選擇排序

??遍歷數組，找出最小的數排在第一位，第二輪循環找出第二小的數放在第二位，以此類推。

function ArrayData () {
    // ......
  this.selectionSort = function () {
    let length = ret.length
    for (let i = 0; i < length - 1; i++) {
      let minIndex = i
      for (let j = i; j < length; j++) {
        if (ret[j] < ret[minIndex]) {
          minIndex = j
        }
      }
      if (i !== minIndex) {
        [ret[i], ret[minIndex]] = [ret[minIndex], ret[i]]
      }
    }
  }
}

let tmp = new ArrayData()
arr.forEach((item) => {
    tmp.push(item)
})
tmp.selectionSort()

插入排序

??把數組分成前后兩部分，前面的一部分是排好序的，然后分別把后面一部分的數字插入到前面排好序的數組中。所以，剛開始時設定第一個元素為排好序的部分，分別把后面的數字插入進來。

function ArrayData () {
    // ......
  this.insertSort = function () {
    let length = ret.length
    let j
    for (let i = 1; i < length; i++) {
      let currentNumber = ret[i]
      for (j = i - 1; j >= 0 && ret[j] > currentNumber; j--) {
        ret[j + 1] = ret[j] 
      }
      ret[j + 1] = currentNumber 
    }
  }
}

let tmp = new ArrayData()
arr.forEach((item) => {
    tmp.push(item)
})
tmp.insertSort()

快速排序

??選一個數作為基準數，遍歷數列，把比它
放到他前面，比他小的放到他后面，然后再對基準數前后的數列遞歸上述操作，直到數列長度為1。

function ArrayData () {
    // ......
    this.quickSort = function () {
        quick(ret, 0, ret.length - 1);
    
        function quick(array, left, right) {
          let index
          if (array.length > 1) {
            index = partition(array, left, right)
            if (left < index - 1) {
              quick(array, left, index - 1)
            }
            if (right > index) {
              quick(array, index, right)
            }
          }
          return array
        }
    
        function partition(array, left, right) {
          let pivot = array[Math.floor((right + left) / 2)],
            i = left,
            j = right;
          while (i <= j) {
            while (array[i] < pivot) {
              i++
            }
            while (array[j] > pivot) {
              j--
            }
            if (i <= j) {
              swap(array, i, j);
              i++;
              j--;
            }
          }
          return i
        }
    
        function swap(array, i, j) {
          [array[i], array[j]] = [array[j], array[i]]
        }
    }
}

let tmp = new ArrayData()
arr.forEach((item) => {
  tmp.push(item)
})
tmp.quickSort()

??一句話實現快速排序。選擇第一個元素作為參考元素，利用filter把數組分成大于參考元素和小于參考元素的兩個數組，并對這兩個數組遞歸調用快排函數。

function quickSort(arr) {
  return arr.length <= 1 ? arr : quickSort(arr.slice(1).filter((item) => item <= arr[0])).concat(arr[0], quickSort(arr.slice(1).filter((item) => item > arr[0])))
}

希爾排序

??希爾排序是把數組按下標的一定增量分組，對每組進行插入排，隨著增量逐漸減少，每個數組的長度越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

function ArrayData () {
    // ......
  this.shellSort = function () {
    let length = ret.length
    for (let step = Math.floor(length / 2); step > 0; step = Math.floor(step / 2)) {
      for (let i = 0; i < step; i++) {
        shellInsertSort(i, step)
      }
    }

    function shellInsertSort(index, step) {
      let length = ret.length
      let j
      for (let i = index; i < length; i += step) {
        let currentNumber = ret[i]
        for (j = i - step; j >= 0 && ret[j] > currentNumber; j -= step) {
          ret[j + step] = ret[j]
        }
        ret[j + step] = currentNumber
      }
    }
  }
}

let tmp = new ArrayData()
arr.forEach((item) => {
  tmp.push(item)
})
tmp.shellSort()

歸并排序

??歸并排序采用分治的思想，將已有序的子序列合并，得到完全有序的序列。所以我們把數列分割成不超過兩個元素的數組，然后將其合并。

function ArrayData () {
    // ......
  this.mergeSort = function () {
    ret = mergeSortFun(ret)

    function mergeSortFun(arr) {
      let length = arr.length
      if (length <= 1) {
        return arr
      }
      let mid = Math.floor(length / 2),
        left = arr.slice(0, mid),
        right = arr.slice(mid, length)
      return mengeConnect(mergeSortFun(left), mergeSortFun(right))
    }

    function mengeConnect(left, right) {
      let
        leftIndex = 0,
        rightIndex = 0,
        result = []
      while (leftIndex < left.length && rightIndex < right.length) {
        result.push(left[leftIndex] < right[rightIndex] ? left[leftIndex++] : right[rightIndex++])
      }
      while (leftIndex < left.length) {
        result.push(left[leftIndex++])
      }
      while (rightIndex < right.length) {
        result.push(right[rightIndex++])
      }
      return result
    }
  }
}

let tmp = new ArrayData()
arr.forEach((item) => {
  tmp.push(item)
})
tmp.mergeSort()

云服務器 GPU云服務器字母的排序算法最好的排序算法選擇排序的算法過程最好的快速排序算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/95585.html

CSS技巧

摘要：技巧使你的更加專業這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內容的標簽添加內容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。成為專業程序員路上用到的各種優秀資料、神器及框架成為一名專業程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

DangoSky 2019-08-22 11:15 評論0 收藏0
CSS技巧

摘要：技巧使你的更加專業這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內容的標簽添加內容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。成為專業程序員路上用到的各種優秀資料、神器及框架成為一名專業程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

zgbgx 2019-08-29 14:01 評論0 收藏0
基本方法筆記 - 收藏集 - 掘金

摘要：探討判斷橫豎屏的最佳實現前端掘金在移動端，判斷橫豎屏的場景并不少見，比如根據橫豎屏以不同的樣式來適配，抑或是提醒用戶切換為豎屏以保持良好的用戶體驗。探討判斷橫豎屏的最佳實現 - 前端 - 掘金在移動端，判斷橫豎屏的場景并不少見，比如根據橫豎屏以不同的樣式來適配，抑或是提醒用戶切換為豎屏以保持良好的用戶體驗。判斷橫豎屏的實現方法多種多樣，本文就此來探討下目前有哪些實現方法以及其中的優...

maochunguang 2019-08-20 17:44 評論0 收藏0
JavaScript數據結構和算法

摘要：棧被稱為一種后入先出的數據結構。散列使用的數據結構叫做散列表。這些操作需要求助于其他數據結構，比如下面介紹的二叉查找樹。前言在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務器端編程。鑒于JavaScript語言已經走出了瀏覽器，程序員發現他們需要更多傳統語言（比如C++和Java）提供的工具。這些工具包括傳統的數據結構（如鏈表，棧，隊列，圖等），...

EastWoodYang 2019-08-21 16:23 評論0 收藏0