浅谈 JavaScript array.sort(compare()) 实现原理.

超、凢脫俗 2022-06-07 01:40 225阅读 0赞

JavaScript array.sort(compare()) 的实现原理是什么？

先看下' 2015-ECMAScript-262语言规范 '的解释：The sort is not necessarily stable - 排序是不稳定的. (Ps: 截取的重要部分）.

MDN的基本解释：`sort()` 方法在适当的位置对数组的元素进行排序，并返回数组。 sort 排序不一定是稳定的。默认排序顺序是根据字符串Unicode码点.

基本的就不说了，那怎样才算排序不稳定？ 我们做个小实验：

var exArray = [15,0,-3,5];
    var i=1;
    window.onload = function(){
    	exArray.sort(compare);
    	console.log("最终结果"+exArray);
    }
    function compare(num1,num2){
        console.log("第" + (i++) +"次比较： "+"nowArray:["+ exArray + "].  参数num1: "+num1+"， 参数num2: "+num2);
        var key = (num1 > num2) ? 1:-1;
        console.log(key);
        return key;
    }

在Chorme的结果如下：

![20171004003732064][]

运行结果解释：

\- 第一次比较时数组元素为：15,0，-3,5. compare比较函数的参数为：15,0. 因为返回1，所以0和15互换位置.

\- 第二次比较时数组元素为：0,15，-3,5. compare比较函数的参数为：15，-3. 因为返回1，所以按道理15和-3互换.

\- 第三次比较时发现数组元素为：0，15,15,5. -3被拐跑了？ 这里便体现了"不稳定排序". 15和-3比较后并没有立即互换，首先把15赋给arr\[2\]数组元素，然后把 -3(可能) 存放在某个临时变量中，再与前面的0做比较，当确定-3比0小之后，互换位置，释放临时变量.

\- 第四次比较时数组元素理所当然的变成了-3,0,15,5. 此时compare比较函数的参数为：15,5.

\- 第五次的比较和第三次原理相同.

得到最终的排序数组：-3,0,5,15.

那做完这个小实验可以总结出一些可能**不太严谨的规律**：

**数组sort比较时，从数组内索引值为0和1的参数开始比较（即参数num1和num2），比较结果没有变动的话，继续比较索引值1和2的，如果结果有变化，变换两者的位置（索引值），并判断之前有无其他参数，如果有的话则会对参数num1和num1之前的参数进行比较。如果没有则用参数num2与索引值+1的参数比较。遵循此逻辑重复循环操作，完成排序***.*

这可能大概就是array.sort(compare())的原理吧。

然后至于是不是冒泡排序，我们先用 "C语言" 来做个小实验：

#include "stdio.h"  
    
    int main()  
    {   
          int a[4];   
          int i, j, temp,count=0;   
    	   
          printf("Please input four numbers: \n");   
          for (i = 0; i < 4; i++)   
                scanf("%d", &a[i]);   
          printf("The array change procedure:\n");      
          for (i = 0; i < 3; i++)
          {   
                for (j = 0; j < 3 - i; j++)
                {
                	if (a[j] > a[j+1])   
    	            {   
    	                  temp = a[j];   
    	                  a[j] = a[j+1];   
    	                  a[j+1] = temp;   
    	            }   
                	count=count+1;
                	printf("\n%d %d %d %d \n",a[0],a[1],a[2],a[3]);
                }
          }
          
          printf("\nThe finally result: "); 
          for (i = 0; i < 4; i++)   printf("%d ", a[i]); 
    	  printf("\n\ncount = %d\n",count);  
          
          return 0;   
    }

在C-Free环境下的运行结果为：

![20171004013703636][]

I : 从运行过程来看，与Js的sort内部排序逻辑不一致； II：从排序的次数来看，有点不一致，可能是因为这个值和Js的5有点偶然吧. 所以Js的array.sort(compare())的内部排序的实现应该不是冒泡。

大概就说这么多吧，可能好多地方不足，前端小白，努力加油中.

参考1：http://blog.csdn.net/u013680938/article/details/51487112 - CSDN的[箫沐予][Link 1].

参考2：https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global\_Objects/Array/sort.

参考3：ECMAScript® 2015 Language Specification.

[20171004003732064]: /images/20220607/8e64fba039a542e19d8386f2ddbb612e.png
[20171004013703636]: /images/20220607/d3a72f8216d045ee8ed54898f69cd0e3.png
[Link 1]: http://blog.csdn.net/u013680938