资讯专栏INFORMATION COLUMN

JavaScript实现的几种排序

piapia / 2891人阅读

摘要:冒泡排序原理冒泡排序的过程就是将数组中相邻的两个元素进行比较,如果前面的元素比后面的元素要大交换位置,否则位置不变举个栗子有数组第一轮循环和比较,小于两者位置不变,接下来和比较,大于,两者交换位置,接着和比较,两者交换位置,继续和比较两者交

1.冒泡排序

原理:冒泡排序的过程就是将数组中相邻的两个元素进行比较,如果前面的元素比后面的元素要大交换位置,否则位置不变;举个栗子:有数组 arr = [3,5,4,2,1];
第一轮循环:3和5比较,3小于5两者位置不变,接下来5和4比较,5大于4,两者交换位置,接着5和2比较,5>2两者交换位置,继续5和1 比较 5>1两者交换位置,一轮后得到的数组是[3,4,2,1,5];把大的元素放到数组的最末尾,这种就像水泡样一层一层的像后移动,就是冒泡排序了;
代码实现:

</>复制代码

  1. // 记录循环次数
  2. let count = 0
  3. // 位置交换函数
  4. const change = function (arr, n1, n2) {
  5. // 用es6的实现交换
  6. [arr[n1], arr[n2]] = [arr[n2], arr[n1]]
  7. //let temp = arr[n1]
  8. //arr[n1] = arr[n2]
  9. //arr[n2] = temp
  10. }
  11. // 冒泡排序
  12. const bubbleSort = function (soucre) {
  13. let len = soucre.length
  14. for (let i = 0;i < len - 1; i++) {
  15. for (let j = 0; j < len - 1 - i;j++) {
  16. count ++
  17. if (soucre[j] > soucre[j+1]) {
  18. change(soucre, j, j+1)
  19. }
  20. }
  21. }
  22. return soucre
  23. }
  24. //验证
  25. console.log(bubbleSort([3,6,2,4,9,1,8])) // [1,2,3,4,6,8,9]
  26. console.log(count) // 21
2.选择排序

选择排序和冒泡排序类似也是依次对相邻的数进行两两比较。不同之处在于,他不是每次两两相邻比较后交换位置,他是先找出最大(最小)将它放到正确的位置,然后再寻找次最大(最小)放在正确的位置;
举个栗子:有数组 arr = [3,5,4,2,1];
先假设第一个元素是最小值,并定义一个minidx=0变量记录最小(最大)值的位置,for循环和其他元素进行比较,3和5进行比较,5>3此时不做处理,4也是一样处理,当3和2比较时,3>2,此时将minidx赋值为2的位置,接下来用arr[minidx]和剩余的元素比较遇到比他小的就用minidx记录小值的位置;最后将最小的位置值和初始给的值位置进行互换(当然是初始的值和一轮循环下来的minidx位置不一样才互换);所以一轮循环下来结果是arr = [1,5,4,2,3]
代码实现:

</>复制代码

  1. // 记录循环次数
  2. let count = 0
  3. // 选择排序
  4. const selectSort = function (soucre) {
  5. let len = soucre.length
  6. let minidx;
  7. for (let i = 0; i < len; i ++) {
  8. minidx = i
  9. for (let j = i + 1; j < len; j++) {
  10. count ++
  11. if (soucre[minidx] > soucre[j]) {
  12. minidx = j
  13. }
  14. }
  15. if (minidx !== i) {
  16. change(soucre,i,minidx)
  17. }
  18. }
  19. return soucre
  20. }
  21. console.log(selectSort([3,6,2,4,9,1,8,23,45,16,14])) // [1, 2, 3, 4, 6, 8, 9, 14, 16, 23, 45]
  22. console.log(count) // 55
3.插入排序

