按 2D 曲线排序

• 下载源文件 - 6.9 KB

最先进的技术

如果您搜索维基百科网站，您会发现这些类似的算法

• 计算几何
• 在线算法
• Graham扫描
• 桶排序
• 奇偶排序

尽管这些算法的复杂度通常为 O(n²) 或 O(n log (n))，但它们通常不使用内存，而我自己的排序算法却使用了内存。

引言

在这篇之前的文章中，我曾写过，一个排序算法必须花费 n 次迭代来排序两个大小为 n / 2 的子列表。

当复杂度为 p * n 时，数字列表中的数字集合是理想的，前提是数字 n 恰好等于 2^p。

这第二篇文章是对一种数字排序方法的研究，该方法最多需要 3 * n 次操作，其中 n 是无序列表的精确大小。

总的来说，这项研究远非数学研究，也并非仅限于算术基本定理^[3]。

背景

有几种数字排序算法。通常，我们有要排序的数字；然而，也可能有其他格式：字符串、浮点数、对象或任何其他可比较的数据。

根据排序算法的实现方法，有两种可能的条件。
首先，必须提供一个比较器来比较两个元素。因此，整数满足此条件。

其次，要进行排序，您必须提供一个函数来计算列表中任意两个项之间的距离。

比较两个元素有时比计算两个元素之间的距离函数^[1] 更困难。 

图形解释

一个排序列表是一系列数字，因此对于每个 k > n，第 n 个数小于或等于第 k 个数。

当列表中的元素未排序时，排序算法会自动将该列表转换为一个从最小到最大的数字序列，而无需人工干预。

二十年前，计算机非常慢。这就是为什么拥有尽可能快的排序算法至关重要。

如果 n = 1000，最简单的排序算法最多会在 999000 次迭代后完成工作。

这个简单的算法很直观。其他算法则不然。如果我假设存在一个更快的排序算法，那么该算法可能会产生一个不完全排序的数字列表。

具有二维数组的图形函数

确实，我可以将一个数字列表精确地解释为一个具有二维数组的图形函数。

例如，假设下面列表中数字的顺序为

45    33   5    21   98    7    4    5    77    34

它显示了这种图形表示

一个排序的数字列表有一个图形表示，并且其表示是一条严格递增的线。

例如，连续偶数的列表与下面的图形表示完全相等。它表明 x 轴上的 1 个单位变化会引起 y 轴上的 2 个单位变化。

此外，这条线的代数方程是一个将每个值 x 映射到值 y 的函数。

y = 2 * x

现在，在一系列理想数字中，这条线是线性的，正如我在线性代数中提出的那样，我的意思是它满足这两个主要约束：加法运算 + 和乘法运算 *。

线和数字序列之间存在直接关系；当每个数字之间的数值间隔始终相等时，图形表示是一条精确的直线，如果间隔不相等，则该线包含不连续点。

例如，上面的列表在其曲线上有几个不连续点。

算法的开发

这个数学理论展示了算法的开发路径。

算法的第一步是读取输入列表中的所有数字（或其子集）。为每个组创建单独的线程相对容易。

一个等差数列是一个具有公差的数字序列。并且，线性递差方程包含了每个数列。

最后一步是读取所有不连续点形成的组；然后，结果就是排序后的列表。

确定等差数列的公差

公差 d 是通过将两端的差值除以元素的数量得到的。

因此，在列表迭代过程中可以计算 d。对于每个项，我都会更新读取的项数、当前最小值和最大值。

保留的数据如下

- 一个等差数列：数字 x_min、x_max、n。术语 d 在执行过程中计算。
- 对于每个间隔，我保留另一个等差数列

因此，在读取一些元素后，数据是一个包含多个等差数列的树。如果内存大小增加，则该大小是 3 的倍数。

计算曲线上 x 处的索引

假设在读取一些元素后，我得到一个包含 n = 5 个数字且 d = 3 的等差数列。
假设 x_min 等于 2，那么数字列表是

2    5    8    11   14

下一个元素的值可以是

• 在第一个元素之前
• 在最后一个元素之后
• 列表中找到的相同项
• 在一个间隔内

对于给定的每个值，等差数列都会被修改。并且这种改变对当前数据树没有影响，这就是它的优点！

欧几里得除法

x 处的索引由以下公式给出

当值 x 是整数时，我在 n 的值上加 1。

