美文网首页
关于js数组元素打乱的简单思考

关于js数组元素打乱的简单思考

作者: zhou | 来源:发表于2015-05-22 16:38 被阅读1153次

    引子

    今天遇到一个需求,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;

    }

    运行结果:

    发现比较次数比上面还少了。

    相关文章

      网友评论

          本文标题:关于js数组元素打乱的简单思考

          本文链接:https://www.haomeiwen.com/subject/bflutttx.html