引子
今天遇到一个需求，js实现时需要打乱数组元素以达到随机效果。php中有专门的shuffle函数实现这个功能，但js没有这样的函数，需要自己实现。
上网搜了一下，最简单的方法如下：
function randomsort(a, b) {
//用Math.random()函数生成0~1之间的随机数与0.5比较，返回-1或1
return Math.random() > .5 ? -1 : 1;
}
var arr = [1, 2, 3, 4, 5];
arr.sort(randomsort);
首先看下js的sort函数。
sort()方法用于对数组的元素进行排序。
arrayObject.sort(sortby)
参数sortby可选，规定排序顺序，必须是函数。
注意，该函数在原数组上进行排序，不生成副本。
如果调用该方法时没有使用参数，将按字母顺序对数组中的元素进行排序，说得更精确点，是按照字符编码的顺序进行排序。要实现这一点，首先应把数组的元素都转换成字符串（如有必要），以便进行比较。
如果想按照其他标准进行排序，就需要提供比较函数，该函数要比较两个值，然后返回一个用于说明这两个值的相对顺序的数字。比较函数应该具有两个参数a和b，其返回值如下：
若a小于b，在排序后的数组中a应该出现在b之前，则返回一个小于0的值。
若a等于b，则返回0。
若a大于b，则返回一个大于0的值。
疑问
由于现在比较函数不是真实比较，只是随机返回一个-1或1，那有一个疑问，这样随机的返回值会不会增加排序比较的步骤或者导致长时间排序，或更严重的无线循环比较呢。如果想要解决这个疑问，需要知道js引擎实现sort函数使用的排序算法。
常见排序算法有：冒泡排序、选择排序、插入排序、希尔排序和快速排序。
下面简单介绍一下，这几种排序算法的思想。
一、冒泡排序
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，依此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，依此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。
优点：稳定，比较次数已知；
缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。
二、选择排序
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[1]与a[3]的值，若a[1]大于a[3]则交换两者的值，否则不变。再比较a[1]与a[4]，依此类推，最后比较a[1]与a[n]的值。这样处理一轮后，a[1]的值一定是这组数据中最小的。再将a[2]与a[3]~a[n]以相同方法比较一轮，则a[2]的值一定是a[2]~a[n]中最小的。再将a[3]与a[4]~a[n]以相同方法比较一轮，依此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。
优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少；
缺点：相对之下还是慢。
三、插入排序
已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、b[2]、……b[m]，需将二者合并成一个升序数列。首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值，若b[1]仍然大于a[2]，则继续跳过，直到b[1]小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1的数组a）
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。
四、缩小增量排序
由希尔在1959年提出，又称希尔排序。
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大是，插入排序的效果很好。首先取一增量d(d
优点：快，数据移动少；
缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。
五、快速排序
快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据a[x]，然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。
优点：极快，数据移动少；
缺点：不稳定。
实际上了解了几种排序算法的思想，应该可以确定不会出现上面疑问中的问题了，因为这几种排序算法实际上每步都在缩小排序范围，不会扩大。
验证
那js引擎如何使用哪种算法的呢？我写个简单的例子才测试一下，代码如下：
function sortNumber(a,b){
console.log(a+':'+b);
return a - b
}
var arr = new Array(6)
arr[0] = "8"
arr[1] = "5"
arr[2] = "4"
arr[3] = "6"
arr[4] = "2"
arr[5] = "1"
console.log(arr)
console.log(arr.sort(sortNumber))
在chrome和opera浏览器上执行结果一样，如下：
从上面打印出的执行过程可以看出使用的是插入排序算法。
如果使用的是插入排序算法也就不会出现上面疑问中的问题了。
修改上面的比较函数，改成随机返回值。
function sortNumber(a,b)
{console.log(a+':'+b);
return Math.random() > .5 ? -1 : 1;
}
运行结果：
发现比较次数比上面还少了。
网友评论