JS前端面试必备——基本排序算法原理与实现方法详解【插入/选择/归并/冒泡/快速排序】
本文实例讲述了JS前端面试必备——基本排序算法原理与实现方法。分享给大家供大家参考，具体如下：
排序算法是面试及笔试中必考点，本文通过动画方式演示，通过实例讲解，最后给出JavaScript版的排序算法
算法描述：
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5
现有一组数组arr=[5,6,3,1,8,7,2,4]
[5]6318724//第一个元素被认为已经被排序 [5,6]318724//6与5比较，放在5的右边 [3，5，6]18724//3与6和5比较，都小，则放入数组头部 [1,3,5,6]8724//1与3,5,6比较，则放入头部 [1,3，5，6，8]724 [1,3，5，6,7，8]24 [1，2,3，5，6,7，8]4 [1，2,3，4，5，6,7，8]
编程思路：双层循环，外循环控制未排序的元素，内循环控制已排序的元素，将未排序元素设为标杆，与已排序的元素进行比较，小于则交换位置，大于则位置不动
functioninsertSort(arr){
vartmp;
for(vari=1;i=0;j--){
if(arr[j-1]>tmp){
arr[j]=arr[j-1];
}else{
arr[j]=tmp;
break;
}
}
}
returnarr
}
时间复杂度O(n^2)
算法描述：直接从待排序数组中选择一个最小（或最大）数字，放入新数组中。
[1]5638724 [1,2]563874 [1,2,3]568724 [1,2,3,4]5687 [1,2,3,4,5]687 [1,2,3,4,5,6]87 [1,2,3,4,5,6,7]8 [1,2,3,4,5,6,7,8]
编程思路：先假设第一个元素为最小的，然后通过循环找出最小元素，然后同第一个元素交换，接着假设第二个元素，重复上述操作即可
functionselectSort(array){
varlength=array.length,
i,
j,
minIndex,
minValue,
temp;
for(i=0;i
时间复杂度O(n^2)
归并排序
算法描述：
1.把n个记录看成n个长度为l的有序子表
2.进行两两归并使记录关键字有序，得到n/2个长度为2的有序子表
3.重复第2步直到所有记录归并成一个长度为n的有序表为止。
56318724
[5,6][3,1][8,7][2,4]
[5,6][1,3][7,8][2,4]
[5,6,1,3][7,8,2,4]
[1,3,5,6][2,4,7,8]
[1,2,3,4,5,6,7,8]
编程思路：将数组一直等分，然后合并
functionmerge(left,right){
vartmp=[];
while(left.length&&right.length){
if(left[0]
时间复杂度O(nlogn)
快速排序
算法描述：
- 在数据集之中，选择一个元素作为”基准”（pivot）。
- 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区(partition)操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
- 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
56318724
pivot
|
56319724
|
storeIndex
56319724//将5同6比较，大于则不更换
|
storeIndex
36519724//将5同3比较，小于则更换
|
storeIndex
36159724//将5同1比较，小于则不更换
|
storeIndex
...
36149725//将5同4比较，小于则更换
|
storeIndex
36145729//将标准元素放到正确位置
|
storeIndexpivot
上述讲解了分区的过程，然后就是对每个子区进行同样做法
functionquickSort(arr){
if(arr.length<=1)returnarr;
varpartitionIndex=Math.floor(arr.length/2);
vartmp=arr[partitionIndex];
varleft=[];
varright=[];
for(vari=0;i
上述版本会造成堆栈溢出，所以建议使用下面版本
原地分区版：主要区别在于先进行分区处理，将数组分为左小右大
functionquickSort(arr){
functionswap(arr,right,left){
vartmp=arr[right];
arr[right]=arr[left];
arr[left]=tmp;
}
functionpartition(arr,left,right){//分区操作，
varpivotValue=arr[right]//最右面设为标准
varstoreIndex=left;
for(vari=left;iright)return;
varstoreIndex=partition(arr,left,right);
sort(arr,left,storeIndex-1);
sort(arr,storeIndex+1,right);
}
sort(arr,0,arr.length-1);
returnarr;
}
时间复杂度O(nlogn)
冒泡排序
算法描述：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。5.
56318724
[56]318724//比较5和6
5[63]18724
53[61]8724
531[68]724
5316[87]24
53167[82]4
531672[84]
53167248//这样最后一个元素已经在正确位置，所以下一次开始时候就不需要再比较最后一个
编程思路：外循环控制需要比较的元素，比如第一次排序后，最后一个元素就不需要比较了，内循环则负责两两元素比较，将元素放到正确位置上
functionbubbleSort(arr){
varlen=arr.length;
for(vari=len-1;i>0;i--){
for(varj=0;jarr[j+1]){
vartmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp
}
}
}
returnarr;
}
时间复杂度O(n^2)
感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。
PS：这里再为大家推荐一款关于排序的演示工具供大家参考：
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。