线性排序算法分析总结

栏目: 编程工具 · 发布时间: 5年前

内容简介:桶排序(Bucket sort),顾名思义,就是用很多桶来存放元素。这里的桶其实是一个区间,一个用来存放在某个数值范围内的元素。比如一个 0-9 的桶表示存放数值大于等于0,小于等于9的元素。我们有 n 个元素,m 个 桶,假设数据很均匀地放到每个桶里面,每个桶就是 k = n/m 个元素,每个桶进行快速排序,时间复杂度是 O(klogk),那 m 个桶的时间复杂度是 O(m * klogk),即 O(nlog(n/m))。当 m 接近于 n 时,n/m 就是一个很小的常量,这样时间复杂度就是 O(n) 了

桶排序(Bucket sort),顾名思义,就是用很多桶来存放元素。这里的桶其实是一个区间,一个用来存放在某个数值范围内的元素。比如一个 0-9 的桶表示存放数值大于等于0,小于等于9的元素。

我们有 n 个元素,m 个 桶,假设数据很均匀地放到每个桶里面,每个桶就是 k = n/m 个元素,每个桶进行快速排序,时间复杂度是 O(klogk),那 m 个桶的时间复杂度是 O(m * klogk),即 O(nlog(n/m))。当 m 接近于 n 时,n/m 就是一个很小的常量,这样时间复杂度就是 O(n) 了。

根据前面时间复杂度的推导,我们会发现,可以进行桶 排序 的场景要求很高。

首先,它要求数据可以较为均匀地分布到每个桶里。假如某些桶的数据相比其它桶非常少,其实等同于将它被合并放到另一个桶里,本质就是少了一个桶,m 就会变小,n/m 就会接近于 n。一种极端情况下,数据全放到一个桶里,时间复杂度就退化为 O(nlogn)。

虽然一般情况下,能用桶排序的场景比较少,但有一种场景就很适合桶排序,那就是 外部排序

外部排序(External sorting)是指能够处理极大量数据的排序算法。通常外部排序会用到外存。在数据量很大,内存无法一次全部读取的情况下,就需要用到外部排序。除了可以用 桶排序,我们还可以用 归并排序 来做外部排序。

假设我们有一个很大的文件,里面保存了很多数据,要对它们进行排序,具体做法是:

  1. 扫描大文件的数据得到数值范围,确定合适的桶的数量(保证 n/m 的数据量可以一次读入到内存中)。这里的桶会对应一个个小文件。
  2. 从头往后扫描大文件,将数据按照范围放到小文件中。
  3. 每个小文件的数据全部读取到内存中,进行排序。这里注意使用的 排序算法 是否为原地排序,且是否为稳定排序。具体根据实际情况进行选择合适的排序算法。另外,如果小文件里的数据(一般来说是数据分布不均匀导致的)仍不能一次读取到内存中,可以对小文件继续进行拆分,得到第二小文件。
  4. 按顺序合并多个小文件为一个大的文件。

代码实现

暂无实现。

算法分析

1. 桶排序不是原地排序

因为我们需要创建多个桶,需要额外的内存空间,桶如果是用数组实现,理论上是创建要 m 个 长度为 n 大小的数组。不过一般来说不会这样做,我们会考虑使用链表、动态数组、跳表和红黑树等动态数据结构来保存。桶排序的空间复杂度我们可以大概说成是 O(n) 。

2. 桶排序是稳定的排序

其实桶排序是否稳定,是取决于桶内部使用的排序算法,如果使用的是一种稳定的排序算法,那这种桶排序算法就是稳定的排序算法。

3. 桶排序的时间复杂度是 O(n)

桶排序的时间复杂度是 O(n) 是有前提条件的,那就是桶的数量 m 接近于 n,且数据要尽量均匀分布。极端情况下所有的数据都放到一个桶里,此时桶排序的时间复杂度就会退化为 桶内部使用的排序算法 的时间复杂度。

计数排序

计数排序不好理解,因为脑子要拐几个弯。

当数据有大量重复时,且都为正整数时,我们可以考虑使用计数排序。

计算排序算是比较特殊的桶排序,因为它的桶只有一种值。假设一组数据的最大值为 k,那我们就分为 k 个桶。

首先我们遍历原数组,用数组 c 统计每个值出现的次数,然后我们在让数组 c 的数组元素和前面的元素累加,即 c[1] = c[0] + c[1], c[2] = c[2] + c[1], ... 。这样得到了新的数组 c ,此时数组元素 c[i] 表示的就是原数组中小于等于 i 的数据的个数。

然后我们从后往前遍历原数组,将元素的数值 v 找到数组 c 中对应索引的值。这个值 c[v] 代表原数组中小于等于 v 的数据个数。又因为我们是从后往前遍历数组,所以当前的原数组的元素就是排序后的第 c[v] 个元素。于是我们就把这个元素放到一个新开的空数组 r 的第 v 个位置。另外我们不要忘记 c[v]自减一,因为我们已经取走了一个数,小于等于 v 的数据的个数也要跟着减1。

