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

相关文章

来自专栏CSDN技术头条

常见的七种排序算法解析

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

2078
来自专栏kalifaの日々

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

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

3315
来自专栏python学习指南

python列表

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

3495
来自专栏生信小驿站

python-运算符与表达式

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

1802
来自专栏ml

nyoj-----前缀式计算

前缀式计算 时间限制:1000 ms  |           内存限制:65535 KB 难度:3 描述 先说明一下什么是中缀式: 如2+(3+4)*5这种我...

3446
来自专栏desperate633

LintCode 编辑距离题目分析代码

给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。

792
来自专栏Python小屋

Python内置函数sorted()和列表方法sort()排序规则不得不说的事

Python内置函数sorted()和列表方法sort()可以使用key参数指定排序规则,并且都是稳定排序,也就是说,对于指定规则不能涵盖的元素,本来谁在前面,...

2713
来自专栏天天

数据类型的转换

1183
来自专栏PHP实战技术

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

1、循环数组有哪几种方式 1)foreach(能够循环关联和索引数组以及对象) 2)for(只能循环索引数组) 3)list和each配合使用循环数组 $arr...

27810
来自专栏PHP在线

PHP函数

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

2955

扫码关注云+社区

领取腾讯云代金券