站内链接:

分类

比较类-非线性时间-排序

  • 交换类排序:快速排序、冒泡排序
  • 插入类排序:简单插入排序、希尔排序
  • 选择排序:简单选择排序、堆排序
  • 归并排序:二路归并排序、多路归并排序

非比较类-线性时间-排序

  • 计数排序: O(n), 特殊的桶排序, 此时桶的个数最大, 创建 maxvalue-minxvalue+1 的数组
  • 基数排序: 利用位数从低位到高位, 不断的进行数值排序
  • 桶排序: 将数组分配到有限数量的桶中, 之后再对桶分别排序.
  • 索引排序: 在排序过程中, 如果数据元素本身很大, 不断的赋值移动消耗资源, 则可将数据移动更改为索引移动, 减少复杂度

内存排序

  1. 内存排序

内存排序是指将待排序的数据存储在计算机的内存中,并在内存中进行排序操作,而不涉及外部存储介质(如硬盘)的读写,上面讲解的这几个排序一般情况下都是内存排序

  1. 外排序

外排序(External Sorting)是一种处理大规模数据时的排序方法,因为数据无法全部加载到内存中,需要借助外部存储介质(如硬盘)进行排序操作。外排序通常涉及将数据分成多个块,并使用内存中的部分数据进行排序,然后将排序好的数据写回到外部存储介质,最后对各个块进行合并,得到最终的有序结果。其步骤一般如下:

  • 划分阶段:将大规模的待排序数据划分为多个能够适应内存的块(通常是固定大小的块)。这些块可以同时存放在内存中的一部分。
  • 排序阶段:对每个块使用适合内存大小的排序算法进行排序。常见的排序算法包括快速排序、归并排序、堆排序等。在排序过程中,可能需要将块的部分数据加载到内存中进行排序,然后将排序好的数据写回到外部存储介质。
  • 合并阶段:将排序好的块逐个读入内存,并使用归并操作将它们合并成更大的块。合并操作通常是两两合并,直到最终得到一个有序的大块。
  • 重复合并阶段:如果仍然有多个大块,重复进行合并操作,直到最终得到完全有序的结果。

性能与分类图解

性能:

algorithm performance

分类:

algorithm classify

性能分类总结:

  • 平方阶:O(n2),简单排序(直接插入、直接选择、冒泡)
  • 线性对数阶:O(nlgn),二分思维– (快速排序、堆排序、归并排序)
  • O(n1 +£):£值范围[0..1],例如 n1.2,n2 等阶,希尔排序
  • 线性阶:O(n),空间换时间(桶排序、基数排序)

排序选择:

  • 基本正序时——简单排序最适合
  • n 较大时——快排、堆排、归并

分治法

说明

分治法(Divide and Conquer)是一种算法设计策略,它将问题分解为更小的子问题,并通过解决子问题来解决原始问题。分治法的核心思想是将复杂问题分解为简单的、相互独立的子问题,然后将子问题的解合并起来得到原始问题的解。其主要分为 3 个步骤:

  • 分解(Divide):将原始问题分解为更小的子问题。这个步骤通常通过递归的方式进行,将问题划分为多个规模更小但结构与原始问题相似的子问题。
  • 解决(Conquer):递归地解决子问题。这个步骤将子问题逐个解决,直到子问题的规模足够小,可以直接求解。
  • 合并(Combine):将子问题的解合并为原始问题的解。这个步骤将子问题的解合并起来,得到原始问题的解。

分治法常用于解决一些具有重叠子问题性质的问题,例如归并排序、快速排序、最大子数组和问题等。其优点如下:

  • 可以将复杂问题划分为更小的子问题,简化问题的解决过程。
  • 可以利用并行计算的优势,将子问题并行处理,提高算法的效率。
  • 可以使算法更易于理解和实现,降低算法的复杂度。

缺点:

  • 分治法通常需要额外的空间来存储子问题的解,可能会增加空间复杂度。
  • 递归调用的开销可能导致较高的时间复杂度。
  • 对于某些问题,分解和合并的过程可能会带来额外的计算开销。

使用案例

  • 归并排序: 将数组分解, 解决, 合并
  • 快速排序: 存在一点分治的思维, 将以某一个值为基准, 对整个数组进行分解, 只不过没有合并的过程

归类法

说明

将一组元素或对象划分成不同的类别或类别的过程。归类可以基于事先定义的分类标准,根据元素的特征或属性将其分组到不同的类别中。归类的目的是将相似的元素放在一起,并将它们与其他不同的元素区分开来。

