JS排序算法

时间:2022-09-26 20:47:20

1、冒泡排序

冒泡算法是比较相邻的两项,如果前者比后者大,就交换他们。

假设一共有n项,那么一共需要n-1趟,第一趟需要交换n-1次,但是第一趟结束后,最后一项基本确定就是最大项了,所以第二次需要交换n-2次,第i次交换n-i次。

JS排序算法

这种排序最好情况下时间复杂度是O(n),一般情况下时间复杂度是O(n²),最差情况下也是O(n²)。

这里是代码演示:

http://codepen.io/Krystal/pen/bZXOpo?editors=1010

2、选择排序

选择排序是找到最小的一项,然后和第一项交换位置,然后找到第二小的和第二项交换,依次类推,一共需要n-1次。

JS排序算法

选择排序在所有情况下空间复杂度都是O(n²)。

代码演示:

http://codepen.io/Krystal/pen/XKvoZw

3、插入排序

插入排序是将前面的项看做数组,然后后面的项根据大小插入到对应的位置。比如第二项和第一项对比,他该插到第一项前面还是后面呢?第三项该插到一二项的哪个地方?

这个一般也需要插入n-1次。

JS排序算法

插入排序最好情况下时间复杂度是O(n),其他情况下也都是O(n²)。

代码演示:

http://codepen.io/Krystal/pen/PzrXRJ

4、归并排序

原生js里面的sort方法,在firefox里面是用归并排序实现的,而在chrome里面是用快速排序的变体来实现的。

JS排序算法

归并排序是一种分治的算法,他是将一个大数组分成无数的小数组,如果小数组里面只有一项,那么直接返回,如果大于一项,就继续分,接着小数组合并成一个大数组,合并的时候左右会进行比较大小,然后排序

代码演示:

http://codepen.io/Krystal/pen/jrNPQE

5、快速排序

快速排序也使用了分治的算法,也是把大数组分成小数组.

它会选择一个中间元,创建两个左右指针,然后分别从左右开始出发,如果左指针遇到比中间元大的数,它会停下来,而右边的如果遇到比中间元小的数,它也会停下来,然后两者交换位置。

接着两个指针继续前进,直到左指针超过了右指针,这样左边的数就会小于中间元,右边的数都会大于中间元,接下来分成左右数组,然后再进行上面的操作,直到数组完全排序。

JS排序算法

代码演示:http://codepen.io/Krystal/pen/KgPVvZ