使用函数指针进行 Introsort（内省排序 - MetaTrader 5程序库

自省排序

这是原始 Introsort 库 的修订版 ，现在Introsort() 函数 可接受一个指向自定义比较函数的可选函数指针。

Intro 或 Introspective 排序是一种混合排序算法，可提供快速性能。它是一种基于比较的排序算法，分为三个阶段。它使用 quicksort 排序以及 heapsort 和 insertion-sort 算法。

快速排序
快速排序是一种分而治之的算法，其工作原理是在数组中选择一个枢轴元素，然后将其他元素分成两个子数组，并检查元素是大还是小。快速排序平均耗时 O(nlog(n))，最坏情况下复杂度为 O(ⁿ²)。

堆排序
堆排序算法是一种基于二元堆比较的排序方法。它是一种不稳定的排序算法，最坏情况和平均情况时间复杂度均为 O(nlog(n))，最佳情况时间复杂度为 O(n)。

插入排序
插入排序算法是一种简单的排序方法，它一次只建立一个最终排序数组。最坏情况和平均情况的时间复杂度为 O(ⁿ²)，最佳情况为 O(n)。

Introsort 算法结合了这三种算法的优点。它从快速排序开始，当递归深度超过基于开始排序的元素数量的水平时，切换到堆排序，当元素数量小于某个阈值时，切换到插入排序。

• 如果分区大小有可能超过最大深度限制，那么 Introsort 会切换到 Heapsort。
• 如果分区大小太小，Quicksort 会切换到插入排序。
• 如果分区大小低于限制且不太小，则执行简单的快速排序。

Introsort 的运行性能特别好。它是目前使用最快的比较排序算法之一，也是 C++ STL、Microsoft .NET Framework 类库、GNU 标准 C++ 库和 LLVM libc++ 库提供的 std::sort 算法的常用实现。

//+------------------------------------------------------------------+
//| Introsort|
//+------------------------------------------------------------------+
/**
 * 使用比较函数 less 对输入数组进行就地排序。
 * 您可以指定自己的比较函数。如果没有指定函数
 *，则使用升序排序。
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| 使用指向自定义 Less() 函数的指针进行内排序。
//| 自定义 Less() 函数包含两个参数和逻辑
//| 来决定它们在排序数组中的相对顺序。其原理是
//| 提供灵活性，以便 Introsort() 可以用于任何 | | | | | 排序。
//| 类型（包括用户定义的类型，如对象或结构）||......
//| 并可用于获得任何所需的排序顺序（升序、|......）。
//| 结构字段的降序或自定义顺序）。
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess);

比较函数 Less：

bool MyLessFunc(const MyStruct &x, const MyStruct &y)
  {
//--- 按 A 排序（升序）
   if(x.A < y.A) return(true);
   if(x.A > y.A) return(false);

//--- 如果 A 相同，则按 B 排序（升序）
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- 如果 B 相同，则按 C 排序（升序）
   if(x.C < y.C) return(true);
   if(x.C > y.C) return(false);

//--- 所有键都相同
   return(false);
  }


// 定义指向自定义 Less 函数的指针类型。
typedef bool (*pLess)(const MyStruct &x, const MyStruct &y);


// 使用自定义 Less 函数对结构数组进行排序。
Introsort(structArray, (pLess)MyLessFunc);