javascript Array.prototype.sort 排序浅谈

每个 Array 的实例都自带sort 函数,本文对sort函数的用法做一些探讨。

基本用法

1.数组元素为字符串的排序:

var fruit = ['cherries', 'apples', 'bananas'];
fruit.sort();
// => ['apples', 'bananas', 'cherries']

无参数调用 sort 函数,默认是升序排列的,字母 a b c ,排序结果正确.

2.数组元素为数字的排序:

var array = [3,7,2,8,2,782,7,29,1,3,0,34];
array.sort();
// => [0, 1, 2, 2, 29, 3, 3, 34, 7, 7, 782, 8]

咦,怎么顺序好像不对?数字应该按从小到大升序排列的啊。什么原因呢?通过查询 MDN 文档[^3],文档里是怎么说的呢?

The default sort order is according to string Unicode code points.

默认排序规则是数组元素 字符 的 Unicode 编码排序的,也就是说数组元素会被当做字符串,然后按照字符串的 Unicode 编码进行升序排列。

3.带参数的sort调用

那么如何实现元素为数字的数组按照数值升序排列呢? 通过传入自定义的函数进行相邻元素的比较。

在探讨排序自定义函数之前,我们回到之前不带参数的排序,在排序时进行的是字符编码大小的比较,我们自己写一个函数将字符转为 unicode

为后面观察方便起见,转换字符串后返回的unicode编码用一个数组表示,如下:

function array2unicode(arr){
  return arr.map(function(s){
           // 先转为字符串
           s = String(s);
           // 字符串拆分字符
           var chars = s.split('');
           // 将每个字符转为 unicode 编码
           return chars.map(function(c){
                    return c.charCodeAt(0);
                  });
         });
}
// 举例
var array = [12,2,13];
array2unicode(array);
// => [ [ 49, 50 ], [ 50 ], [ 49, 51 ] ]
//    [     12        2         13     ]

4.sort排序过程模拟

那么下面来模拟内部的排序过程

var array;
array = [12,2,13];
// 将 array 的元素转为 unicode 编码
array2unicode(array);
// 对应关系如下:
//    [     12        2         13     ]
// => [ [ 49, 50 ], [ 50 ], [ 49, 51 ] ]
// 容易得出升序的排列结果为
//    [     12          13        2    ]
// => [ [ 49, 50 ], [ 49, 51 ], [ 50 ] ]

// 验证一下
[12,2,13].sort();
// => [12, 13, 2]

如果传入一个比较函数作为参数,如何实现默认的字符串排序效果呢?

[12,2,13].sort(function(a,b){
  a = String(a);
  b = String(b);
  if (a < b){
    return -1;
  }else if(a > b){
    return 1;
  }else{
    return 0;
  }
});
// => [12, 13, 2]

上面是 sort 函数内部按照字符unicode编码排序,关键的关键在于返回 -1 0 1,那么对于数字数组而言,我们更希望是按照数值进行排序 ,我们看到很多 js 代码中对数字进行排序的自定义函数如下:

[12,2,13].sort(function(a,b){
  return a - b;
});
// => [2, 12, 13]

5.带函数参数的sort排序规则的总结

sort 函数参数有两个,a、b,表示相邻的两个数组元素:

[12,2,13].sort(function(a,b){
  return a - b;
});

a - b 的值有三种情况

  • 小余 0 时,a 排在 b 前面
  • 大余 0 时,a 排在 b 后面
  • 等余 0 时,a b 的相对位置保持不变

6.注意项

上面说到,sort 函数参数返回值可能有 3 个,那么下面的写法是错误的:

arr.sort(function(a,b){
  return a<b;
});
// 可能的结果 => [21, 0, 3, 11, 4, 5, 6, 7, 8, 9, 10, 1, 2, 12, 
//               13, 14, 15, 16, 17, 18, 19, 20, 22]
// 不是正确的结果,因为
// return a<b;
// 只返回了两种值 true false 相当于 1 0 ,而没有 -1

Array.prototype.sort 的内部实现 [^1]

Quicksort is generally considered to be efficient and fast and so is used by V8 as the implementation for Array.prototype.sort() on arrays with more than 23 items. For less than 23 items, V8 uses insertion sort[2]. Merge sort is a competitor of quicksort as it is also efficient and fast but has the added benefit of being stable. This is why Mozilla and Safari use it for their implementation of Array.prototype.sort().

chrome 对 sort 做了特殊处理,对于长度小余 23 的数组使用的是 insert sort ,大于 23 使用的是 quicksort. quicksort 是不稳定的排序算法 , 因此 Mozilla 和 Safari 采 用了 merge sort 来实现. 由于所学有限,就不展开了。

关于什么是稳定排序(Stable),wiki 上有张示意图很明白 [^2]:

参考

[1] https://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/

[2] https://en.wikipedia.org/wiki/Sorting_algorithm

[3] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏221-B

python正则表达式的部分特殊符号

\w - 匹配字母或数字或下划线或汉字(3.x版本可以匹配汉字,但2.x版本不可以) \s - 匹配任意的空白符 \b - 在正则表达式中表示单词的开头或结尾,...

741
来自专栏Golang语言社区

Go语言基本语法

前面已经看到了Go程序的基本结构,所以这将是很容易理解Go编程语言等基本构建块。 Go令牌 Go程序包括各种令牌和令牌可以是一个关键字,一个标识符,常量,字符串...

2586
来自专栏MasiMaro 的技术博文

IF和SWITCH的原理

在C语言中,if和switch是条件分支的重要组成部分。if的功能是计算判断条件的值,根据返回的值的不同来决定跳转到哪个部分。值为真则跳转到if语句块中,否则跳...

924
来自专栏java思维导图

正则表达式思维导图,不再难懂

01 一张思维导图 ? 02 导图内容解析 工具 RegexBuddy 语法结构 字符 [ab5@] 匹配"a"或"b"或"5"或"@" [^abc] 匹配a、...

34911
来自专栏前端儿

JS 数组去重(数组元素是对象的情况)

但当数组元素是对象时,就不能简单地比较了,需要以某种方式遍历各值再判断是否已出现。

510
来自专栏菩提树下的杨过

ruby学习笔记(6)-Array的使用

ruby的数组基本使用,跟c#中的数组比起来,最不习惯的区别在于允许负索引(跟javascript到有几分相似) arr=[3,4,5,6,7,8,9] pu...

1775
来自专栏云霄雨霁

查找----基于有序数组

1330
来自专栏java一日一条

自己动手实现一个 Java Class 解析器

最近在写一个私人项目,名字叫做ClassAnalyzer,ClassAnalyzer的目的是能让我们对Java Class文件的设计与结构能够有一个深入的理解。...

754
来自专栏互联网杂技

JS编程小常识很有用

2.JS中的真真假假 空,null,undefined,false,0,””,'',NaN都为假,其他都为真 3.函数,类,对象,构造器有什么区别? 答:...

3196
来自专栏转载gongluck的CSDN博客

python笔记:#008#变量的命名

变量的命名 目标 标识符和关键字 变量的命名规则 0.1 标识符和关键字 1.1 标识符 标示符就是程序员定义的 变量名、函数名 名字 需要有 见名知义 的...

3384

扫码关注云+社区