前端数据结构与算法细致分析—中下(排序)

javascript/jquery

浏览数:287

2020-5-26

上一篇文章,总结了一些常用的最基本的排序算法的复杂度以及实现。这一篇主写剩下的一些常用算法。

归并排序

归并排序正如名字所示。使用的是分治思想,即将一个大的问题拆解成一个个小的子问题,小的问题都解决了,组合到一起就等价于大的问题也解决了,如果你react使用的比较熟练,你应该能明白,一个大的模块我们可以将它拆解成细小的组件,每个组件完成大模块对应的某一部分功能,拼合再一起就组成了一个功能完整的大模块。
这里,比如要对一个数组进行排序,我们可以将数组分为若干个小数组,对每个小数组进行排序,当每个小数组有序之后,我们再将其合并为一个整体,这样,整个数组就是有序的了.图解:

代码实现

function sort(arr) {
    return divide(arr, 0, arr.length - 1)
}

function divide(nowArray, start, end) {
    if (start >= end) {
        return [ nowArray[start] ];
    }
    let middle = Math.floor((start + end) / 2);
    let left = divide(nowArray, start, middle);
    let right = divide(nowArray, middle + 1, end);
    return merge(left, right)
}

function merge(left, right) {
    let arr = [];
    let pointer = 0, lindex = 0, rindex = 0;
    let l = left.length;
    let r = right.length;
    while (lindex !== l && rindex !== r) {
        if (left[lindex] < right[rindex]) {
            arr.push(left[lindex++])
        } else {
            arr.push(right[rindex++])
        }
    }
    // 说明left有剩余
    if (l !== lindex) {
        while (lindex !== l) {
            arr.push(left[lindex++])
        }
    } else {
        while (rindex !== r) {
            arr.push(right[rindex++])
        }
    }
    return arr;
}

分析

1、归并排序稳定吗?

我们从图中一目了然的可以看到,归并排序在分合的过程中并不会设计到跨空间调换顺序,即每次拆解合并都是在原始顺序的基础上进行操作。所以归并排序是一个稳定的排序算法

2、归并排序的时间复杂度

我们设总时间为T(n),其中我们知道,divide中有递归,声明变量所花费的时间我们忽略,其实总的时间T(n)分解之后主要为left递归和right递归以及merge left和right,其实我们可以这么理解,T(n)分为了两个子问题(程序)T(left)和T(right)以及merge left和right
所以 T(n) = T(left) + T(right) + merge(left, right)
我们设merge(left, right) = C;
T(n) = T(left) + T(right) + C;
因为我们是从中间分开,所以若总时间为T(n)那么两个相等的子数组排序并merge的时间为T(n/2),我们知道最后merge两个子数组的时间复杂度O(n)[不用深入考虑递归,我们只看最后的left和right]
所以

