Radix 排序（最快的数字排序）- MetaTrader 5 库

基数排序通过考虑一串数字对数字数据（整数或浮点数）进行排序，其中从最低有效数字位置到最高有效数字位置逐位排序。

该算法在维基百科页面上有更好的解释https://en.wikipedia.org/wiki/Radix_sort

该算法按 LSD（最低有效数字）顺序迭代 k 个字节位置；对于每个字节位置，它迭代所有 n 个元素以按第 k 个字节对它们进行排序。

这是 LSD RadixSort 在 MQL 中的高度优化实现 使用基数 256（8 位）。这对于对具有数百万个数字的大型数组进行排序非常有用。

该实现基于 Pierre Terdiman 的基数排序，发表于 http://codercorner.com/RadixSortRevisited.htm，其中部分优化由 Michael Herf 发布于 http://stereopsis.com/radix.html 作者：Eddy L O Jansson，作者： https://github.com/eloj/radix-sorting。

该函数至少为 快3-10倍 比 MQL 的 内置 数组排序() 功能。 

该函数接受简单类型（char、uchar、short、ushort、int、uint、long、ulong、bool、color、datetime、float、double）的任意维数组作为参数。但是，排序始终应用于第一个（零）维度。 

无论 AS_SERIES 标志值如何，数组始终按升序排序。

请注意，如果数组包含的项目数少于某个阈值（当前为 128），则算法将回退到 ArraySort()。

基数排序应该是对数字数据进行排序的默认值，因为它 经营于 O(n*k) 时间。 C基于比较的排序算法（如快速排序、归并排序和堆排序）运行在 O(n * log n) 时间。因此，数组大小越大，基数排序相对越快。基数排序的缺点是它需要更多内存（临时数组）来完成其工作。

//+------------------------------------------------------------------+
//| RadixSort                                                       |
//+------------------------------------------------------------------+
//|对多维的第一维中的值进行排序    |
//|按升序排列的数值数组。                            |
//|                                                                  |
//|参数：                                                       |
//|数组[]                                                         |
//|   [in][out] ：用于排序的数字数组。                         |
//|                                                                  |
//|返回值：成功则返回 true，否则返回 false。               |
//|                                                                  |
//|注：                                                           |
//|   数组始终按升序排序，无论 |
//|   AS_SERIES 标志值的。                                   |
//|                                                                  |
//|   该函数接受简单类型的任意维数组     |
//|   （char、uchar、short、ushort、int、uint、long、ulong、bool、     |
//|   颜色、日期时间、浮点数、双精度）作为参数。  然而，      |
//|   排序始终应用于第一个（零）维度。       |
//|                                                                  |
//|性能：                                                    |
//|   这是 LSD RadixSort 的高度优化实现 |    |
//|   在 MQL 中使用基数 256（8 位）。这可能对      | 有用
//|   对包含数百万个数字的巨大数值数组进行排序。          |
//|   它比内置的 ArraySort() 至少快 3-10 倍。    |
//+------------------------------------------------------------------+
模板<类型名>布尔值基数排序(T &arr[]);//+------------------------------------------------------------------+
//| RadixSort                                                       |
//+------------------------------------------------------------------+
//|对多维的第一维中的值进行排序    |
//|按升序排列的数值数组。                            |
//|                                                                  |
//|高维数值数组的函数重载。         |
//|                                                                  |
//|参数：                                                       |
//|数组[]                                                         |
//|   [in][out] ：用于排序的数字数组。                         |
//|                                                                  |
//|返回值：成功则返回 true，否则返回 false。               |
//+------------------------------------------------------------------+
// 对二维数值数组进行排序。
模板<类型名>布尔值RadixSort(T &arr[][]);// 对三维数值数组进行排序。
模板<类型名>布尔值RadixSort(T &arr[][][]);// 对四维数值数组进行排序。
模板<类型名>布尔值RadixSort(T &arr[][][][]);//+------------------------------------------------------------------+
//| RadixSortIndices                                                 |
//+------------------------------------------------------------------+
//|按照排序顺序填充索引[] 数组      |
//|数值数组[]的值按升序排列。          |
//|                                                                  |
//|参数：                                                       |
//| array[]     ：要排序的数值数组                  |
//| Index[]   ：排序索引的数组                           |
//|                                                                  |
//|返回值：成功则返回 true，否则返回 false。               |
//+------------------------------------------------------------------+
模板<类型名>布尔值基数排序索引(常量T&arr[],整数&索引[]);//+------------------------------------------------------------------+
//| ParallelRadixSort                                               |
//+------------------------------------------------------------------+
//|该函数使用      | 同时对 array[] 和 items[] 进行排序
//|基数排序算法。排序后，items[] 数组已排序 |
//|按 array[] 的数值按升序排列。         |
//|                                                                  |
//|参数：                                                       |
//| array[]     : 使用数字键进行排序的数组                    |
//| items[]     ：根据键排序的项目数组              |
//|                                                                  |
//|返回值：成功则返回 true，否则返回 false。               |
//+------------------------------------------------------------------+
模板<类型名吨，类型名项目>布尔值ParallelRadixSort(T &arr[], TItem &items[]);

这是一个基准脚本，展示了 RadixSort() 相对于 MQL 的 ArraySort() 的速度优势：

//+------------------------------------------------------------------+
//|                                          RadixSort_benchmark.mq5 |
//|                                        版权所有 © 2018，阿姆·阿里 |
//|                             https://www.mql5.com/en/users/amrali |
//+------------------------------------------------------------------+
＃包括“基数排序.mqh”

＃定义尺寸10*1000*1000  // 1000 万
整数     arr1[大小]；整数     arr2[大小]；//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
空白 启动时()
  {//--- 准备未排序的数组。  为了（整数我=0;我<尺寸；我++）
     {
      arr1[i] =数学兰德();
      arr2[i] = arr1[i];
     }//--- ArraySort() 基准测试。  单位t1=获取刻度数();
  数组排序（arr1）；
  单位刻度1 =获取刻度数() - t1；//--- RadixSort() 基准测试。  单位t2=获取刻度数();
   基数排序(arr2);
  单位刻度2 =获取刻度数()-t2；//--- 显示结果。  打印格式（“对 %d 个整数进行排序：”， 尺寸）;
  打印格式（“ArraySort() -> %u 毫秒”, 刻度1);
  打印格式（“RadixSort() -> %u 毫秒”, 刻度2);
  打印格式（“加速系数为 %.1fx”, (双倍的) 刻度 1/刻度 2);
  打印格式（“%s”,数组比较(arr1, arr2) ? “RadixSort：排序顺序无效。”：””）；
  }//+------------------------------------------------------------------+

// 示例输出：
/*
 对 10000000 个整数进行排序：
 ArraySort() -> 953 毫秒
 RadixSort() -> 62 毫秒加速系数为 15.4 倍*/

要在旧的 mq5 或 mqh 文件中将 MQL 的 ArraySort() 替换为 RadixSort()，只需在文件顶部添加这两行：

＃包括“基数排序.mqh”
＃定义数组排序(a) 基数排序(a)

附件下载

📎 radixsort.mqh (37.14 KB)

📎 radixsort_benchmark.mq5 (3.23 KB)

📎 radixsort_validate_types.mq5 (8.19 KB)

Source: MQL5 #38763