资讯专栏INFORMATION COLUMN

js排序算法(一)

v1 / 2442人阅读

摘要:冒泡排序算法即相邻的两个元素进行比较,如果前一个元素比后一个元素大,则将这两个元素换位,即将较大的元素后置。重复操作,每次都将的值折半比较,直到,唯的时候排序操作结束。归并排序通过递归的方式不断的合并两个有序数组完成数组的排序

1. 冒泡排序算法: 即相邻的两个元素进行比较,如果前一个元素比后一个元素大,则将这两个元素换位,即将较大的元素后置。

内循环每走一次都会将前length - i个元素中的最大元素放到length - i 的位置上。

var data = [1, 49, 30, 80, 6, 2, 18, 15, 23, 78, 16, 5, 4, 2, 34, 35, 46, 18]
function bubble(arr) {
  var length = arr.length
  for (var i = 0; i < length; i++) {
    for(var j = 0; j < length - 1 -i; j++) {
      var temp = arr[j]
      if (arr[j] > arr[j+1]) {
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
    }
  }
  console.log(arr)
}

bubble(data)
2. 选择排序算法: 每次循环都选择最小值,然后将其与当前位置的值进行互换操作即可
function select(arr) {
  var minIndex
  var temp
  for (var i = 0; i < arr.length-1; i++) {
    minIndex = i
    for(var j = i + 1; j < arr.lenght - i - 1; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    temp = arr[i]
    arr[i] =  arr[minIndex]
    arr[minIndex] = temp
  }
  console.log(arr)
}
select(data)
3. 插入排序: 如果前一个的值比当前值小则二者换位, 直到将这个碰见比前一个值小的数为止
function insert(arr) {
  for (var i=1; i= 0 && arr[preIndex] > current) {
      arr[preIndex+1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex+1] = current
  }
  console.log(arr)
}
insert(data)
4. 希尔排序: 先将arr分成arr.length/2组,其中index=1和index=length/2 + 1为一组,

如果length/2的值比较小则互换位置。重复操作,每次都将gap的值折半比较,
直到,gap唯1的时候排序操作结束。

function shell(arr) {
  function swap(array, i, k) {
    var temp = array[i]
    array[i] = array[k]
    array[k] = temp
  }
  var gap = Math.floor(arr.length / 2)
  while(gap > 0) {
    for(var i=gap; i0; j-=gap) {
        if (arr[j-gap] > arr[j]) {
          swip(arr, j-gap, j)
        }
      }
    }
     gap = Math.floor(gap / 2)
  }
  console.log(arr)
}
shell(data)
5. 归并排序: 通过递归的方式不断的合并两个有序数组完成数组的排序
function mergeSort(arr) {
  var len = arr.length;
  if (len < 2) {
    return arr
  }
  var middle = Math.floor(len / 2)
  var left = arr.slice(0, middle)
  var right = arr.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());
    return result;
}
console.log(mergeSort(data))

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

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

相关文章

  • JS数据结构与算法_排序和搜索算法

    摘要:上一篇数据结构与算法树写在前面这是学习数据结构与算法的最后一篇博客,也是在面试中常常会被问到的一部分内容排序和搜索。 上一篇:JS数据结构与算法_树 写在前面 这是《学习JavaScript数据结构与算法》的最后一篇博客,也是在面试中常常会被问到的一部分内容:排序和搜索。在这篇博客之前,我每每看到排序头就是大的,心里想着类似冒泡排序,两层遍历啪啪啪就完事了,然后再也无心去深入研究排序相...

    姘搁『 评论0 收藏0
  • 使用JS实现三种基本的排序算法以及三种算法的比较

    摘要:介绍排序算法是算法中最常见的算法之一,我这里要介绍的是排序算法中的三种基本算法冒泡排序选择排序插入排序,在文章的后面我会对三种算法的速度进行对比。 1.介绍 排序算法是算法中最常见的算法之一,我这里要介绍的是排序算法中的三种基本算法:冒泡排序、选择排序、插入排序,在文章的后面我会对三种算法的速度进行对比。 2.冒泡排序 冒泡排序其名来源与其算法实现,会使得数组中的元素一个个从数组一端漂...

    wh469012917 评论0 收藏0
  • 排序算法分析总结(附js实现)

    摘要:本文对一些排序算法进行了简单分析,并给出了的代码实现。平均时间复杂度不好分析,它是冒泡排序是稳定的排序算法。冒泡排序是原地排序算法原地排序指的是空间复杂度是的排序算法。归并排序,会将数组从中间分成左右两部分。 本文对一些排序算法进行了简单分析,并给出了 javascript 的代码实现。因为本文包含了大量的排序算法,所以分析不会非常详细,适合有对排序算法有一定了解的同学。本文内容其实不...

    liaoyg8023 评论0 收藏0
  • JS排序算法

    摘要:冒泡排序冒泡算法是比较相邻的两项,如果前者比后者大,就交换他们。插入排序最好情况下时间复杂度是,其他情况下也都是。代码演示插入排序归并排序原生里面的方法,在里面是用归并排序实现的,而在里面是用快速排序的变体来实现的。 1、冒泡排序 冒泡算法是比较相邻的两项,如果前者比后者大,就交换他们。 假设一共有n项,那么一共需要n-1趟,第一趟需要交换n-1次,但是第一趟结束后,最后一项基本确定就...

    notebin 评论0 收藏0
  • JS排序算法

    摘要:冒泡排序冒泡算法是比较相邻的两项,如果前者比后者大,就交换他们。插入排序最好情况下时间复杂度是,其他情况下也都是。代码演示插入排序归并排序原生里面的方法,在里面是用归并排序实现的,而在里面是用快速排序的变体来实现的。 1、冒泡排序 冒泡算法是比较相邻的两项,如果前者比后者大,就交换他们。 假设一共有n项,那么一共需要n-1趟,第一趟需要交换n-1次,但是第一趟结束后,最后一项基本确定就...

    sihai 评论0 收藏0
  • JS中可能用得到的全部的排序算法

    本篇有7k+字, 系统梳理了js中常见的12种排序算法。除了基本排序算法,文章还包含了希尔排序、堆排序、桶排序等较为复杂的排序实现,如果喜欢请点赞支持~谢谢. 原文: http://louiszhai.github.io/20... 导读 排序算法可以称得上是我的盲点, 曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时, 我的内心是奔溃的(啥是快排, 我只知道...

    verano 评论0 收藏0

发表评论

0条评论

v1

|高级讲师

TA的文章

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