T(n) = 2T(n/2) + n
     = 2(2T(n/4) + n/2) + n = 4T(n/4) + 2n
     = 4(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n
     = 8(2T(n/16) + n/8) + 3n = 16T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
整理一下可以得到 
T(n) = 2^kT(n/2^k)+kn
当T(n/2^k)=T(1)即n/2^k = 1;所以k=log2n
代入可得T(n)=n+nlog2n = n(logn + 1)

并且从上面分析我们也可以看出,归并排序中,最好,最坏的时间复杂度都是nlogn,因为不论数组的有序度如何,归并排序始终会经历分-合的过程。

3、归并排序是原地排序算法吗?

我们可以看到归并排序申请了临时的存储数组空间left,right。每有一个merge意味着会去申请一个临时空间,我们会把整个数组拆解到单个元素再进行合并,这里要注意,因为合并完成时我们要的只是merge后返回的新的有序数组,并没有依赖内部的作用域,所以在合并完成之后,临时开辟的内存空间就被释放掉了,我们知道javascript是单线程的,在任意时刻,都只是有一个函数在执行,假设数组长度为n,那么临时内存空间最大也不会超过n,所以空间复杂度是n。

快速排序

快速排序简称”快排”,应用非常多,其中也蕴含了”分治思想”。
核心原理:假设我们要排序的数组下标为a-z,我们先从a-z中选择一任意下标x作为分隔点,然后遍历数组,将小于分隔点的放到左边,大于分隔点的放到右边。这样,该数组就被划分成了三个部分, 分别是小于分隔点的那一部分,分隔点,大于分隔点的那一部分。接着我们结合前边的递归思想对a到x-1以及x+1到z下标的部分继续划分,这样当数组的子区间被划分到长度为1时,整个数组有序。如图(红色:分区点.绿色:排好区间):

图中大致为:首先我们拿8最为分隔点,第一次比较之后,大于8的元素全部在右边,小于在左边,8这个元素已经确定好位置为绿色。
接着我们在8左边的元素(6,5,1,3)中继续以3位分隔点按照上述四项继续划分直到所待排区间只有一个元素为止。
其实可以说每次排序之后,我们都会确定一个已排好的元素在中间,然后继续排它左右区间。
代码实现:

function sort(arr) {
    let l = arr.length;
    kp(arr, 0, l - 1)
}

function kp(arr, start, end) {
    if (start >= end) {
        return;
    }
    // 假设以末尾元素作为分隔点
    let tar = arr[end];

    // 设初始中间元素的位置为0
    /**
     * 这里解释一下point的精髓
     * 在这里的point定义它为中间点,其实就是分隔点的位置,怎么确定的呢?
     * 比如 13, 14,  17,  12,   9,   8.   8位分隔点,初始的时候,假设8前边的元素全部大于8,那么中间数(8也就是point)的下标则一直为0,因为比较完
     * 之后我们的顺序应该是 8, 13, 14,  17,  12,   9, 那如果是1, 14,  7,  12,   9,   8呢?因为1小于8,所以最终排好
     * 之后的中点一定是在1之后,所以point的位置+=1,遇到14>8,不会对分隔点有影响,遇到7<8,说明point的位置会再次后移一位...
     */
    let point = start;
    let i = start;
    while ( i < end ) {
        // 如果分区点元素大于目标元素
        if (tar > arr[i]) {
            let cache = arr[i];
            arr[i] = arr[point];
            arr[point] = cache;
            // 分区点位置应该向后移动一位
            point++
        }
        i++
    }
    // 最后将分区点插入中间,也就是和当前分区点下标位置元素互换
    let cache = arr[point];
    arr[point] = tar;
    arr[end] = cache;
    kp(arr, start, point - 1);
    kp(arr, point + 1, end)

}

分析

快速排序稳定排序算法吗?

我们看这个 4, 5, 8, 8, 12, 6;
经过第一次划分之后第一个8和6的位置调换了,所以快速排序是不稳定排序算法。

快速排序是原地排序算法吗?

我们在代码中可以看到巧妙之处,就是我们全程都是在用数组的位置索引进行数据比较和交换,没有申请额外的存储空间,所以快速排序是原地排序算法。注意,虽然这种原地快速排序的空间复杂度是O(1).因为我们没有申请额外的存储空间,但是我们在递归调用的时候还是消耗了一些空间的,这一点需要注意。

快速排序时间复杂度?

最好情况: 可以看出,我们每次都会划分成三个小区间,所以最好的情况一定是每次所划分的左右两个空间长度刚好相等(当然这是极少数)
最坏情况:那么每次划分我们只能划分出两个空间(即分隔点,全部比分隔点大或者小),说白了就是原始数组刚好有序或者有序度为0,这样每次我们只能确定一个元素(成了冒泡排序),这时候,该算法的复杂度就退化到了O(n^2)。
平均情况:
平均情况地推导用常规的方法非常复杂,完全可已不在这里浪费时间,但是可以明确地告诉大家,平均情况时间复杂度是nlogn。

快速排序优化

其实上面的代码我已经进行了第一步优化,就是原地排序,即不需要额外的内存空间。 但是我上面提到的,在极端情况下,快速排序会退化成冒泡排序,时间复杂度是O(n^2),这个该怎么解决呢?
其实看到这里,我希望大家不要马上往下面看,而是去思考一下。
首先,我们面对的问题是什么?根本原因是什么?
面对的问题就是我们可能每次划分区间时,区间分配极端,那么根本原因呢?根本原因就是我们每次都以最后一个元素作为分区点,其实我们拿到一个数组,它是完全有序或者0有序度的情况还是很多,所以我们首先可以以分区点的选取作为切入点。
第一种办法就是最常用的三数取中,即我们分别选取所排区间,最小,最大以及中间下标作为参考,先进行比较,取得的中间值作为分区点。如1, 2, 3,4,5, 6,7,8.我们拿1,4,8进行比较,得到合适的分区点为4,以此类推。代码就不写了,很简单,大家可以试着自己实现
第二种就是随机下标法,这个也不多说
以上是我们对分区点的选取作为切入点进行优化,如果是面试,你到了这一步基本OK,但是如果再问你,还可以继续优化吗?那答案一定是肯定得。我之前说过,如果将程序映射到真实的事物或场景,你学习起来会更加容易。
比如,我们排序一个超大数据量的订单100w+,按照金额从小到大排序,先假设内存足够,可以说n已经足够大了,那么选用时间复杂度O(nlogn)的算法一定比O(n^2)好(系数合理情况下),既然是订单金额,那么一定会有相等金额的订单。比如 1,4,5,17,2,6,7,6,6,6,19,2,6 这个数组中有很多重复的元素,假设第一个分区点为6那么第一次分区之后,所有的6都排在分区点6的左端,我们这个时候可以在代码里做一些优化,记录一下相等的元素,当比较完之后相同的元素我们可以省略,比如 1,4,5,2,7,2,6,6,6,6,6,17,19.这样第二次我们选择比较分区的时候就可以直接选取1,4,5,2,7,2和17,19.在处理大型数据的时候会大大提高效率。具体实现就不再写了,有兴趣的可以自己实现一下。

本篇主要就讲这两种,太多了也不好消化,大家加油。

作者:Yxaw