当值 x 是有理数，并且在哈希表中已经存在与 x 值的整数部分对应的等差数列时，我必须将计算传递给该等差数列。

当值 x 是有理数但没有等差数列时，我创建它并将其与 x 值的整数部分一起添加到哈希表中。

要确定 x 是整数还是有理数，我只需使用 div() 函数。此函数返回商部分和余数部分。这显然是欧几里得除法。

使用仿射方程

主要任务是计算仿射方程的系数 a 和 b，使得

y = a * x + b

对于此函数，需要两对坐标来精确确定系数。
如果是一个更复杂的方程，例如多项式，则需要更多的坐标对。

这是一个在线算法。这意味着几件事情

1. 您可以在列表的任何点开始排序计算，
2. 在每一步，所有给定的元素都已排序，
3. 在每一步，您要求算法处理一个新数字，
4. 如果您交换列表中的项，工作顺序也会交换，
5. 算法具有时间上的记忆性；如果您删除内存，算法将如同刚开始一样运行。

第一个数字

我用坐标 (k₁, p₁) 定义第一个元素。

第二个数字

我用坐标 (k₂, p₂) 定义第二个元素。 确保 p₂ 大于 p₁。如果不是，则交换它们。

由于我有两个坐标，我可以计算系数 a 和 b。它们由两个公式给出。这些公式是具有两个未知数的方程组的解。可以通过替换或更复杂的方法（高斯消元法）得到它们。

                            

第三个数字

根据算法的这个时间顺序，我用坐标 (k_i, p_i) 定义每个元素。
我必须通过从仿射方程中分离出该项来确定 k_i 的值。

剩下两个选项。

选项 1

当 k_i 得到一个整数 z 时，如果已经有 z-i 个元素，那么 p_i 将肯定被放置在该索引号 z 处。

这个结果可以用每个元素的总和、所有 i 次索引的总和以及公差来表示。

选项 2

当 k_i 得到一个有理数时，我必须将直线分成两部分。
这两部分是通过默认的 k_i 的下界和上界得到的。

第一条线从 k₁ 开始，到 E[k_i] 结束（E 是取整函数），第二条线从 E[k_i]+1 开始，到 k₂ 结束。第一条线保留在顶部，第二条线放在哈希表中。

算法改进

计算机的真正问题是什么？
换句话说，人类和计算机在排序整数方面有什么区别？

我的回答是：人有眼睛。那么，为了让计算机能够“看到”，有什么比图形表示更好的呢？

 该算法将所有点对齐在同一条垂直线上。

要对项目进行排序，首先从底部到顶部选择行中的每个指针。

最少的时间和最小的内存占用

由于时间与 n 成固定比例，内存大小也必须最小。为了达到这个最小值，我必须理解排序列表的实际困难。

一个排序列表可以有三种生成形式

• 一条连续的直线，意味着从列表中看到的最小数字到最大数字只有一个公差，
• 多条不连续的直线，这意味着存在多个斜率，它们是较小的排序直线序列，这些直线也可能存在不连续性，
• 列表中存在重复项。

所以重要的事情是首先计算不连续点和重复项的数量。完成后，一个迭代计数器将自动将所有不连续点组织成多个没有内部递归的序列，通过将每个计数添加到计数器并指示每个数字的确切位置。

当第二步完成时，我只需要进行置换就可以对整个列表进行排序。

因此，最大时间始终是 3 * n，其中 n 是输入列表中元素的数量。

除此以外，直线演变仍然存在问题。

列表渐进迭代过程中的计算

对于任何列表大小，但相对较大时，十进制基数（如向量空间有一个 10 作为其核值）有助于快速预览最近的大小。
大小小于或等于十时，秩为十。排序需要 2 次列表迭代。这已经小于
10 * log₂ (10) ≈ 3 * 10。但这相当于 10 * log₁₀ (10)。

但我们必须注意，1 的对数等于 0。这意味着当 n 是一个小数字时，算法的复杂度不是精确值，因为零的复杂度（然后是无穷大？）。

大小小于或等于一百时，秩可以是 10 或 100。如果列表中的数字很大，这可能达到 100。但是，如果列表中的数字小于 100，则秩不会增加。

大小大于或等于一千时，秩可以是 10 到 100，因为我们将始终将每个大的增长除以 10。

该方法按照这些小公式的描述工作得很好

0 < i < 10, m=0, y_i = k_i * m + r_i

