网格排序方法

引言

我的文章旨在介绍一种“新”的整数排序方法。通常，排序算法的复杂度为 O (n * log₂ (n) )。

但这并未考虑整数属性的优势。

背景

我的一位朋友说，存在一种复杂度为 O (n) 的排序算法。

当他说这话时，我以为不可能得到这样的算法。

但是，我们从未在互联网上找到过这种算法。这就是我写这篇文章的原因，我声称它是真实的。

排序算法概述

在这里我将探讨一系列排序算法。我参考了 William H. Press, William T. Vetterling, Saul A. Teukolsky 和 Brian P. Flannery 合著的《C 语言数值食谱》（Numerical Recipes in C）（1999 年第二版）。

最重要的是，这本书的第八章展示了大多数带有 C 语言源代码和解释的排序算法。

一些实用的排序技术知识是任何优秀程序员专业知识中不可或缺的一部分。我们不希望在对如此基础的主题一无所知的情况下，将自己视为数值技术专家。

这里，更具体地，是本章将处理的任务：

1. 排序，即重新排列，将数字数组按数值顺序排列。
2. 将数组按数值顺序重新排列，同时对一个或多个附加数组进行相应的重新排列，以便保持所有数组中元素之间的对应关系。
3. 给定一个数组，为其准备一个索引表，即一个指针表，指示哪个数字数组元素在数值顺序中排在第一位，哪个排在第二位，依此类推。
4. 给定一个数组，为其准备一个排名表，即一个表，指示第一个数组元素的数值排名、第二个数组元素的数值排名等等。
5. 从数组中选择第 M 个最大元素。

对于排序 N 个元素的基本任务，最好的算法需要大约数倍于 n log₂ n 次操作。算法发明者试图将这个估计前面的常数减小到尽可能小的值。

两种最好的算法是无与伦比的 C.A.R. Hoare 发明的“快速排序”和 J.W.J. Williams 发明的“堆排序”。

对于大的 n（例如 > 1000），快速排序在大多数机器上速度快 1.5 或 2 倍；但是，它需要一些额外的内存，并且是一个中等复杂的程序。堆排序是真正的“原地排序”，程序编写起来更紧凑，因此更容易为特殊目的进行修改。

 

网格排序方法

这是介绍一种用数字对元素进行排序的思路。

网格的属性是二维值以单独顺序进行切割。
这个想法表明，对于一个数字，还有另外两个变量，并且方程只是毕达哥拉斯的距离，通常用于极坐标中的笛卡尔坐标端口。

以下段落将从一个例子开始探索这个想法，并使算法适应真实情况。

在本文档的后面，我将展示这个对包含数字的 n 个元素进行分类的算法。

示例

假设我想对这组数字进行排序

11  62  88  30  5  45  13  70  76

我可以给出这组数字的另一种排列。但是，只有一种排列是按升序排列的。

我建议用这个例子来展示有助于排序的网格。

这个网格在水平线上显示任意数字的个位数字。然后，在垂直列上，对于小于或等于 99 的数字，有 10 个可能的十位数字。

现在，要对列表进行排序，我必须从上到下，然后从左到右读取这个网格。

预期测试

预测算法的过程对于可视化所有风险并证明算法可能是正确的或存在导致结果错误的错误测试非常重要。

网格是一个模型，用于理解一个随机的数字列表只是通过相应的有序列表从一开始获得的多个排列的一个实例。

此外，填充一个没有重复的 100 个数字列表的方法是浏览网格。如果列表包含重复数字，则计算重复数字的数量很重要。然后，您将此计数器保存在每个重复数字的列表中。

改进措施

使用网格来存储数字并通过网格以有序迭代的方式进行排序是一个好主意。

然而，精确的算法并非完全是一个用于存储数字的网格。网格必须用每个数字的切割来填充。列和行的乘积必须等于列表中元素的数量。

网格可以有三维或四维；但是，对于二维网格，我必须取最近的平方，以便列表中的元素数量等于 p²。

所以对于三维网格，我必须取最近的立方，以便元素的数量等于 p³。

数学和代数表明，存在一个数值上等于三维网格的二维网格。
有了这个断言，我们可以改用二维网格来存储列表中所有要排序的项目。但是，这对于所有列表大小可能不适用。

在后一种情况下，列表简单地分为两部分；剩余部分可以放在网格的最后一个单元格中。

算法复杂度

根据网格排序方法，其复杂度为 O (n)。

首先，列表迭代一次，所以你需要“n”次循环。

其次，你有两种方式：

1. 您通过读取网格来重新创建升序（或降序）列表。复杂度随 + "b²" 变化。
2. 网格具有特殊格式：例如，两位数在网格中以 20 个 10 位整数值建模。10 个值用于处理水平线，另 10 个值用于垂直列。

第一个选项使您的算法的复杂度与 b² 相同，其中 b 是列表中每个值的切割。

第二个选项是实现网格的最佳方式。

自适应复杂性

当列表中有 N 个元素，每个元素最多有 k 位数字时，存在一个最优的网格维度数量（2、3 或更多）和每个维度的基数，在代数中也称为 Ker(F)。

连续数字之和

连续数字之和是

当我尝试在网格中定位并且有 15 个元素时，我可以创建一个 5 行 6 列的网格。这是我制作的网格

结论

这个方程是一个二次多项式。方程中的 1 表示它是一个每次新元素只有 1 次转换的递进。
如果不是 1，它可能是一个以连续距离发出每个项的数字，例如，每个项之间间隔相同的距离。

最后，两个方程给出了距离和所有元素之和以及其中最大元素（由变量 x 标识）的解。

 

因此，算法是迭代的。如果在 u 中遇到一个正方形，则用 x + u 和 u 的乘积提供的行和列绘制网格。

增量播放成本太高

尽管我可以计算每个项目的确切位置并与其他项目交换，但我无法浏览列表以找到特定项目及其放置位置。

同样，我无法将项目插入已排序的列表，因为插入的项目会移动所有后续项目。

 

关注点

在学习计算机科学时，我了解了排序算法的主要需求。

特别是，排序算法是正确的，直到我们找到一个带有特定数字列表的示例，其结果是无序列表。这是 Hoare 的逻辑和 Hoare 证明的逻辑。

然后，当我说一个新的排序算法时，主要的研究是证明这个算法将始终是有序列表的结果。为此，首先，花时间使用它并探索有机模型以确保它是一个真正的排序算法。

历史

本文的第一个版本。

几天后，我将继续寻找一种能够结合数学和算法优化的排序算法。