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 条评论
登录 后参与评论

相关文章

来自专栏架构说

指针和引用的区别

先看代码输出是什么? ? 最后输出是: 1234567890 hello 指针和引用主要区别 1 在C++中,指针和引用经常用于函数的参数...

2707
来自专栏C#

解析C#类中的构造函数

《解析C#类中的构造函数》 一.  C#中的构造函数概述: C#中类包含数据成员和函数成员。函数成员提供了操作类中数据的某些功能,包括方法、属性、构造器和终结器...

1765
来自专栏WindCoder

Java代码块执行顺序初探

Java继承中对构造函数是不继承的,只是显式或者隐式调用,并且必须是在构造函数第一行。这里是隐式调用了super()。

921
来自专栏学海无涯

8.数组

502
来自专栏技术博客

C#简单的面试题目(一)

1.简述private、protected、public、internal修饰符的访问权限。

923
来自专栏desperate633

Java Iterable 与 Iterator

但实际中,我们不需要这么麻烦,因为所有collection都有一个iterator()方法,在JDK1.4之前这个方法定义在collection接口中的,因此所...

684
来自专栏Jack的Android之旅

疯狂Java笔记之面向对象的陷阱

instanceof是一个非常简单的运算符。instanceof运算符的前一个操作数通常是一个引用类型的变量,后一个操作数通常是一个类(也可以是接口,可以把接口...

672
来自专栏Vamei实验室

Python基础07 函数

函数最重要的目的是方便我们重复使用相同的一段程序。 将一些操作隶属于一个函数,以后你想实现相同的操作的时候,只用调用函数名就可以,而不需要重复敲所有的语句。 函...

1839
来自专栏游戏杂谈

C++学习笔记 -- 函数指针与指针函数

函数指针:指向函数的指针,首先它是指针变量(同指向一个整形变量、字符、数组一样),其次它指向一个函数(地址)。

592
来自专栏java一日一条

Java中创建对象的5种方式

作为Java开发者,我们每天创建很多对象,但我们通常使用依赖管理系统,比如Spring去创建对象。然而这里有很多创建对象的方法,我们会在这篇文章中学到。

513

扫码关注云+社区