关于快速排序，复杂度2 * N

最近开发了一种快速排序算法，其复杂度定义为2 * N（N的2倍）。

在本文中，我们不会分析排序算法本身，而只是在进行了一系列测试之后，才将其与Visual Studio中使用的排序进行比较（std :: sort函数）。正如他们所说：只有事实和最少的情感。

我们将对文本信息进行排序，因此我们将考虑单词数组。这种排列将在文学作品的基础上形成。为此，我们将这些作品的所有单词按顺序排列在此数组中。单词拆分是在没有现代化的情况下发生的，新单词开头的标志是空白。数组中的单词完全对应于文本中的单词。由于标点符号（句号，逗号等）和控制字符被写在没有空格的单词后面，因此它们是单词的一部分。单独的标点符号和控制字符被视为单独的单词。这些文件包含这些文件所在的站点的地址。地址数据是一个字。最长的单词由95个字符组成。在所考虑的作品中，有拉丁字母，西里尔字母，标点符号和控制字符。

排序的信息是任意的，没有以任何方式排序，因此，不应用特殊的排序。

比较了两种排序方法：复杂度为2 * N的新开发的排序算法和Visual Studio 2017中使用的算法（std :: sort function）。他们对排序时间和每次测试中用于此内存的每种方法的数量感兴趣。

程序是在平台-Windows x64环境-Visual Studio 2017中编写的。测试以2种配置进行。表1和2分别显示了Debug配置和Release配置中的测试结果。这些表显示了测试两种排序方法的结果。

由于计算时间的结果是浮动的（值在10％之内变化），因此对每个测试进行了一系列计算，从中选择了最小的值并将这些值放在表中。第4列和第6列中指示的时间仅是排序时间。在指定的时间内不包括其他过程（例如，读取和写入文件，数组形成）。

时间效率$$$E_t$和从内存$$$E_m$分别根据以下公式计算：

$$

$$E_t =100\frac{T_1 - T_2}{T_1}, \qquad \qquad \qquad E_m =100\frac{M_1 - M_2}{M_1},$$

哪里 $$$T_1, T_2$－分别执行Visual Studio中使用的std :: sort函数的时间步数和新的排序算法；$$$M_1, M_2$用于执行Visual Studio中使用的std :: sort函数的内存量和新的排序算法。

表1.


表2.


新开发的复杂度为2 * N的排序算法在Visual Studio 2017（函数std :: sort）中使用的算法（在时间和内存使用方面）的效率更高（由您决定）。