遍历完后,r就是我们要的排序好的数组了。

代码实现

const countingSort = (a) => {

    // 找出数组的最大的数。
    let i, max = a[0];
    for (let i = 1; i < a.length; i++) { 
        if (a[i] > max) {
            max = a[i];
        }
    } 

    let c = [];
    for (i = 0; i <= max; i++) {
        c[i] = 0;
    }
    for (i = 0; i < a.length; i++) {
        c[a[i]]++;
    }
    console.log('数组C(值表示小于等于索引的数量):', c.toString());
    // 计数累加
    for (i = 1; i < c.length; i++) {
        c[i] = c[i - 1] + c[i];
    } 

    // 从后往前扫描 数组a(从后往前可以保证是 稳定 排序)
    let r = [];
    for(i = a.length - 1; i >= 0; i--) {
        let index = c[a[i]] - 1;   
        // 为什么要减1?? 
        // 因为 c[] 记录的是小于等于索引的元素数量,比如小于等于 3 的有 4个,
        // 所以 3 必然是这第4个(索引对应3,所以要减1)。
        // 你会说小于等于并不是等于啊,但我们现在是正在遍历原数组,且确实发现有这个 3 了。
        r[index] = a[i];
        c[a[i]]--;
    }
    return r;
}
复制代码

算法分析

1. 计数排序不是原地排序算法

计数排序使用了额外的两个数组(数组 c 和 数组 r),他们的长度分别为 k 和 n,所以空间复杂度是 O(k+n),所以 线性排序不是原地排序算法

2. 计数排序是稳定的排序算法

不过线性排序是 稳定 的排序算法,因为它没有进行元素的交换。

3. 计数排序的时间复杂度是 O(n)

这个毫无疑问时间复杂度是 O(n),当然也可以说时间复杂度是 O(n+k),只是前面的被省略的系数发生了变化。

另外,计数排序的局限性还是挺大的,首先计数排序只能用在 数据范围不大的场景 中,因为数据范围越大(尤其是 k 远大于 n 的情况),需要创建的两个数组长度也越长。此外因为要用到数组的索引,所以只能对 非负整数 进行排序,当然我们可以对不符合情况的数据进行一些处理(不改变相对大小),转换为非负数。比如对于小树,可以乘以 10 的倍数,有负整数则可以每个数据加相同大小的值,使负整数变成非负整数。

基数排序(Radix sort)

较短的数值前面补0,从右往左 每一位 上的数进行排序,直到最高位。

基数排序的对比排序是基于 的,我们想要基数排序的时间复杂度为 O(n),那每一位的排序都必须是线性排序,网上比较常见的是配合桶排序的基数排序(我也不知道为什么反正我配合使用的是计数排序)。

代码实现

const radixSort = (a) => {
    // 从低到高排序
    
    // 位数拆分
    let i, tmp = [];

    const size = 11;    // 正数的位数
    let radix = 1;
    for (let j = 0; j < size; j++) {
        for (i = 0; i < a.length; i++) {
            let k = Math.floor(a[i]  / radix) % 10   // 获取j位上的值。
            tmp[i] = k;
        }
        a = cSInRadixSort(tmp, a);
        radix *= 10; 
        // console.log(a.toString());
        // 计数排序一下。(要专门为基数排序写一个计数排序,因为排序的是 a,而不是 tmp)
        // return c
    }
    return a;
  
}


/**
 * // 基数排序专用的 计数排序
 * @param {Array} a 提炼出的某位上的值
 * @param {Array} o 原数组
 */
const cSInRadixSort = (a, o) => {

    // 找出数组的最大的数。
    let i, max = a[0];
    for (let i = 1; i < a.length; i++) { 
        if (a[i] > max) {
            max = a[i];
        }
    } 

    let c = [];
    for (i = 0; i <= max; i++) {
        c[i] = 0;
    }
    for (i = 0; i < a.length; i++) {
        c[a[i]]++;
    }
    // console.log('数组C(值表示小于等于索引的数量):', c.toString());
    // 计数累加
    for (i = 1; i < c.length; i++) {
        c[i] = c[i - 1] + c[i];
    } 

    // 从后往前扫描 数组a(从后往前可以保证是 稳定 排序)
    let r = [];
    for(i = a.length - 1; i >= 0; i--) {
        let index = c[a[i]] - 1;   
        r[index] = o[i];    // 这里 的 a[i]  改成 o[i]
        c[a[i]]--;
    }

    return r;
}
复制代码

算法分析

1. 基数排序不是原地排序算法

因为它要配合一种线性排序算法(桶排序或计数排序),这些线性排序算法都需要额外内存空间。

2. 基数排序是稳定的排序算法

其实还是取决于和基数排序配合使用的线性排序算法的稳定性


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

The Four

The Four

Scott Galloway / Portfolio / 2017-10-3 / USD 28.00

NEW YORK TIMES BESTSELLER USA TODAY BESTSELLER Amazon, Apple, Facebook, and Google are the four most influential companies on the planet. Just about everyone thinks they know how they got there.......一起来看看 《The Four》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具