原理:将数组分为已排序和未排序,将第一个元素看作是已排序的元素,而其他是未排序的,从未排序的里面取出一元素和已排序元素进行比较,并插入到正确位置,这样已排序部分增加一个元素,而未排序的部分减少一个元素。直到排序完成
举个栗子:有数组 arr = [1,5,4,2,3],第一次假设元素1 是已排序部分,5,4,2,3为未排序,取出元素5加入已排序部分,5>1,已排序部分为1,5;而未排序部分为4,2,3;如此往复完成排序;
代码实现:

</>复制代码

  1. const insertSort = function (source) {
  2. let len = source.length
  3. let value
  4. let j
  5. let i
  6. for (i = 0; i < len; i++) {
  7. value = source[i]
  8. // 已排序部分进行元素的右移一位,并把目标值value插入到对应的位置
  9. for (j = i -1 ;j > -1 && source[j] > value; j--) {
  10. source[j+1] = source[j]
  11. }
  12. source[j+1] = value
  13. }
  14. return source
  15. }
  16. console.log(insertSort([3,6,2,4,9,1,8])) // [1,2,3,4,6,8,9]
4.归并排序

原理: 将两个已经排序的数组合并,要比从头开始排序所有元素来得快。因此,可以将数组拆开,分成n个只有一个元素的数组,然后不断地两两合并,直到全部排序完成
代码实现:

</>复制代码

  1. const mergeSort = function mergeSort(source) {
  2. let len = source.length
  3. if (len < 2) {
  4. return source
  5. }
  6. let mid = Math.floor(len/2)
  7. let left = source.slice(0,mid)
  8. let right = source.slice(mid)
  9. return merge(mergeSort(left), mergeSort(right))
  10. }
  11. function merge(left, right) {
  12. let result = []
  13. while (left.length && right.length) {
  14. if (left[0] <= right[0]) {
  15. result.push(left.shift())
  16. } else {
  17. result.push(right.shift())
  18. }
  19. }
  20. while (left.length){
  21. result.push(left.shift())
  22. }
  23. while (right.length){
  24. result.push(right.shift())
  25. }
  26. return result
  27. }
  28. console.log(mergeSort([4,8,1,3,5,9,6])) // [1,3,4,5,6,8,9]
5.快速排序

原理:快速排序是目前公认的速度快和高效的排序方式,时间复杂度O(nlogn)是比较理想的状态,他的实现过程是,先在数组找到一个基点,把大于这个基点的值放到右侧,小于基点的值放到左侧,再将右侧的和左侧的也按照这种方式再次分配,直到完成排序
举个栗子:有一个数组 arr = [1,5,4,2,3];假设我们找数组的中间点作为基点也就是4,那一轮循环后结果就是[1,2,3,4,5] ->_->怎么这么巧,一轮就OK,果然是快速排序,就是快 哈哈,当然程序不会这么做,他是严谨的,他还会去拆分[1,2,3]只是这个实际上已经是排好了的;
代码实现:粗糙一点的

</>复制代码

  1. const quire = function quire(source) {
  2. if(source.length < 2) return source
  3. let left = []
  4. let right = []
  5. let len = source.length
  6. let key = source[Math.floor(len/2 -1)]
  7. for (let i = 0;i key){
  8. right.push(source[i])
  9. }
  10. }
  11. return [].concat(quire(left),key,quire(right))
  12. }

上面这种方法缺点就是空间浪费,他会创建很多个left 和 right 这样的数组,造成空间的浪费,当数据量一大的话还是很恐怖的,所以我们要改进的就是,不新建中间数组,而是直接修改位移目标数组;

改进原理: 选取一个基点,从数组的两头两个指针分别向基点位移,位移的原则是,基点的左边的元素如果小于基点,那就像基点位置靠拢一位,i++,如果大于基点就原地不动,基点右边的元素反过来,如果大于基点就像基点靠拢一位,j--;如果小于就原地不动;这时再比较两个原地不动的点,如果右边的不动点小于左边的值,就互换他们的位置;

代码实现:

</>复制代码

  1. // 位置交换
  2. const change = function (arr, n1, n2) {
  3. // let temp = arr[n1]
  4. // arr[n1] = arr[n2]
  5. // arr[n2] = temp
  6. // 用es6的实现交换
  7. [arr[n1], arr[n2]] = [arr[n2], arr[n1]]
  8. }
  9. const quiregai = function quiregai(source, start, end) {
  10. let pivot = source[Math.floor((start + end)/2)]
  11. let i = start // 左边指针初始位置
  12. let j = end // 右边指针初始位置
  13. while(i<=j) {
  14. while (source[i] < pivot) {
  15. i ++ // 左指针右移
  16. }
  17. while (source[j] > pivot) {
  18. j -- // 右指针左移
  19. }
  20. if (i <= j){
  21. change(source,i,j) // 交换两个位置的值
  22. i++
  23. j--
  24. }
  25. }
  26. return i // 返回一轮循环后左指针的位置,为下一轮循环初始位置确定
  27. }
  28. const quiregaiSort = function quiregaiSort(source, start, end) {
  29. if (source.length < 2) return source
  30. var start = start || 0
  31. var end = end || source.length - 1
  32. var nextStart = quiregai(source, start, end)
  33. // debugger
  34. if (start < nextStart -1) {
  35. quiregaiSort(source, start, nextStart -1 ) // 上个循环结束的左指针作为左边区块循环的右指针
  36. }
  37. if (nextStart < end) {
  38. quiregaiSort(source, nextStart, end) // 上个循环结束的左指针作为右边区块循环的左指针
  39. }
  40. return source
  41. }
  42. console.log(quiregaiSort([4,1,9,3,7,5,76,21,12,53,24]))

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

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

相关文章

  • 基本方法笔记 - 收藏集 - 掘金

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

    maochunguang 评论0 收藏0
  • Javascript算法——快速排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。这里主要介绍快速排序。快速排序是一种既不浪费空间又可以快一点的排序算法。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。这里主要介绍快速排序。 一图胜千言: showImg(https://segmentfault.com/img/bVNIpc?...

    马忠志 评论0 收藏0
  • 2018年5月前端面试题

    摘要:在上家公司裸辞之后,经过一段时间休整,月中下旬面试了一些公司,由于本人框架使用的是,所以面试题涉及到框架的都是,现将面试题整理一下列举常用的特性。事件冒泡以及事件捕获。其他前端分页和后端分页优缺点。包含多个子节点及孙节点,遍历。 在上家公司裸辞之后,经过一段时间休整,5月中下旬面试了一些公司,由于本人框架使用的是vue,所以面试题涉及到框架的都是vue,现将面试题整理一下: es6 ...

    wwolf 评论0 收藏0
  • 2018年5月前端面试题

    摘要:在上家公司裸辞之后,经过一段时间休整,月中下旬面试了一些公司,由于本人框架使用的是,所以面试题涉及到框架的都是,现将面试题整理一下列举常用的特性。事件冒泡以及事件捕获。其他前端分页和后端分页优缺点。包含多个子节点及孙节点,遍历。 在上家公司裸辞之后,经过一段时间休整,5月中下旬面试了一些公司,由于本人框架使用的是vue,所以面试题涉及到框架的都是vue,现将面试题整理一下: es6 ...

    Lavender 评论0 收藏0
  • mgo做分页几种方法

    摘要:场景当数据两足够大的时候,一页展示不完的时候,我们经常会需要分页的功能。方案三,数据比较大,排序需要排序当数据量比较大的时候,并且需要排序的时候,可以使用这种情况。 场景 当数据两足够大的时候,一页展示不完的时候,我们经常会需要分页的功能。 方案 方案一,数据不是很大 需要排序 s := globalS.Copy() c := s.DB(db).C(collection...

    Terry_Tai 评论0 收藏0

发表评论

0条评论

piapia

|高级讲师

TA的文章

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