js数组排序的几种方法

JavaScript08

js数组排序的几种方法,第1张

一、 冒泡排序

平均复杂度：o(n^2)空间复杂度：o(1)稳定性：稳定

步骤： 1、比较相邻的元素。如果第一个比第二个大，就交换他们两个；

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样，最后的元素应该会是最大的数；

3、针对所有的元素重复以上的步骤，除了最后一个；

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

二、选择排序

平均复杂度：o(n^2)空间复杂度：o(1)稳定性：不稳定

步骤： 1、每一次循环，找到最小的那个数，并用变量记住它的索引

2、然后将最小值放在它该在的位置上

3、持续对越来越少的元素重复上面的步骤

三、插入排序

平均复杂度：o(n^2)空间复杂度：o(1)稳定性：稳定

（1）直接插入排序：将第一个数和第二个数排序，然后构成一个有序序列；将第三个数插入进去，构成一个新的有序序列；对第四个数、第五个数......直到最后一个数，重复第二步

（2）二分插入排序：将寻找每个数插入位置的方法改为折半比较即可

四、Shell排序（插入排序的一种，又称为缩小增量排序）

平均复杂度：o(nlogn)空间复杂度：o(1)稳定性：不稳定

步骤：把数组按下标的一定增量分组，然后对每组使用直接插入排序

想学习更多前端开发的知识，就来北京尚学堂！

数组表示有序数据的集合，而对象表示无序数据的集合。如果数据的顺序很重要，就用数组，否则就用对象。

比如有一个数组a=[1,2,3,4]，还有一个对象a={0:1,1:2,2:3,3:4}，然后你运行alert(a[1])，两种情况下的运行结果是相同的！这就是说，数据集合既可以用数组表示，也可以用对象表示，

作为有序的数组, js 提供了很多函数用以高速处理数组这一个特别的 "对象" 如增加 删除 排序 等. 用对象的话就代码复杂得多了.而且效率也低.

所谓二分法查找法，也就是折半查找，它是一种在有序数组查找特定元素的搜索算法。

参考《前端程序员面试秘籍》

思想：从数组中开始查找，如果该元素是要搜索的目标元素，则循环结束，如果不是继续下一步，如果目标元素大于或者小于中间元素，则在数组大于或者小于中间元素的那一半区域进行查找，进而重复上面操作。如果数组是空的，则找不到该目标元素。