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

摘要：本文除了会带大家了解一些方法后面简写为方法的基本定义和用法之外，还会探讨一下方法到底是使用的什么排序算法。下面我们来看看方法到底是如何排序的。

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

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

定义

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

语法

arr.sort()

arr.sort(compareFunction)

说明

1.如果没有指明 compareFunction ，那么元素会按照转换为的字符串的诸个字符的Unicode位点进行排序。 
2.如果指明了 compareFunction ，那么数组会按照调用该函数的返回值排序。即 a 和 b 是两个将要被比较的元素：

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

3.如果数组包含undefined元素（元素值为undefined或元素末定义）  
以上90%引用自MDN

实例

//例1.字母排序
var a = new Array("banna","watermelon","orange","apple");
s.sort(); 
console.log(a) //输出 ["apple", "banna", "orange", "watermelon"]
//没什么好说的，比较函数缺省，按照字母顺序升序排序 a.5?-1:1; //根据说明2-c特性，实现随机排序
});
console.log(a) //每次运行的输出都不同

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

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

var arr=[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]
*/

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

  再试试一下

var arr=[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]
*/

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

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

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

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

  这里不多说，直接上代码。然后看注释

Array.prototype._sort.f=function(a,b){ //设置默认按照Unicode位点进行排序
    a+="",b+="";
    return a0){ //大于零则需要交接位置
            t=this[i+1],this[i+1]=this[i];
        }
        
        /**
        * 如果t值是unfeined，
        * 则当前的这次骑比较没有发生位置变化
        * 也就不需要使用插入法了
        */
        if(t){
            //使用插入法找到正确的插入位置，上面排序算法还有优化插入法排序的方法
            for(var j=i-1;j>=0;j--){
            
                if(f(this[j],t)>0){//如果当前元素大于t,则当前元素后移一位
                
                    this[j+1]=this[j];
                    
                }else{//否则表示找到插入点了，插入t,并退出循环
                
                    this[j+1]=t;
                    t=undefined;//将t设为undefined，防止冒泡未发生替换就进入插入法排序
                    break;
                    
                }
            }                        
        }            
    }
    return this; //返回排序后的新数组
}

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

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

}

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