详细的 JavaScript 数组比较函数 比较函数

背景

很多朋友在学习JavaScript的时候会碰到Array数组(对象)的一个方法——.sort()的排序问题，.sort()方法用于对数组中的元素进行排序。当我们数组中的元素都为字符串时，一般不会有问题，但当我们数组中的元素为数据时问题就来了，例如：20与100这两个元素来排序的话谁更大呢？用sort排序时会因为2比1先，从而得出20大于100这样的排列结果。因此，对于数组中的数字元素的排序我们一般会引入比较函数。也就是本文所讨论的"compare function"(也可称之为sortFunction)，对于此函数与数据的sort()方法结合起来使用的工作机制，很让人迷惑，貌似w3schools上也没讲透彻，下面我们一起来探究下。

关于数组的sort()方法

myArray.sort()方法用于将当前数组对象的元素按指定顺序进行排序，并返回排序后的数组，该方法对原数组对象进行重排，并不会在内存中创建新的数组。

该方法属于Array对象，所有主流浏览器均支持该方法。

语法
array.sort( sortFunction )

关于sort方法的参数
sort方法的参数必须是一个用于比较排序的函数，这里称之为比较函数，英文里常称之为'sortFunction'，为可选。
如果省略sortFunction参数，元素将按ASCII字符顺序的升序进行排列。
例：

//定义一个数组myArray
var myArray = []
myArray[0] = "10"
myArray[1] = "5"
myArray[2] = "40"
myArray[3] = "25"
myArray[4] = "1000"
myArray[5] = "1"
//定义一个比较函数sortFunction
function sortNumber(a,b)
{
return a - b //这里返回a减b的值，供后续的sort方法使用
}
console.log(myArray.sort())  //这里为省略sort方法参数的用法
//sort方法依据上面自定义的比较函数所返回的值的正、负、零来决定如何对当前两个数值进行排序
console.log(myArray.sort(sortNumber)) //1,5,10,25,40,1000

关于数组对象的sort方法的返回值
sort()方法的返回值为Array类型，返回排序后的数组对象。
在排序过程中，并不会创建新的数组对象，返回的数组对象就是经过排序后的当前数组本身。

如果在使用sort方法时，提供了sort方法的参数——“比较函数”（sortFunction），一般来说“比较函数”（sortfunction）必须携带两个参数（经常被命名为a和b），那么该函数会返回下列值之一：

• 当a小于b的时候，则返回负值。
• 当a等于b的时候，则返回零。
• 当a大于b的时候，则返回正值。

数组的sort方法在两两比较数组中的元素值时，如果有指定“比较函数”，那么其则会依据“比较函数”中返回值的正、负、零，来决定当前两个数组元素的排序。

下面是比较函数的另一种写法：

//compare()函数是升序的一种写法：
function compare(value1,value2){
    if(value1<value2){
        return -1;
    }else if(value1==value2){
        return 0;
    }else{
        return 1;
    }
}

那么我们主要的困惑来了，数组的sort方法内部到底是如何运作的呢？

数组的sort()方法的内部排序机制——冒泡算法

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地两两比较要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

冒泡排序算法的运作原理如下：（从后往前）

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
  冒泡算法的原理如下动画演示，了解期机制才能真正理解在这过种中sort方法与比较函数compare function到底一起协同作了什么：

现在流行去Flash化，没法子上传了，只能放附件中，大家自己下载吧。
<a href="http://pan.baidu.com/s/1miSA8ZY">BubbleSort原理解析动画下载</a>

冒泡排序细节

交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。

具体排序方法

将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

（1）初始
　 R[1..n]为无序区。

（2）第一趟扫描
　 从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]的内容。
　第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。

（3）第二趟扫描
　 扫描R[2..n]。扫描完毕时，"次轻"的气泡飘浮到R[2]的位置上……
　最后，经过n-1 趟扫描可得到有序区R[1..n]

注意：

第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R[i]上，结果是R[1..i]变为新的有序区。

因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于有序区中气泡的重量，所以整个冒泡排序过程至多需要进行n-1趟排序。

若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。为此，在下面给出的算法中，引入一个布尔量exchange，在每趟排序开始前，先将其置为FALSE。若排序过程中发生了交换，则将其置为TRUE。各趟排序结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一趟排序。

附：
算法介绍 http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.1.1.htm

Tag：JavaScript
发布时间：2015-06-17
修订时间：2017-05-22