算法 排序

排序算法归纳

Posted by WWJ on May 21, 2018

排序算法总结

插入排序

  1. 场景： 假设桌子上有一副扑克牌，首先拿起第一张牌放在左手中，当左手中只有一张扑克牌的时候，扑克牌的顺序肯定是有序的，然后我们每次从桌子上拿出一张牌（假设为key）后，都需要在左手中的牌中找到一个正确的位置进行插入，方法就是从右到左将它依次与左手的中牌进行比较，找到一个正确的位置（如果是升序的话，那么就找到第一个比它小的牌，如果是降序的话，那么就找到第一个比它大的牌） 升序：找到第一个比key小的牌，而且在比较的过程中，比key大的牌都需要往后移一步，最后再交换key和比key小的那张牌的位置 降序：找到第一个比key大的牌，而且在比较的过程中，比key小的牌都需要往后移一步，最后再交换key和比key大的那张牌的位

  2. 算法实现：

    const insertSort = function(arr) {
 //从第二张牌开始遍历
 for(let i = 1; i < arr.length; i++) {
     let key = arr[i]
     let point = i - 1
     while(point >= 0 && arr[point] > key) {
         arr[point+1] = arr[point]//大于key的元素需要往后移动一步
         point--
     }
     //最后交换key与比key小的元素的位置
     arr[point + 1] = key
 }
}

    所以这里就出现了一个循环不变式：即在arr[0, i - 1]中的元素都是有序的，对应左手中已经排好序的牌，arr[i + 1, arr.length - 1]对应桌子上待排序的牌

归并排序

  1. 算法思想-拆分数组：将序列分成左右两部分，再将左右两部分的序列继续分割成更小的两部分，以此类推，直到所有的序列里只存在一个元素，最后再递归地将左右两部分的序列合并成一个有序的序列
  2. 算法思想-合并数组：
    • 先声明一个空间为这两个序列长度和的合并序列，用来存放最后排好序的元素
    • 比较比较两个序列的第一个元素，如果左边序列的第一个元素大于右边序列的第一个元素，那么就将左边序列的第一个元素加入到合并序列中，然后将该元素从原始数组中删除，如果右边序列的第一个元素大于左边序列的第一个元素，那么就将右边序列的第一个元素加入到合并序列中，然后将该元素从原始数组中删除，直到其中一个序列已经为空
    • 将另一序列剩余的元素加到合并序列的尾部
  3. 代码实现： 
    Array.prototype.merge_sort = function() {
 const merge = function(left, right) {
     let result = []
     while(left.length && right.length) {
         result.push(left[0] <= right[0] ? left.shift() : right.shift())
     }
     return result.concat(left.concat(right))
 }
 if(this.length < 2) return this
 let mid = Math.floor(this.length / 2)
 return merge(this.slice(0, mid).merge_sort(), this.slice(mid).merge_sort())
}

    堆排序（O（nlgn））

    堆是一种近似于完全二叉树的数据结构，该树上的每个结点对应于数组中的一个元素，除了最底层外，该树是完全满的，而且是从左到右依次填充，且每个根结点总是比它的孩子结点大（或者小） 算法思想：

    • 构建最大堆（即满足每个根结点总是比它的孩子结点大）(buildMaxHeap)
    • 将堆的最后一个结点与第一个结点交换（exange）
    • 输出堆的最后一个结点并删除
    • 重新调整堆的顺序（maxHeapify）

在数组中，如果根结点的索引是i，那么左孩子的索引就是idx * 2 + 1，右孩子的索引就是idx * 2 +2（假设是从索引0开始遍历数组） 代码实现：

