Javascript常見排序算法的筆記

617035918 發(fā)布于2019-08-22 18:11 / 773人閱讀

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

??排序算法主要針對(duì)的是數(shù)組，所以，在開始學(xué)習(xí)之前，我們先自己新建一種數(shù)據(jù)結(jié)構(gòu)來方便我們的學(xué)習(xí)。

function ArrayData () {
  let ret = []
  this.times = 0  // 統(tǒng)計(jì)執(zhí)行次數(shù)
  this.push = (item) => {
    ret.push(item)
  }
  this.toString = () => {
    return ret.join()
  }
}

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

冒泡排序

??比較相鄰兩個(gè)數(shù)的大小，如果前面的數(shù)大于后面，則交換這兩個(gè)數(shù)的位置。要排序n個(gè)數(shù)字，需要經(jīng)歷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

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

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

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

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

選擇排序

??遍歷數(shù)組，找出最小的數(shù)排在第一位，第二輪循環(huán)找出第二小的數(shù)放在第二位，以此類推。

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()

插入排序

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

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()

快速排序

??選一個(gè)數(shù)作為基準(zhǔn)數(shù)，遍歷數(shù)列，把比它
放到他前面，比他小的放到他后面，然后再對(duì)基準(zhǔn)數(shù)前后的數(shù)列遞歸上述操作，直到數(shù)列長度為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()

??一句話實(shí)現(xiàn)快速排序。選擇第一個(gè)元素作為參考元素，利用filter把數(shù)組分成大于參考元素和小于參考元素的兩個(gè)數(shù)組，并對(duì)這兩個(gè)數(shù)組遞歸調(diào)用快排函數(shù)。

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])))
}

希爾排序

??希爾排序是把數(shù)組按下標(biāo)的一定增量分組，對(duì)每組進(jìn)行插入排，隨著增量逐漸減少，每個(gè)數(shù)組的長度越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

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()

歸并排序

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

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()