前端排序算法总结

前言

排序算法可能是你学编程第一个学习的算法,还记得冒泡吗?

当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较你和一个连快排都不会写的人的时候,会优先选择你的。那么,前端需要会排序吗?答案是毋庸置疑的,必须会。现在的前端对计算机基础要求越来越高了,如果连排序这些算法都不会,那么发展前景就有限了。本篇将会总结一下,在前端的一些排序算法。


正文

Array.sort

相信每个使用js的都用过这个函数,但是,这个函数本身有些优点和缺点。我们可以通过一个例子来看一下它的功能:

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

console.log(arr.sort());   // [ 1, 10, 100, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88 ]

console.log(arr.sort((item1, item2) => item1 - item2)); // [ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]

相信你也已经看出来它在处理上的一些差异了吧。首先,js中的sort会将排序的元素类型转化成字符串进行排序。不过它是一个高阶函数,可以接受一个函数作为参数。而我们可以通过传入内部的函数,来调整数组的升序或者降序。

sort函数的性能:相信对于排序算法性能来说,时间复杂度是至关重要的一个参考因素。那么,sort函数的算法性能如何呢?通过v8引擎的源码可以看出,Array.sort是通过javascript来实现的,而使用的算法是快速排序,但是从源码的角度来看,在实现上明显比我们所使用的快速排序复杂多了,主要是做了性能上的优化。所以,我们可以放心的使用sort()进行排序。


冒泡排序

冒泡排序,它的名字由来于一副图——鱼吐泡泡,泡泡越往上越大。

思路:第一次循环,开始比较当前元素与下一个元素的大小,如果比下一个元素小或者相等,则不需要交换两个元素的值;若比下一个元素大的话,则交换两个元素的值。然后,遍历整个数组,第一次遍历完之后,相同操作遍历第二遍。

图例:

冒泡排序

代码实现:

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);

性能:

时间复杂度:平均时间复杂度是O(n^2)

空间复杂度:由于辅助空间为常数,所以空间复杂度是O(1);

改进:

我们可以对冒泡排序进行改进,使得它的时间复杂度在大多数顺序的情况下,减小到O(n);

1.加一个标志位,如果没有进行交换,将标志位置为false,表示排序完成。

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

function swap(arr, i, j){

 const temp = arr[i];

 arr[i] = arr[j];

 arr[j] = temp;

}

for(let i = 0; i < arr.length - 1; i++){

 let flag = false;

 for(let j = 0; j < arr.length - 1 - i; j++){

   if(arr[j] > arr[j+1]){

     swap(arr, j, j+1);

     flag = true;

   }

 }

 if(!flag){

   break;

 }

}

console.log(arr);  //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]

2.记录最后一次交换的位置, 因为最后一次交换的数,是在这一次排序当中最大的数,之后的数都比它大。在最佳状态时,时间复杂度也会缩小到O(n);

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50 ,112];

function swap(arr, i, j){

 let temp = arr[i];

 arr[i] = arr[j];

 arr[j] = temp

}

function improveBubble(arr, len){

 for(let i = len - 1; i >= 0; i--){

   let pos = 0;

   for(let j = 0; j < i; j++){

     if(arr[j] > arr[j+1]){

       swap(arr, j, j+1);

       pos = j + 1;

     }

   }

   len = pos + 1;

 }

 return arr;

}

console.log(improveBubble(arr, arr.length));  // [ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]


选择排序

选择排序,即每次都选择最小的,然后换位置

思路:

第一遍,从数组中选出最小的,与第一个元素进行交换;第二遍,从第二个元素开始,找出最小的,与第二个元素进行交换;依次循环,完成排序

图例:

选择排序

代码实现:

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 ]

性能:

时间复杂度:平均时间复杂度是O(n^2),这是一个不稳定的算法,因为每次交换之后,它都改变了后续数组的顺序。

空间复杂度:辅助空间是常数,空间复杂度为O(1);


插入排序

插入排序,即将元素插入到已排序好的数组中

