Willdark

每一个不曾起舞的日子,都是对生命的辜负

深入JavaScript数组排序sort方法内部原理

<前言>相信大家对JavaScript里的sort方法并不陌生,都知到它可以用来进行数组排序,但是对于它的内部具体做了哪些操作,可能还会存在一定的疑惑,那就让我们来一起剖析一下它的内部原理

一、sort初体验
1.sort分两种情况,一是直接调用,而是传参调用。
(1)直接调用的情况

var arr = [1,3,10,4,5];
arr.sort();//[1,10,3,4,5]
解析:不写参数的情况是系统默认按照ASCII码进行排序

(2)调用函数预留接口的情况(传一个函数作为参数),需满足以下情况
1)必须写两个形参
2)有返回值
i.当返回值为负数时,那么前面的数放在前面(不交换顺序)
ii.当返回值为正数时,那么后面的数放在前面(交换顺序)
iii.当返回值为0时,不交换顺序

二、渐入佳境
1.先来看一下升序降序的表层写法
var arr = [6,9,4,7,3];

(1)升序(假如a比b小->不用交换位置,否则交换位置))
arr.sort(function(a,b){
if(a<b){ return -1;}//返回负数,不交换位置
else{ return 1;}//返回正数,交换位置
}

(2)降序(假如a比b小->交换位置,否则不交换位置)
arr.sort(function(a,b){
if(a<b){return 1;}//返回正数,交换位置
else{return -1;}//返回负数,不交换位置
});

(3)以上函数也可以简写为
arr.sort(function(a,b){
return a-b;//升序
//return b-a;//降序
});

2.那么,在我们调用函数并且传递一个函数作为参数到sort里面时,到底内部发生了什么?
用升序的例子来演示内部的过程

[6,9,4,7,3]
function(a,b){return a-b}
//第一轮 分别把6,9传进来给a,b进行接收,发现返回值为负数,不交换位置
//第二轮 分别把6,4传过来给a,b进行接收,发现返回值为正数,交换6,4的位置,数组变为
[4,9,6,7,3]
//第三轮 分别把4,7传过来,返回负数,不交换位置
//第四轮 分别把4,3传过来,返回正数,交换位置,数组变为
[3,9,6,7,4]
//第五轮 分别传9,6过来,交换位置,数组变为
[3,6,9,7,4]
//第六轮 分别传6,7 不交换
//第七轮 分别传6,4 交换 数组变为
[3,4,9,7,6]
//第八轮 分别传9,7 交换 数组变为
[3,4,7,9,6]
//第九轮 传7,6 交换 数组变为
[3,4,6,9,7]
//第十轮 传9,7 交换 数组变为
[3,4,6,7,9]

至此,数组排序完成,把排序好的数组进行返回。

以上便是sort函数内部的一个实现原理,相当于每一个大轮次的时候找一个最小的放在最前面,然后在未排序区域再找一个次小的,以此类推。

降序的排序原理就是返回负数的时候就交换位置。内部原理亦然

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注