美文网首页
一天一算法 - 基础排序

一天一算法 - 基础排序

作者: ghwaphon | 来源:发表于2017-03-03 14:03 被阅读146次

    准备

    在实现排序算法之前,先介绍将用到的几个函数。比如说为了将数组中数字的顺序打乱,我们可能需要一个洗牌函数,为了记录代码运行的时间,我们需要一个记录时间的函数。下面来介绍这些函数的实现。

    1. 洗牌方法

      function shuffle() {
         return Math.random() - 0.5;
      }
      

    因为 Math.random() 方法产生的数值在 [0,1) 之间,所以这个方法可以确保返回的数值是随机的。有了这个函数之后,只需要将其传入数组的 sort() 方法作为参数即可打乱数组。这个方法借鉴自 《12 个 JavaScript 技巧》 一文。

    1. 记录时间

    记录时间其实很简单,我们只需要在代码执行前获取到时间,然后执行完毕之后再获取一次时间,取二者之间的差值即可,就像下面这样。

        var Clock = {
             "time": function() {
                this.start = new Date().getTime();
            },
    
            "timeEnd": function() {
                this.end = new Date().getTime();
                return Math.floor(this.end - this.start);
            }
        }
    

    如果你在 Java 中利用上面这个方面来计时,那是合情合理的,不过我们这是在写 JavaScript 代码,我们的宿主环境非常体贴,为我们提供了 console.time()console.timeEnd() 方法来帮助我们计算 js 代码执行的时间。

    不过值得一提的是,如果你利用 Clock 对象来计时会让你感到失望,因为它计时不是太准确,我使用上面提到的方法对选择排序进行了千数量级的计时, Clock 对象给我的结果使 8ms 左右,而 console.time()console.timeEnd() 给出的结果却是 4ms, 咋一看,好像时间长了两倍,当我在进行万数量级测验时,发现二者计时还是相差 4ms 左右,所以我的理解是,我们使用自定义计时方法是创建了一个对象,而这 4ms 使我们创建这个对象花费的时间。

    好了,说的已经够多了,下面开始进入正题。


    选择排序

    选择排序的思想非常简单,首先,找到数组中最小的那个元素,然后将它和数组的第一个元素交换位置。其次,在剩下的元素中找到最小的元素,将它和数组的第二个元素位置交换。如此往复,直到整个数组排序。

    从算法的思想中我们可以得出结论,在最好的情况下,也就是说数组元素全部有序的情况下,选择排序需要经历 N^2 / 2 次比较,0 次位置变换。在最差的情况下,也就是说所有数组元素一开始都不在最终位置上,需要经历 N^2 / 2 次比较和 N-1 次移位。

    function selectionSort(array) {
        var length = array.length,
            min,
            temp;
    
        for(var i = 0; i < length; i++) {
            min = i;
    
            for(var j = i; j < length;j++) {
                if (array[min] > array[j]) {
                    min = j;
                }
            }
    
            if (min !== i) {
                temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
    }
    

    可见,这种算法实现起来十分简单,不过遗憾的是这种排序算法用于处理小数组的排序尚能称职,对于比较多的数据却是无力回天,这也正是我们探索其他方法的动力所在,下面来讲一个同样简单但是性能优于选择排序的算法 —— 插入排序。


    插入排序

    插入排序的思想就是从第二个元素开始,与前面的元素进行比较,直到找到比当前元素还要小的元素之后,将元素放下来,然后将后面的元素依次后移,腾出位置。

    举个例子来说,对于数组 [2, 1,0, 4],首先从 1 也就是第二个元素开始,与前面的 2 进行对比,发现 1 比 2 小,而且 2 前面也没有元素了,所以要将 1 放置在 2 的前面,这个时候 2 就需要后移为 1 腾出位置,这个时候数组元素就变成了 [1, 2, 0, 4]。然后 0 与 2 比较,发现 0 比 2 小,这个时候交换 0 与 2 的位置,再 与 1 进行比较,发现 0 还是比 1 小,所以交换 1 与 0 的位置,这个时候数组就变成了 [0, 1, 2, 4]。4 与 2 比较,比 2 大,保持原位置不变。

    那么,插入排序与选择排序的差别在哪里呢?选择排序会对余下的所有元素进行大小比较,而插入排序则不是这样,对位于 i 下标的元素来说,只要它在 (i-1) - 0 的路径中找到比 i 小的元素,它就会终止比较,这对于一个已经基本排序的数组来说,是一个非常大的优化。不过,有利也有弊,插入排序相对于选择排序的缺点就是它移动次数会显著增加。

    在最佳情况下,也就是说对于一个有序数组,插入排序只需要 N-1 次比较和 0 次交换。在最差情况下,也就是对于一个逆序数组,它需要 N^2 / 2 次比较和 N^2 /2 次交换。

    function swap(array, i, j) {
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    function insertionSort(array) {
        var length = array.length,
            temp;
    
        for(var i = 1; i < length; i++) {
            for(var j = i; j > 0 && array[j] < array[j - 1]; j--) {
                swap(array, j, j-1);
            }
        }
    }
    

    插入排序平均情况下会比选择排序快一倍左右,我以万级数量级数据对这两个算法进行了比较,选择排序耗时 120 ms 左右, 插入排序在 65ms 左右。当然,这只是在我电脑上的数据,根据电脑配置的不同得出的结果会有所不同。

    还有一点值得提及,对于一个基本有序的数据来说,插入排序可能比任何排序算法都要快,也就是说它可能比归并排序和快速排序还要快。那么该怎么定义基本有序呢?满足下面三个条件之一就可以了。

    1. 数组中的每个元素距离它的最终位置都不远。
    2. 一个有序的大数组接一个小数组。
    3. 数组中只有几个元素的位置不正确。

    希尔排序

    希尔排序其实就是对插入排序进行改进,让其适应大数组排序。看了插入排序的代码你可能也发现了一个问题,如果一个非常大的数组,比如千万数量级的数组,它是逆序的,使用插入排序的话,那么我们不得不将最后一个元素一步步的移动到第一位,将倒数第二个元素一步步的移动到第二位,这样的话真的是拖垮了这个算法的性能,也就是插入排序的最坏情况。

    希尔排序只是对插入排序进行了一点点修改,却将这个算法的性能提升了一大截,将细节的作用展现的淋漓尽致。简单地说,希尔排序的思想就是使数组中任意间隔 h 的元素都是有序的,这样的数组被称为 h 有序数组。如果 h 很大,那么我们一次就可以将一个元素移动到很远的位置,这样就弥补了插入排序的缺陷。

    所以,关键的就是这个 h 的值该如何选择呢?事实上算法的性能和 h 的大小是有关系的,不过到目前为止并不知道 h 选取什么值是最好的,所以我一般选择数组长度的 1/3 左右 。

    function shellSort(array) {
        var length = array.length,
            temp,
            h = 1;
    
        while (h < length / 3) {
            h = 3 * h;
        }
    
        while (h >= 1) {
            for (var i = h; i < length; i++) {
                for (var j = i; j >= h && array[j] < array[j - h]; j -= h) {
                    swap(array, j, j - h);
                }
            }
    
            h = h / 3;
        }
    }
    

    关于希尔排序的运行时间具体是多少,目前尚不清楚,只能说它的运行时间达不到平方级别,最坏情况下的比较次数与 N^(3/2) 成正比。

    对于万级数量级数组,我用希尔排序只花了 8ms 的时间,相比于插入排序和选择排序,这种算法真是快了不知多少倍!


    冒泡排序

    对于冒泡排序是真的没什么好讲的了,它和选择排序一样,是各教科书介绍的重点,它的思想就是每次迭代将最大的元素排到末尾。我感觉这种算法在比较次数上和选择排序相同,而移动次数却又和插入排序差不多,所以性能比较差,是理论上的排序算法,并不实用。

    function bubleSort(array) {
        var length = array.length;
    
        for (var i = 0; i < length; i++) {
            for (var j = 0; j < length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:一天一算法 - 基础排序

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