图例:

插入排序

代码实现:

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 ]

性能:

时间复杂度:平均算法复杂度为O(n^2)

空间复杂度:辅助空间为常数,空间复杂度是O(1)

我们仨之间

其实,三个算法都是难兄难弟,因为算法的时间复杂度都是在O(n^2)。在最坏情况下,它们都需要对整个数组进行重新调整。只是选择排序比较不稳定。


快速排序

快速排序,从它的名字就应该知道它很快,时间复杂度很低,性能很好。它将排序算法的时间复杂度降低到O(nlogn)

思路:

首先,我们需要找到一个基数,然后将比基数小的值放在基数的左边,将比基数大的值放在基数的右边,之后进行递归那两组已经归类好的数组。

图例:

原图片太大,放一张小图,并且附上原图片地址,有兴趣的可以看一下:

快速排序

代码实现:

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));

性能:

时间复杂度:平均时间复杂度O(nlogn),只有在特殊情况下会是O(n^2),不过这种情况非常少

空间复杂度:辅助空间是logn,所以空间复杂度为O(logn)


归并排序

归并排序,即将数组分成不同部分,然后注意排序之后,进行合并

思路:

首先,将相邻的两个数进行排序,形成n/2对,然后在每两对进行合并,不断重复,直至排序完。

图例:

归并排序

代码实现:

//迭代版本

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));

//递归版

const arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];

function mergeSort(arr, seg = 1){

 const len = arr.length;

 if(seg > len){

   return arr;

 }

 const arrB = [];

 for(var start = 0; start < len; start += 2*seg){

   let low = start, mid = Math.min(start+seg, len), heig = Math.min(start+2*seg, len);

   let start1 = low, 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++]);

   }

 }

 return mergeSort(arrB, seg * 2);

}

console.log(mergeSort(arr));

性能:

时间复杂度:平均时间复杂度是O(nlogn)

空间复杂度:辅助空间为n,空间复杂度为O(n)


基数排序

基数排序,就是将数的每一位进行一次排序,最终返回一个正常顺序的数组。

思路:

首先,比较个位的数字大小,将数组的顺序变成按个位依次递增的,之后再比较十位,再比较百位的,直至最后一位。

图例:

基数排序

代码实现:

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));

性能:

时间复杂度:平均时间复杂度O(k*n),最坏的情况是O(n^2)


总结

我们一共实现了6种排序算法,对于前端开发来说,熟悉前面4种是必须的。特别是快排,基本面试必考题。本篇的内容总结分为六部分:

冒泡排序

选择排序

插入排序

快速排序

归并排序

基数排序

排序算法,是算法的基础部分,需要明白它的原理,总结下来排序可以分为比较排序和统计排序两种方式,本篇前5种均为比较排序,基数排序属于统计排序的一种。希望看完的你,能够去动手敲敲代码,理解一下

引文地址:https://segmentfault.com/a/1190000011294349

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,126评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,254评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,445评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,185评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,178评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,970评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,276评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,927评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,400评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,646评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,213评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2 345

推荐阅读更多精彩内容

  • /* (无序区,有序区)。从无序区通过交换找出最大元素放到有序区前端。 选择排序思路: 1. 比较相邻的元素。如果...
    刘帆_d384阅读 463评论 0 0
  • 排序算法说明 (1)排序的定义:对一序列对象根据某个关键字进行排序; 输入:n个数:a1,a2,a3,…,an 输...
    code武阅读 650评论 0 0
  • 【程序1】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔...
    开心的锣鼓阅读 3,307评论 0 9
  • 参考:十大经典排序算法 0、排序算法说明 0.1排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明...
    谁在烽烟彼岸阅读 1,006评论 0 12
  • 图文/刘懒懒 有人把最好的一面放在朋友圈,吃喝玩乐,真的或装作 活的潇洒。 有人把开心 悲伤 日常 放在里面,然后...
    少女哪吒刘懒懒阅读 487评论 4 6