Array.prototype.heapSort = function () {
    let res = [], arr = this.slice(0)
    //构建最大堆
    const buildMaxHeap = (len) => {
        len = Math.floor(len / 2)
        for (let i = len - 1; i >= 0; i--) {
            maxHeapify(arr, i)
        }
    }
    //重新调整堆，因为可能在交换了数组中的第一个元素和最后一个元素之后，数组就不满足堆的性质了
    const maxHeapify = (arr, idx) => {
        let left = idx * 2 + 1
        let right = idx * 2 + 2
        let largest = idx
        if (arr[left] > arr[idx]) largest = left
        if (arr[right] > arr[largest]) largest = right
        if (largest !== idx) {
            swap(arr, largest, idx)
            maxHeapify(arr, largest)
        }
    }
    swap = function(arr, i, j) {
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
    }
    buildMaxHeap(arr.length)//保证数组中的第一个元素是最大的
    for (let i = arr.length - 1; i >= 0; i--) {
        swap(arr, i, 0)
        res.push(arr[i])
        arr.pop()
        maxHeapify(arr, 0)
    }
    return res
}
const arr = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4]
console.log(arr.heapSort())

利用堆排序构建优先队列

优先队列中的每个元素都有自己的优先级，优先级高的先得到服务，优先级相同的按元素在队列中出现的顺序得到服务 最大优先队列：

  • insert（val）将val插入到队列中，插入完成后按val从大到小的顺序更新每个元素在队列中的位置
  • extractMax()删除并返回队列val最大的元素，因为排好序之后最大元素就是队列中的第一个，所有无需更新队列
  • getMaximum()返回队列中val最大的元素
  • increaseKey(idx, newVal)将优先队列中的索引为idx的值修改为newVal，修改后队列可能会不符合最大堆的性质，即需要更新队列 
    function MaxQueue() {
  this.min = Number.MAX_VALUE
  this.queue = []
}
//向优先队列中插入一个元素
MaxQueue.prototype.insert = function (val) {
  this.queue.push(val)
  this.queue = this.queue.heapSort()
  this.max = this.queue[0]            
}
//返回优先队列中最大的元素
MaxQueue.prototype.getMaximum = function() {
  return this.queue[0]
}
//删除并返回优先队列中最大的元素
MaxQueue.prototype.extractMax = function() {
  let max = this.queue.shift()
  // this.queue.heapSort()
  return max
}
//将优先队列中的索引为idx的值修改为newVal
MaxQueue.prototype.increaseKey = function(idx, newVal) {
  if(idx >= this.queue.length) return
  this.queue[idx] = newVal
  this.queue = this.queue.heapSort()
}
let maxQueue = new MaxQueue()
for (let i = 0; i < 10; i++) {
  maxQueue.insert(i)
}
maxQueue.increaseKey(7, 11)
// console.log(maxQueue.extractMax())
console.log(maxQueue.queue)

    最小优先队列：

  • insert（val）将val插入到队列中，插入完成后按val从小到大的顺序更新每个元素在队列中的位置
  • extractMin()删除并返回队列val最大的元素，因为排好序之后最大元素就是队列中的第一个，所有无需更新队列
  • getMinimum()返回队列中val最小的元素
  • increaseKey(idx, newVal)将优先队列中的索引为idx的值修改为newVal，修改后队列可能会不符合最小堆的性质，即需要更新队列

更新调整堆的方法

const minHeapify = (arr, idx) => {
    let left = idx * 2 + 1
    let right = idx * 2 + 2
    let largest = idx
    if (arr[left] < arr[idx]) largest = left
    if (arr[right] < arr[largest]) largest = right
    if (largest !== idx) {
        swap(arr, largest, idx)
        maxHeapify(arr, largest)
    }
}

其余逻辑和实现最大优先队列一模一样

快速排序