y > 10, 0 < i < 100, m=10, y_i = k_i * m + r_i

y > 100, i >= 100, m'=10 * m,  y_i/10 = k_i * m/10 + r_i / 10

y_i' = k_i' * m' + r_i',  y_i' = y_i / 10, k_i' = k_i / 10,  r_i' = r_i / 10,  m' = 10 * m

每十个 k_i 的元素相加，形成 n° 0 处的元素数量。请记住，用于存储计数器的大小表是双重的；一个是在欧几里得除法的余数等于 0 时，另一个是在余数不为零时。

您将在本文中找到与此排序方法相关的源代码。

POC（概念验证）：二维网格

在图 1 中，您可以看到从左上角开始，每个单元格递增 1 的连续点。

图 1

这个点配置意味着连续元素在每个元素增加 1 时被排序。如果它不是选择的确切配置，它可能是小于或大于 i 的数字。

这两种变化分别在图 2 和图 3 中给出。

                                

图 2                                                                           图 3

我们可以得出结论，在第一次遍历最大值和最小值之后，一个带有计数的 k_i 值列表将合理地给出由其最小值、数量和公差组成的多个等差数列。

因此，对于任何混合数字列表，此算法的复杂度为 2 * n。这称为 O(n)。

但是……

因为我可以使用网格来显示排序列表只是一条斜率递增的直线，或者是一些连续的直线和特定的斜率。
这是否让人联想到 Bresenham 算法^[2]？

假设我可以根据概率建模，要么向左移动，要么向左和向上移动 1 个单位。
此外，我给其中一个命名为 A，第二个命名为 B。

例如，这个序列允许沿直线移动

BABBAAABABBAAAA

我将此序列解释为已排序列表。是否可能找到一个不同的序列，其中列表未排序，并将其转换为该列表排序后的相应序列？

示例

假设我要排序这个列表

3  9  4  7  8

对于每个连续差值，如果一个数字小于其后继数字，我称之为 A+；如果一个数字大于其后继数字，我称之为 A-。如果它们相等，我称之为 B。

A+    A-    A+    A+

有了这个例子，我得到

           3         9          4         7          8

A+      A+        A-       A+        A+

另一个例子

如上所述，未排序列表的风险是插入和差异。
所以我可以尝试用这个列表来承担这样的风险

4        42        48        55       18       37        27       71        80

                          A+       A+       A+        A-        A+       A-       A+        A+                           

结论

Brezenham 算法在具有排序数字的网格中绘制一条线。由于排序数字具有不同的斜率，这些斜率与欧几里得数相对应。在这样绘制的线中，核的大小和值表明我可以定义一个向量空间，因此列表中的元素数量必须等于等效大小的网格。

因此，在此段之后，字母让位于斜率。

 

如果我找到一个足够大的尺寸来容纳这些项，是否需要进行插入或调整大小？
如果尺寸太大，我能否仅计算位置？
如果我只能计算位置，我能否简单地迭代斜率？

我回答“是”；但是，问题在于重复项。所以我不对任何值、任何斜率进行分类，我不创建网格，我只计算重复项的数量。

使用代码

IntegerList 类处理数字列表。
列表中的数字可以从文件读取，也可以随机生成，或者通过斜率迭代。

然后，Indexer 类有助于迭代列表。因此，必须创建一个额外的类来计算每个数字项的最大值（如果列表中的每个项的数据类型都是整数）。

然后，算法需要一个类来计算坐标对（行，列），这是主要计算。

算法的最后一步是逐行逐列地迭代重复数字的字典。为了避免对网格大小进行长时间迭代，将行和列转换为具有斜率 (1,s) 且大小等于列表中元素数量的网格。

缺少一个用于重复项的 dictionary 类。

 

示例

模拟整数排序的算法示例

这是一个使用斜率对给定输入列表进行排序的示例。

为什么我会想到用斜率来对整数进行排序？

我考虑斜率有两个原因

1) 当整数很大时，整数的和可能会溢出。
事实上，如果一个有序列表的子集具有单一斜率，则元素之和与 1 的等差数列之和成正比。

2) 单一斜率并不完全接近整数列表。不同的斜率意味着列表具有不同的增量。

注释

[1] https://en.wikipedia.org/wiki/Distance (前往链接)

[2] https://en.wikipedia.org/wiki/Bresenham (前往链接)

[3] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic (前往链接)