我们在面试中经常会遇到排序算法题。我整理了冒泡排序、选择排序、插入插入等常见的简单排序方法。希望本文对懂排序的前端同学有所帮助。封装排序数组为了简单高效的演示算法的实现，我先封装一个构造函数。下面的排序默认是从小到大排序的，因为无论是从大到小还是从小到大，思路都是一样的。functionArrayList(){//创建一个排序数组this.list=[6,3,8,5,4,1,9,7];//排序后的结果显示在-divisionthis.toString=function(){returnthis.list.join('-')}//交换数组m和n的位置this.swap=function(m,n){vartemp=this.list[n];this.list[n]=this.list[m];this.list[m]=temp;}}冒泡排序冒泡排序就是依次比较相邻的两个数，小的放在前面，大的放在后面。ArrayList.prototype.bubblesort=function(){//第一个元素和第二个元素交换，较大的放在后面，9放在最后[6,3,8,5,4,1,9,7]=>[3,6,5,4,1,8,7,9]//除了最后一个元素9，然后比较大小，交换位置[3,6,5,4,1,8,7,9]=>[3,5,4,1,6,7,8,9]//除了最后一个元素9和最后两个元素8，然后比较大小，交换位置[3,5,4,1,6,7,8,9]=>[3,4,1,5,6,7,8,9]//依此类推...[3,4,1,5,6,7,8,9]=>[3,1,4,5,6,7,8,9]varlen=this.list.length;for(varj=len-1;j>=0;j--){for(vari=0;ithis.list[i+1]）{这。交换（我，我+1）；}}}返回这个。toString();//1-3-4-5-6-7-8-9}冒泡排序的比较次数为1+2+3+...+N-1=N(N-1)/2,BigO表示法是O(N^2)。如果每两次比较交换一次，那么冒泡排序的交换次数就是N(N-1)/4次。选择排序首先在未排序的序列中找到最小的元素，将其存放在已排序序列的开头，然后继续从剩余未排序的元素中查找最小的元素，然后将其放在已排序序列的末尾。ArrayList.prototype.selectsort=function(){//遍历一轮寻找最小元素1，其下标为5，下标0和下标5交换位置[6,3,8,5,4,1,9,7]=>[1,3,8,5,4,6,9,7]//从第二个元素开始遍历，找到最小值，交换位置[1,3,8,5,4,6,9,7]=>[1,3,8,5,4,6,9,7]//依此类推...[1,3,8,5,4,6,9,7]=>[1,3,4,5,8,6,9,7]varlen=this.list.length;for(varj=0;jthis.list[i+1]){min=i+1;}}this.swap(min,j);}返回this.toString();//1-3-4-5-6-7-8-9}选择排序的比较次数为N-1+N-2+N-3+...+1=N*(N-1)/2，大O表示法是O(N^2)。但是交换次数是N-1次，比冒泡排序要少很多。插入排序插入排序将第一个待排序序列的第一个元素视为有序序列，将第二个元素至最后一个元素视为未排序序列。从头到尾按顺序扫描未排序的序列，并将每个扫描到的元素插入到已排序序列中的适当位置。ArrayList.prototype.insertsort=function(){//获取第二个元素3，与第一个元素6比较，3小于6，交换位置[6,3,8,5,4,1,9,7]=>[3,6,8,5,4,1,9,7]//获取第三个元素8，8大于前两个元素6和3，所有位置不变[3,6,8,5,4,1,9,7]=>[3,6,8,5,4,1,9,7]//依此类推...[3,6,8,5,4,1,9,7]=>[3,5,6,8,4,1,9,7]varlen=this.list.length;for(vari=1;itemp&&j>0){this.list[j]=this.list[j-1];j--;}this.list[j]=temp;}返回this.toString();}varlist=newArrayList();//1-3-4-5-6-7-8-9插入排序的比较次数是(1+2+3+...+N-1)/2=N*(N-1)/4.与冒泡排序和选择排序相比，它的比较次数最少。但是，它也是大O表示法中的O(N^2)。以上三种只是简单的排序，插入排序的思想是实现高级排序的基础。后期更新会引入希尔排序、快速排序等高级排序内容。
