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

相关文章

来自专栏PHP实战技术

你应该这个姿势学习PHP(2)

2、is_array(),is_bool,is_int(),is_integer(),is_numeric(),is_string(),is_object(),...

3926
来自专栏编程

Shell 数组

Shell中数据类型不多,比如说字符串,数字类型,数组。数组是其中比较重要的一种,同时Shell中的数组不像JAVA/C,只能是一维数组,没有二维数组;数组元素...

1950
来自专栏python学习指南

python列表

本篇将介绍python中的列表,更多内容请参考:Python学习指南 一、序列 在python中有六种内建的序列:列表、元祖、字符串、Unicode字符串...

2195
来自专栏CSDN技术头条

常见的七种排序算法解析

01 选择排序 实现原理 首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之...

2018
来自专栏GreenLeaves

JavaScript引用类型之Object类型

在JavaScript中大多数的引用类型都是Object的实例,Object类型也是使用最多的类型! 创建Object类型实例的方式有两种,下面分别来分析一下:...

2015
来自专栏kalifaの日々

一个易于理解的C++全排列(permutation)实现

通常我们用这两条语句可以得到一个数组的全排列: sort(nums.begin(),nums.end()); //调用next_permutation求全排列...

2725
来自专栏生信小驿站

python-运算符与表达式

你所编写的大多数语句(逻辑行)都包含了表达式(Expressions)。一个表达式的简单例子便是 2+3。表达式可以拆分成运算符(Operators)与操作数(...

972
来自专栏大前端开发

ES6特性之:解构

解构(destructuring assignment), 也称解构赋值,这种语法可以方便的将数组元素或对象属性赋成新的变量。

582
来自专栏PHP在线

PHP函数

请点击上面蓝色PHP关注 你知道这些简单的函数中的方法吗? count() 函数计算数组中的单元数目或对象中的属性个数。 对于数组,返回其元素的个数,对于其他值...

2795
来自专栏玄魂工作室

输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字

要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和...

1581

扫码关注云+社区