如何让同类数据存储在一个相同的地方? 对于单位数据, hash 天生自带该功能, 对于复合数据那么需要一定的算法, 对原始数据进行整合归类。

使用案例

  • 桶排序: 有点类似归类
  • 基数排序: 按照位数来进行归类

Example

出现次数最多纪录

问题: 海量日志数据, 提取出现次数最多的 IP.

分析: 注意到 ipv4 的位数(32 位), 如果载入所有 ip 到 hash 中, 最多有 2^32 个记录, 需要采用分而治之的思想, 将 ip 的地址 Hash(ip) % 1024, 即将 ip 分别存储到 1024 个文件中, 这样每一个文件最多包含: 2^32 / 1024 == 4MB

步骤(分治 + Hash);

  • 分治, Hash(ip) % 1024, 海量 ip 分配到 1024 个文件中, 每一个文件大概 4MB 内存
  • 对于每一个小文件, 构建 key->value 的映射, 其中 ip 为 key, 记录出现次数最多的 ip
  • 对于 1024 个小文件筛选出次数最多的 IP 值, 因为所有的相同 IP 利用 hash 都会映射到同一个文件中.

出现次数前 100 的记录

问题: 海量日志数据, 提取出现次数最多的前 100 IP.

分析: 该问题和 3.1 的区别在于提取多个数据. 即对每一个小文件, 提取前 100 项数据, 得到数据项: 1024 * 100, 最后对这个 1024 个文件进行归并排序

步骤:

  • 分支
  • 对于小文件, 利用 trie/hash_map 进行分类, 记录出现次数最多的 100 个 ip
  • 进行归并排序

对多个大文件进行频度统计

问题: 有 10 个文件, 每一个文件 1G, 每个文件的每一行存放的都是用户的 query, 每个文件的 query 都可能重复, 需要按照 query 对文件进行排序.

最终场景: 10 个文件, 其中文件中的 query 都有有序的, 并且文件 a 的最小频度 > 文件 b 的最大频度

分析: TOP K 算法, 首先需要对数据进行归类, 对相同的 query 进行合并, 利用 hash 进行归类, 其次对归类的每一个文件进行排序操作, 最后对所有文件进行归并排序. 这里就使用到归类法.

步骤:

  • 首先, 对 10 个文件依次进行 hash(query) % 10, 这里假设 hash 的数据都能平均的分到 10 个文件里面, 得到 10 个归类后的文件
  • 其次, 找一个 2G 内存的机器, 对每一个文件进行排序, 输出 query-query_count
  • 再次, 对 10 个文件进行归并排序

查找 a 是否在 40 亿个不重复的 unsigned int 整数集中

问题: 对于 40 亿个不重复的 unsigned int 整数, 未排过序, 任意给定一个数, 如何快速判断
是否在改集合中.

最终场景: 快速的查找某一个数

分析: 一般, 查找算法的前提都是基于排序算法, 只有对目标数据进行排序, 后续的查找
算法才能更加方便和快捷. 一般而言, 树结构对于查找算法最适合, 考虑到整数的特殊性,
这里可以按照位数来将一个大文件改造成一棵小文件树结构.

步骤:

  • 首先, 对 40 亿个数进行分类, 最高位 0-A 文件, 最高位 1-B 文件, 此时两个文件大小 20 亿条数据
  • 其次, 重复上述步骤, 构建一棵哈夫曼树结构(霍夫曼编码)
  • 再次, 查找, O(logN)

逆序对组合

问题: 对于一个长度为 n 的整数数组 A, 找出”逆序对”的个数, 对于下标 i,j, 当 i>j,
A[i]小于 A[j], 则(A[i], A[j])称为逆序对

最终场景: 最终会列出所有的逆序对, 并且是有序的.

分析: 如果使用暴力方式, 那么对于每一个值 a, 比较其他 N-1 个值, 重复 N 次, 整个时间复杂度为 O(N^2). 如果采用分治思想, 以 mod 中间点进行数组切割, 递归统计: 左半部分, 右半部分, 跨越中点的个数(即 i 在左边, j 在右边的合法值队), 最后进行归并, 此时归并排序
改变的位置值实际上不影响最终的结果, 因为当前已经排序好的组合在位置上是一个整体,
即对外是一个下标: set-i, 其他递归集也是这样的: set-j, set-x.

步骤:

  • divide: 对数组进行对半切分, 每一个子数组都是一个逆序对组合题目
  • conquer: 递归的对子数组进行对半切分
  • combine: 对两个已经排好序的子数组进行归并排序, 同时记录逆序对, 注意, 这里主要工作量在归并排序, 以及记录逆序对这里