Array.prototype.sort()方法到底是如何排序的？

  本文除了会带大家了解一些Array.prototypr.sort()方法(后面简写为sort()方法)的基本定义和用法之外&＃xff0c;还会探讨一下sort()方法到底是使用的什么排序算法。简单度娘了一下&＃xff0c;网上的那些sort()方法详解文章&＃xff0c;大多只说了sort()方法的用法。还有说sort()方法是使用冒泡法做的排序&＃xff0c;这是错误的。下面&＃xff0c;我们发车&＃xff01;

sort()方法

  先来看看sort()方法的一些基础知识。已经了解sort()方法的童鞋可以直接跳过这部分。

定义

sort() 方法在适当的位置对数组的元素进行排序&＃xff0c;并返回数组。 sort 排序不一定是稳定的。

语法

arr.sort()

arr.sort(compareFunction)

说明

1.如果没有指明 compareFunction &＃xff0c;那么元素会按照转换为的字符串的诸个字符的Unicode位点进行排序。

2.如果指明了 compareFunction &＃xff0c;那么数组会按照调用该函数的返回值排序。即 a 和 b 是两个将要被比较的元素&＃xff1a;

   a.如果 compareFunction(a, b) 小于 0 &＃xff0c;那么 a 会被排列到 b 之前&＃xff1b;
   b.如果 compareFunction(a, b) 等于 0 &＃xff0c; a 和 b 的相对位置不变。(ECMAScript 标准并不保证这一行为&＃xff0c;而且也不是所有浏览器都会遵守,例如 Mozilla 在 2003 年之前的版本&＃xff09;&＃xff1b;
   c.如果 compareFunction(a, b) 大于 0 &＃xff0c; b 会被排列到 a 之前。
  d. compareFunction(a, b)必须总是对相同的输入返回相同的比较结果&＃xff0c;否则排序的结果将是不确定的。(利用这一特性&＃xff0c;可实现随机排序)

3.如果数组包含undefined元素&＃xff08;元素值为undefined或元素末定义&＃xff09;

以上90%引用自MDN

实例

//例1.字母排序
var a &＃61; new Array("banna","watermelon","orange","apple");
s.sort();
console.log(a) //输出 ["apple", "banna", "orange", "watermelon"]
//没什么好说的&＃xff0c;比较函数缺省&＃xff0c;按照字母顺序升序排序 avar a&＃61;[11,2,44,3,5,6];
a.sort();
console.log(a) // [11, 2, 3, 44, 5, 6]
//说明第一条&＃xff0c;数字转为字符串&＃xff0c;"11"<"2"<"3"<"44"<"5"<"6"//例3.数字排序
var a&＃61;[11,2,44,3,5,6];
a.sort(function(a,b){return a-b; //升序——当a});
console.log(a) //输出 [2, 3, 5, 6, 11, 44]//例3.随机排序
var a&＃61;[11,2,44,3,5,6];
a.sort(function(a,b){return Math.random()>.5?-1:1; //根据说明2-c特性&＃xff0c;实现随机排序
});
console.log(a) //每次运行的输出都不同

  以上是sort()方法的一些基本用法,MDN里还有更多的用法。下面我们来看看sort()方法到底是如何排序的。

sort()方法如何实现排序

  怎么查看sort()方法是如果实现排序的呢&＃xff1f;我们可以在比较函数里把a,b及数组输出一下&＃xff0c;看看是否能够看出使用的排序算法。

var arr&＃61;[1, 8, 3, 5, -1];
function compare(a,b){console.log(a,b,arr);return a-b;
}
arr.sort(compare);
/**
控制台输出
1 8 [1, 8, 3, 5, -1]
8 3 [1, 8, 3, 5, -1]
1 3 [1, 8, 8, 5, -1]
8 5 [1, 3, 8, 5, -1]
3 5 [1, 3, 8, 8, -1]
8 -1 [1, 3, 5, 8, -1]
5 -1 [1, 3, 5, 8, 8]
3 -1 [1, 3, 5, 5, 8]
1 -1 [1, 3, 3, 5, 8]
[-1,1, 3, 5, 8]
*/

  不知道同学们有没有看出什么端倪。反正我一开始是什么都没有发现&＃xff0c;那就分析分析咯。
  第一次1和8比较&＃xff0c;1<8&＃xff0c;不需要调整位置。
  第二次8和3比较&＃xff0c;8>3&＃xff0c;需要调整位置。但是这里没有交换位置&＃xff0c;仅仅是8覆盖了3位置。这里就可以推断出不是单纯的使用了冒泡算法。
  第三是1和3比较&＃xff0c;1<3&＃xff0c;3替换了8的位置。什么鬼&＃xff0c;几个意思&＃xff1f;&＃xff1f;&＃xff1f;看到这里我也是表示不懂呀。那就继续往下看咯。
  第四是8和5比较&＃xff0c;8>5&＃xff0c;又仅仅是覆盖&＃xff0c;没有交换位置。还是不懂&＃xff0c;继续往下&＃xff01;
  第五是3和5比较&＃xff0c;3<5&＃xff0c;5替换了8的位置&＃xff0c;不懂&＃xff0c;继续往下&＃xff01;
  第六是8和-1比较&＃xff0c;8>-1&＃xff0c; 还仅仅是覆盖&＃xff0c;继续往下&＃xff01;
  第七、八、九次&＃xff0c;-1依次和5&＃xff0c;3&＃xff0c;1做了比较&＃xff0c;并且5&＃xff0c;3&＃xff0c;1都移动了一次位置。等等&＃xff0c;这怎么和插入排序法有点相似。

  再试试一下

var arr&＃61;[1, 8, 9, 5, 2];
arr.sort(compare);
/**
控制台输出
1 8 [1, 8, 9, 5, 2]
8 9 [1, 8, 9, 5, 2]
9 5 [1, 8, 9, 5, 2]
8 5 [1, 8, 9, 9, 2]
1 5 [1, 8, 8, 9, 2]
9 2 [1, 5, 8, 9, 2]
8 2 [1, 5, 8, 9, 9]
5 2 [1, 5, 8, 8, 9]
1 2 [1, 5, 5, 8, 9]
[1, 2, 5, 8, 9]
*/

  没跑了&＃xff0c;这就是插入法。再捋捋&＃xff0c;第一次冒泡完之后&＃xff0c;前两位肯是有序的。第二次比较&＃xff0c;如果发生位变化&＃xff0c;a先向后移动一位&＃xff0c;b没有直接前移&＃xff0c;而是通过插入法找到正确的位置插入&＃xff0c;此时前三位有序。如果没有发生位置变化&＃xff0c;说明此时前三位已经有序&＃xff0c;继续拿有序的最后一位和之后的一位比较。如此循环&＃xff0c;直至整个数组有序。

  到这里&＃xff0c;我们得出了结论&＃xff1a;sort()方法是使用的冒泡和插入两种方式结合进行排序的。 如果对排序不熟悉的同学&＃xff0c;可以看看——《十大经典排序算法》

  经一位大神的提醒&＃xff0c;EMCAScript并没有定义sort()方法使用的排序算法&＃xff0c;各个浏览器实现的方式并不相同。以上的结论我只在chrome和fireFox中存在。以上结论在chrome和fireFox也并不完全正确&＃xff0c;当数组长度过长时&＃xff0c;就不在是使用冒泡和插入两种方式结合进行排序了&＃xff0c;而是使用一种我不了解方法。先修改错误的结论。等我弄清楚那种我不了解的方法&＃xff0c;再来更新_srot()方法。

  童鞋你似不似以为到这里就完了&＃xff0c;文章就完美结束了&＃xff1f;当然不似!!!接下来,闲着没事我们模仿sort(),实现一个和sort()方法功能一样的自定义方法玩玩呀。

实现一个和sort()方法相似的_sort()方法

  这里不多说&＃xff0c;直接上代码。然后看注释

Array.prototype._sort.f&＃61;function(a,b){ //设置默认按照Unicode位点进行排序a&＃43;&＃61;"",b&＃43;&＃61;"";return a}Array.prototype._sort&＃61;function(f){/*** 如未传入实参* 或传入的实参不是函数* 使用默认的排序函数 &＃xff08;按字符顺序&＃xff09;*/var f&＃61;f&&typeof(f)&＃61;&＃61;"function"?f:Array.prototype._sort.f,len&＃61;this.length,i&＃61;0,t;/*** 这个循环开始排序* Array.sort()使用的是一种冒泡各插入结合的排序方法* */for(i&＃61;0,t&＃61;undefined;i0){ //大于零则需要交接位置t&＃61;this[i&＃43;1],this[i&＃43;1]&＃61;this[i];}/*** 如果t值是unfeined&＃xff0c;* 则当前的这次骑比较没有发生位置变化* 也就不需要使用插入法了*/if(t){//使用插入法找到正确的插入位置&＃xff0c;上面排序算法还有优化插入法排序的方法for(var j&＃61;i-1;j>&＃61;0;j--){if(f(this[j],t)>0){//如果当前元素大于t,则当前元素后移一位this[j&＃43;1]&＃61;this[j];}else{//否则表示找到插入点了&＃xff0c;插入t,并退出循环this[j&＃43;1]&＃61;t;t&＃61;undefined;//将t设为undefined&＃xff0c;防止冒泡未发生替换就进入插入法排序break;}} } }return this; //返回排序后的新数组
}

  到这里就完了&＃xff1f;&＃xff1f;&＃xff1f;No!No!No!虽然我们实现了_sort()方法&＃xff0c;但是还有一个不完美的地方。说明第三点说了对undefined的处理规则&＃xff0c;我们还没有对unfined进行任何处理呢。还需要在上面的排序循环开始之前添加这样一段。

//这个循环把所有数组undefined的元素和数组最后一个不是undefined的元素替换
//不同浏览器对undefined处理方式不同&＃xff0c;这里模仿chrome的处理方式
for(;i&＃61;i的条件*/while(this[len-1]&＃61;&＃61;&＃61;undefined&&len>&＃61;i){ len--;}/*** 如果len等于i* 就表示下标不小于i的元素都是undefined了* 可以不用继续遍历了*/if(len&＃61;&＃61;&＃61;i) break; /*** 使用t将最后一个不是undefined的元素保存起来* i in this 是判断这个元素是不存在&＃xff0c;还是值是undefined* 数组中一个不存在的元素&＃xff0c;也会返回undefined(稀疏数组)* 这两者还是有区别的* 如果不存在i in this会返回 false*/t&＃61;this[len-1];if(i in this)this[len-1]&＃61;undefined; //元素值为undefined&＃xff0c;直接将要替换元素值设为undefinedelsedelete this[len-1]; //元素不存在&＃xff0c;通过删除将要替换的元素设置为不存在&＃xff0c;this[i]&＃61;t; //替换undefined元素//又塞了一个undefinef到后面&＃xff0c;所以要排序的元素又少了一个&＃xff0c;再减减一下len--; }}

  到这里是真结束了&＃xff0c;谢谢大家&＃xff01;如何有什么我说错了或者没说明白的地方&＃xff0c;欢迎大家留言一起讨论&＃xff0c;大家一起学习&＃xff0c;共同进步么。