在线客服
扫描二维码
下载博学谷APP扫描二维码
关注博学谷微信公众号
排序算法是前端算法中一个十分经典的算法,因此它也是前端面试中常见的考察重点。如今前端行业火爆,就业市场对前端人才的要求也越来越高,排序算法是每个前端从业者都必须掌握的基础知识。众所周知,排序算法有六种,分别是冒泡排序、选择排序、快速排序、归并排序、基数排序。下面我为大家逐一用代码演示这六大排序算法,感兴趣的朋友一起来看看吧!
1、冒泡排序
(1)概念
冒泡排序,顾名思义,就像鱼吐泡泡,泡泡越往上越大。第一次循环,开始比较当前元素与下一个元素的大小,如果比下一个元素小或者相等,则不需要交换两个元素的值;若比下一个元素大的话,则交换两个元素的值。然后,遍历整个数组,第一次遍历完之后,相同操作遍历第二遍。
(2)性能
时间复杂度:平均时间复杂度是O(n^2);空间复杂度:由于辅助空间为常数,所以空间复杂度是O(1)。
(3)代码演示
const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];
function bubbleSort(arr){
for(let i = 0; i < arr.length - 1; i++){
for(let j = 0; j < arr.length - i - 1; j++){
if(arr[j] > arr[j + 1]){
swap(arr, j, j+1);
}
}
}
return arr;
}
function swap(arr, i, j){
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
console.log(arr);
2、选择排序
(1)概念
选择排序,即每次都选择最小的,然后换位置。第一遍,从数组中选出最小的,与第一个元素进行交换;第二遍,从第二个元素开始,找出最小的,与第二个元素进行交换;依次循环,完成排序。
(2)性能
时间复杂度:平均时间复杂度是O(n^2),这是一个不稳定的算法,因为每次交换之后,它都改变了后续数组的顺序。空间复杂度:辅助空间是常数,空间复杂度为O(1)。
(3)代码演示
const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];
function swap(arr, i, j){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function selectionSort(arr){
for(let i = 0; i < arr.length - 1; i++){
let index = i;
for(let j = i+1; j < arr.length; j++){
if(arr[index] > arr[j]){
index = j;
}
}
swap(arr, i, index);
}
return arr;
}
console.log(selectionSort(arr)); //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]
3、插入排序
(1)概念
插入排序就是将元素插入到已排序好的数组中。首先,循环原数组,然后,将当前位置的元素,插入到之前已排序好的数组中,依次操作。
(2)性能
时间复杂度:平均算法复杂度为O(n^2);空间复杂度:辅助空间为常数,空间复杂度是O(1)。
(3)代码演示
const arr = [1, 20, 10, 30, 22, 11, 55, 24, 0, 31, 88, 12, 100, 50 ,112];
function insertSort(arr){
for(let i = 0; i < arr.length; i++){
let temp = arr[i];
for(let j = 0; j < i; j++){
if(temp < arr[j] && j === 0){
arr.splice(i, 1);
arr.unshift(temp);
break;
}else if(temp > arr[j] && temp < arr[j+1] && j < i - 1){
arr.splice(i, 1);
arr.splice(j+1, 0, temp);
break;
}
}
}
return arr;
}
console.log(insertSort(arr)); //[ 0, 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]
4、快速排序
(1)概念
快速排序,从它的名字就应该知道它很快,时间复杂度很低,性能很好。它将排序算法的时间复杂度降低到O。
(2)性能
时间复杂度:平均时间复杂度O(nlogn),只有在特殊情况下会是O(n^2),不过这种情况非常少;空间复杂度:辅助空间是logn,所以空间复杂度为O。
(3)代码演示
const arr = [30, 32, 6, 24, 37, 32, 45, 21, 38, 23, 47];
function quickSort(arr){
if(arr.length <= 1){
return arr;
}
let temp = arr[0];
const left = [];
const right = [];
for(var i = 1; i < arr.length; i++){
if(arr[i] > temp){
right.push(arr[i]);
}else{
left.push(arr[i]);
}
}
return quickSort(left).concat([temp], quickSort(right));
}
console.log(quickSort(arr));
5、归并排序
(1)概念
归并排序,即将数组分成不同部分,然后注意排序之后,进行合并。首先,将相邻的两个数进行排序,形成n/2对,然后在每两对进行合并,不断重复,直至排序完。
(2)性能
时间复杂度:平均时间复杂度是O;空间复杂度:辅助空间为n,空间复杂度为O(n)。
(3)代码演示
//迭代版本
const arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
function mergeSort(arr){
const len = arr.length;
for(let seg = 1; seg < len; seg += seg){
let arrB = [];
for(let start = 0; start < len; start += 2*seg){
let row = start, mid = Math.min(start+seg, len), heig = Math.min(start + 2*seg, len);
let start1 = start, end1 = mid;
let start2 = mid, end2 = heig;
while(start1 < end1 && start2 < end2){
arr[start1] < arr[start2] ? arrB.push(arr[start1++]) : arrB.push(arr[start2++]);
}
while(start1 < end1){
arrB.push(arr[start1++]);
}
while(start2 < end2){
arrB.push(arr[start2++]);
}
}
arr = arrB;
}
return arr;
}
console.log(mergeSort(arr));
6、基数排序
(1)概念
基数排序,就是将数的每一位进行一次排序,最终返回一个正常顺序的数组。首先,比较个位的数字大小,将数组的顺序变成按个位依次递增的,之后再比较十位,再比较百位的,直至最后一位。
(2)性能
时间复杂度:平均时间复杂度O(k*n),最坏的情况是O(n^2)。
(3)代码演示
const arr = [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127, 10000];
function radixSort(arr){
let maxNum = Math.max(...arr);
let dis = 0;
const len = arr.length;
const count = new Array(10);
const tmp = new Array(len);
while(maxNum >=1){
maxNum /= 10;
dis++;
}
for(let i = 1, radix = 1; i <= dis; i++){
for(let j = 0; j < 10; j++){
count[j] = 0;
}
for(let j = 0; j < len; j++){
let k = parseInt(arr[j] / radix) % 10;
count[k]++;
}
for(let j = 1; j < 10; j++){
count[j] += count[j - 1];
}
for(let j = len - 1; j >= 0 ; j--){
let k = parseInt(arr[j] / radix) % 10;
tmp[count[k] - 1] = arr[j];
count[k]--;
}
for(let j = 0; j < len; j++){
arr[j] = tmp[j];
}
radix *= 10;
}
return arr;
}
console.log(radixSort(arr));
以上就是六种前端排序算法的代码演示,大家都看明白了吗?排序算法是前端学习中的基础部分,只要大家明白它的原理,再多动手敲敲代码,相信掌握前端排序算法并不困难。如果大家喜欢本篇文章,欢迎关注博学谷资讯栏目,本栏目将每天为大家更新更多的前端资讯。
— 申请免费试学名额 —
在职想转行提升,担心学不会?根据个人情况规划学习路线,闯关式自适应学习模式保证学习效果
讲师一对一辅导,在线答疑解惑,指导就业!
相关推荐 更多
Web前端知识点之HTML规范
本文就标签规则,标签语义化,属性规则,属性顺序和布尔属性五个方面,带大家梳理一下Web前端知识点之HTML规范。
6564
2019-07-29 14:16:46
HTML5开发工具哪个好?前端必备工具推荐
HTML5作为前端开发中十分重要的部分,深受前端工程师的喜爱和欢迎。都说工欲善其事必先利其器。想要更好的完成在HTML5开发,好用的工具少不了。下面给大家推荐10款前端必备的HTML5开发工具,它们分别是Lungo、Animatron、DCloudHBuilder、mobl、Initializr、WebStorm、Notepad++、Dreamweaver、Eclipse和DevExtreme。
6077
2019-10-09 19:10:15
React项目开发教程推荐
React作为当下最流行的框架之一,拥有简单的代码逻辑和较高的性能,因此它可以很好地解决前端视图中所遇到的问题。本文将为大家推荐React项目开发教程,希望大家可以通过这个实战项目的课程,系统学习React新特性及其生态圈相关知识,并掌握实战开发的相关经验,下面我们一起来看看教程简介吧~
5042
2020-05-04 15:49:24
学习前端的机构哪家比较好?
先给大家讲几个前端培训机构的判断标准,行业的口碑、授课讲师的资质、课程内容的质量以及还有班级的学习氛围。可能有人要说了,我不知道怎么了解这些判断标准,不能直接推荐一个靠谱的培训机构吗?当然可以,但是直接推荐还是过于主观,不一定适合所有人。因此,最好的办法就是大家多试听几家培训机构的课程,货比三家,依照以上的几个判断标准,就一定能选出最适合你的前端培训机构。
5857
2020-08-05 17:00:22
Web前端都需要学什么?从哪入门?
基础阶段学习HTML常用标签与表单控件、CSS基本样式及显示模式、选择器、标签显示模式、CSS复合选择器、CSS背景应用、CSS三大特性、CSS盒子模型、浮动、定位、JavaScript基础语法、DOM操作,事件处理、DOM应用等基础阶段核心知识点;以问题为导向的项目实战开发阶段,初学者加深对前端基础知识理解的同时,获取Web项目开发的技巧与思路,锻炼Web网站开发的能力。
4242
2021-04-28 10:39:15