最坏情况：当序列完全有序时（升序或者降序），时间复杂度为O(n^2) 最好情况：每次用分治策略将序列划分为两部分时，该两部分的元素个数基本相等 算法思想：

  • 将序列分成左右两个子序列，如果要实现升序的话，那么左边序列中的所有元素都要小于基准值，右边序列中的所有元素都要大于基准值，如果要实现降序的话，那么左边序列中的所有元素都要大于基准值，右边序列中的所有元素都要小于基准值，基准值一般设置为被分割的父序列的最后一个元素
  • 然后利用分治策略将子序列再分割成更小的两部分 代码实现： 
    Array.prototype.swap = function(i, j) {
  let tmp = this[i]; this[i] = this[j]; this[j] = tmp;
}
Array.prototype.quickSort = function(low, high) {
  const partition = function(arr, low, high) {
      let key = arr[high], start = low - 1
      for(let i = low; i < high; i++) {
          if(arr[i] < key) {
              start++
              arr.swap(start, i)
          } 
      }
      arr.swap(start + 1, high)
      return start + 1
  }
  if(low < high) {
      let idx = partition(this, low, high)
      this.quickSort(low, idx - 1)
      this.quickSort(idx + 1, high)
  }
}
const arr = [3,4,1,6,9,5,12,7,4,6,1,2,8,12]
arr.quickSort(0, arr.length - 1)
console.log(arr)

    计数排序

  • 计数排序对数组中的每一个元素都是0-k区间的一个整数，它的运行时间是O(n + k)，计数排序不是比较排序，它的排序时间快于任何比较排序算法
  • 由于用来计数的数组长度取决于待排序数组中的数据范围（最大值-最小值+1），所以对于数据范围很大的数组，计数排序就需要很大的内存和时间 算法思想：遍历数组，对于当前遍历的元素，找出小于当前元素的个数，根据这一信息，就能确定当前元素应该放在什么位置。比如元素x，有17个小于x，那么元素x就放在地18个位置，如果有相等的情况，这一策略要稍作修改 在程序运行过程中，我们需要开辟两个额外的数组，一个是计数数组，用来存放元素i在数组中出现的次数，一个是用来存放已经找到正确位置的元素的数组 实现步骤：
  • 找到数组中的最大和最小值（计数数组C的空间长度 = 最大值 - 最小值 + 1）
  • 统计元素i在数组中出现的次数，并存入计数数组中C
  • 对计数数组中的每个元素进行累加
  • 对于每一个元素，找到一个正确的位置并存入数组B中

代码实现：

Array.prototype.range = function() {
    let max = Number.MIN_VALUE
    let min = Number.MAX_VALUE
    for(let i = 0; i < this.length; i++) {
        max = Math.max(max, this[i])
        min = Math.min(min, this[i])
    }
    return max - min + 1
}
Array.prototype.countSort = function(radix) {
    let C = new Array(this.range()+1).fill(0)
    let B = new Array(this.length).fill(0)
    for(let i = 0; i < this.length; i++) {
        C[this[i]]++
    }
    
    for(let i = 1; i <= this.range(); i++) {
        C[] = C[i - 1] + C[i]
    }
    for(let i = this.length - 1; i >= 0; i--) {
        B[C[this[i]] - 1] = this[i]
        C[this[i]]--
    }
    for(let i = 0; i < this.length; i++) {
        this[i] = B[i]
    }
}
const arr = [1,4,2,6,8,1,3,4,6]
arr.countSort()
console.log(arr)

基数排序

算法思想：将数组中的每个元素按数位分割成不同的数字，然后每次比较相同数位上的数字以此来调整数组中元素顺序。基数排序在按每个数位分别比较的过程中用到了计数排序。基数排序的时间复杂度为O(K + N)，K代表数位，N代表元素的个数 代码实现：

 Array.prototype.digit = function () {
    let max = Number.MIN_VALUE
    let digit = 1
    for (let i = 0; i < this.length; i++) {
        max = Math.max(max, this[i])
    }
    while (max >= 10) {
        max = Math.floor(max / 10)
        digit++
    }
    return digit
}
Array.prototype.radixSort = function () {
    let digit = this.digit()
    let count = Array(10), res = Array(this.length), radix = 1
    for (let i = 1; i <= digit; i++) {
        count.fill(0)
        for (let j = 0; j < this.length; j++) {
            let divisor = Math.floor(this[j] / radix)
            count[divisor % 10]++
        }
        for (let j = 1; j < 10; j++) {
            count[j] = count[j - 1] + count[j]
        }
        for (let j = this.length - 1; j >= 0; j--) {
            let divisor = Math.floor(this[j] / radix)
            res[count[divisor % 10] - 1] = this[j]
            count[divisor % 10]--
        }
        for (let j = 0; j < this.length; j++) {
            this[j] = res[j]
        }
        radix *= 10
    }
}
const arr = [1, 4, 2, 896, 8, 1, 3, 434, 6]
arr.radixSort()
console.log(arr)
CATALOG