资讯专栏INFORMATION COLUMN

Javascript常见排序算法的笔记

617035918 / 734人阅读

摘要:排序算法主要针对的是数组,所以,在开始学习之前,我们先自己新建一种数据结构来方便我们的学习。统计执行次数冒泡排序比较相邻两个数的大小,如果前面的数大于后面,则交换这两个数的位置。所以我们把数列分割成不超过两个元素的数组,然后将其合并。

  排序算法主要针对的是数组,所以,在开始学习之前,我们先自己新建一种数据结构来方便我们的学习。

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

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/95585.html

相关文章

  • CSS技巧

    摘要:技巧使你的更加专业这是上关于技巧的一篇译文,另外你也可以在本项目看到原文。列举了一些很实用的技巧,比如给空内容的标签添加内容,逗号分隔列表等等。排序算法看源码,把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。 成为专业程序员路上用到的各种优秀资料、神器及框架 成为一名专业程序员的道路上,需要坚持练习、学习与积累,技术方面既要有一定的广度,更要有自己的深度。 Java...

    DangoSky 评论0 收藏0
  • CSS技巧

    摘要:技巧使你的更加专业这是上关于技巧的一篇译文,另外你也可以在本项目看到原文。列举了一些很实用的技巧,比如给空内容的标签添加内容,逗号分隔列表等等。排序算法看源码,把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。 成为专业程序员路上用到的各种优秀资料、神器及框架 成为一名专业程序员的道路上,需要坚持练习、学习与积累,技术方面既要有一定的广度,更要有自己的深度。 Java...

    zgbgx 评论0 收藏0
  • 基本方法笔记 - 收藏集 - 掘金

    摘要:探讨判断横竖屏的最佳实现前端掘金在移动端,判断横竖屏的场景并不少见,比如根据横竖屏以不同的样式来适配,抑或是提醒用户切换为竖屏以保持良好的用户体验。 探讨判断横竖屏的最佳实现 - 前端 - 掘金在移动端,判断横竖屏的场景并不少见,比如根据横竖屏以不同的样式来适配,抑或是提醒用户切换为竖屏以保持良好的用户体验。 判断横竖屏的实现方法多种多样,本文就此来探讨下目前有哪些实现方法以及其中的优...

    maochunguang 评论0 收藏0
  • JavaScript数据结构和算法

    摘要:栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构,比如下面介绍的二叉查找树。 前言 在过去的几年中,得益于Node.js的兴起,JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器,程序员发现他们需要更多传统语言(比如C++和Java)提供的工具。这些工具包括传统的数据结构(如链表,栈,队列,图等),...

    EastWoodYang 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<