C# 中 Dijkstra 的 Smoothsort 通用实现
5.00/5 (2投票s)
本文描述了 Dijkstra 的 Smoothsort 在 C# 中作为通用排序算法的实现。
1. 引言
1981 年，已故的 Edsger Wybe Dijkstra 教授撰写了一篇关于他命名为 Smoothsort 的排序算法的文章，作为 Heapsort 的替代方案，用于对一维未指定数据类型的数组进行原地（即在原位）排序 (Dijkstra 1981)。Heapsort 是最快的排序算法之一：对于大小为 N 的数组，其保证执行时间为 O( N log2 N )。然而，它的一个缺点是即使原始数组接近（或完全）排序，其执行时间也相同。相比之下，Smoothsort 在任意数组上的执行时间为 O( N log2 N )，但如果数组接近排序，则平滑地过渡到 O( N )。
2. 二叉树和堆
在二叉树中，每个父节点最多有两个子节点。至少有一个子节点的节点是父节点，而没有子节点的节点是叶子。完全二叉树是没有节点只有一个子节点的树，并且树的节点满足属性：叶子数 = 内部节点数 + 1。
完美二叉树是所有叶子都在同一层级的完全树。如果倒数第二层充满节点，并且最后一层的叶子左对齐，则二叉树是完整的。这些树如图 1 和图 2 所示。
如果 h 是完美二叉树的高度（层级数），那么它总共有 (2 ^ (h + 1)) - 1 个节点，其中 2 ^ h 是叶子，(2 ^ h) - 1 是内部节点。
在使用一维数组实现二叉树时，数组的元素对应于树的节点，数组的索引对应于连接节点及其子节点（如果存在）的边。给定节点的索引，必须有一种有效的方法来确定其子节点的索引。为了在 N 元素数组中存储 N 节点二叉树，可以逐层、从上到下、从左到右遍历树，并将节点存储在连续的数组元素中。这就是众所周知的广度优先搜索顺序。
堆是满足两个属性的二叉树。从其形状来看，堆是完全二叉树。从存储元素的顺序来看，如果每个父节点中存储的值大于或等于其每个子节点中存储的值，则堆是最大堆。另一方面，在最小堆中，父节点中存储的值小于或等于其子节点中的值。叶节点空泛地满足堆的顺序属性。图 3 显示了包含素数的最大堆和最小堆的示例。
对于基于 0 的 N 元素数组 x，给定节点 x[ i ] 的索引 i 满足约束 0 <= i <= (N - 3)/2，该节点的左子节点和右子节点分别为 x[ i * 2 + 1 ] 和 x[ i * 2 + 2 ]。
3. 堆排序
J.W.J. Williams (1964) 发布了其基于 1 的数组的 Algol 堆排序实现。本节描述了堆排序的底层逻辑以及作者在 C# 中该算法的通用实现。作为 Smoothsort 的前奏，van Gasteren、Dijkstra 和 Feijen (1981) 给出了堆排序执行前后的正式规范，如图 4 中 Dijkstra 的手写所示。
换句话说，前置条件规定，对于基于 0 的 N 元素整数数组 m，数组包含任意整数集合（即一个包），在堆排序执行后，后置条件规定，对于所有满足条件 0 <= i < j 和 1 <= j < N 的索引 i 和 j，m 的元素按排序顺序排列。当然，该规范对任何类型的数组元素都有效。接下来描述整数元素数组的堆排序实现。
堆排序的逻辑很简单。假设数组需要按升序排序，重新排列元素以创建最大堆，将最大元素放在其正确位置，从第一个元素到倒数第二个元素恢复最大堆属性，并重复该过程直到没有更多元素需要处理。排序结果是一个最小堆。这种口头描述的实现如下。C# 代码改编自作者编写的 C++ 代码 (Orejel 2003)，并假定它存在于控制台应用程序中的 static 类中。
/// <summary>Apply Heapsort to an {int} array.
/// </summary>
/// <param name="m">Array reference.</param>
/// <param name="n">Index of LAST element of {m}.</param>
/// <remarks>
/// The sorting is done in ascending order.
/// The initial root element is at the midpoint of {m}.
/// </remarks>
static void HeapSort( int[] m )
{
int N = m.Length;
BuildHeap( m, N >> 1, N - 1 );
SortNodes( m, N - 1 );
}// HeapSort
正如函数 HeapSort 的 remarks 部分所述，构建最大堆的过程从数组的中点开始。一旦堆建成，节点就可以排序。
图 5a 显示了函数 BuildHeap 的尾递归实现。该函数是尾递归的，因为在递归调用返回后无需执行任何操作。因此，图 5b 显示了一个迭代版本，其中尾递归调用已被其等效代码替换。假设存在用于显示数组和树的适当功能（稍后处理），图 6 显示了一个示例数组和执行 BuildHeap 后生成的树结构。
函数 ReheapDown 是 BuildHeap 的主力。只要有节点（即数组元素）需要检查，如果父节点大于其子节点的最大值，则交换节点，并以最大子节点作为新父节点继续该过程。该函数也是尾递归的，其注释指示如何使该函数迭代：取消注释标签，注释掉递归调用，并取消注释替换调用的代码。
/// <summary>Move a parent node down the heap until the max-heap property is restored.
/// </summary>
/// <param name="m">Array reference.</param>
/// <param name="parent">Index of a parent element in {m}.</param>
/// <param name="bottom">Index of last element in {m} to consider.
/// </param>
static void ReheapDown( int[] m, int parent, int bottom )
{
int maxChild, leftChild;
// L0: // Target label for {goto} statement.
leftChild = ( parent << 1 ) + 1;
if ( leftChild <= bottom )
{
maxChild = MaxChildIndex( m, leftChild, bottom );
if ( m[ parent ] < m[ maxChild ] )
{
Swap( ref m[ parent ], ref m[ maxChild ] );
ReheapDown( m, maxChild, bottom );
// Uncomment the label {L0}, comment out the tail-recursive call,
// and uncomment the following line.
//
// parent = maxChild; goto L0;
}
}
}// ReheapDown
ReheapDown 调用的两个辅助函数是 MaxChildIndex（用于确定最大子节点的索引）和 Swap（用于执行数组元素的交换）。请注意，将参数按引用传递给 Swap 至关重要。
/// <summary>Determine the index of the maximum child of a parent.
/// </summary>
/// <param name="m">Array reference.</param>
/// <param name="leftChild">Index of left child.</param>
/// <param name="bottom">Index of last element in {m} to consider.</param>
/// <returns>Index of the maximum child.
/// </returns>
static int MaxChildIndex( int[] m, int leftChild, int bottom )
{
int rightChild = leftChild + 1; // Index of right child.
return ( leftChild == bottom )
? leftChild
: ( m[ leftChild ] > m[ rightChild ] )
? leftChild
: rightChild;
}// MaxChildIndex
/// <summary>Interchange the values of two {int} variables.
/// </summary>
/// <param name="x">Reference to first variable.</param>
/// <param name="y"> Reference to second variable.</param>
/// <remarks>
/// The arguments to this function MUST be passed by
/// reference in order to properly alter them.
/// </remarks>
static void Swap( ref int x, ref int y )
{
int t = x; x = y; y = t;
}// Swap
最后一个要编写的函数是 SortNodes。它将最大堆元素放置在数组末尾的正确位置，调用 ReheapDown 以从第一个元素到倒数第二个元素恢复最大堆属性，最后递归调用自身。正如可能已经预料到的，SortNodes 也是尾递归的，代码中的注释指示如何使其迭代。
/// <summary>Arrange the elements of an array in ascending order.
/// </summary>
/// <param name="m">Array reference.</param>
/// <param name="bottom">Index of last element in {a} to consider.
/// </param>
static void SortNodes( int[] m, int bottom )
{
// L0: // Target label for {goto} statement.
if ( bottom > 0 )
{
// Put { m[ 0 ] } in its proper place.
Swap( ref m[ 0 ], ref m[ bottom-- ] );
ReheapDown( m, 0, bottom );
SortNodes( m, bottom );
// Uncomment the label {L0}, comment out the tail-recursive call,
// and uncomment the following line.
//
// goto L0; {bottom} already decreased after call to {Swap}.
}
}// SortNodes
图 7 显示了 SortNodes 执行结束时的最小堆树结构和数组。最后一点，如果对排序后的同一数组调用 HeapSort，它将执行与数组未排序时相同的操作。至此，关于整数值数组上的堆排序的描述结束。
4. 通用堆排序
本节不是对第 3 节代码的重复。首先，代码是通用的，它可以处理满足非常简单约束的任意数据类型的数组元素。其次，它使用了一些（将在使用时描述的）对排序算法自然通用的库函数。第三，代码是迭代的，不使用标签和 goto 语句。因此，本节是对未来事物的预演，即 GenericSmoothSort。
为了处理任意数据类型，实现堆排序的函数必须具有泛型类型参数 <T>，并且该类型必须受 IComparable 接口的约束。GenericHeapSort 命名空间中的类名和函数签名如图 8 所示。第 3 节中的函数名已保留。有一个 using 语句指示代码引用了一个名为 UtilSortLib 的库，该库实现了排序算法通用的函数。特别地，请注意 HS 类不包含 Swap 函数，因为它是任何排序算法中的基本操作，因此它属于该库。
UtilSortLib 库包含三个类：一个用于 static 变量，两个用于函数：TypedUfn<T>（“类型化实用函数”的缩写）和 UntypedUfn（“非类型化实用函数”的缩写）。大多数函数都与在控制台上显示结果有关，并在第 7 节中描述，但有些将在使用时描述。
在每个函数名称后指定类型参数允许它们将泛型数组作为参数，并且 where 约束指示参数必须可比较。这意味着数组元素的数据类型必须有一个 CompareTo 函数。根据 Microsoft 文档，所有可排序或可比较的类型（即所有 C# 基本数据类型）都有这样的函数。但是，正如稍后将演示的，任意数据类型必须显式实现比较函数。
除了在控制台上显示两个实用程序全局变量（交换操作计数和比较计数）以及树形数组（通过调用 TypedUfn<T>.DisplayTree）之外，函数 HeapSort<T> 是第 3 节中对应函数的泛型版本。
/// <summary>Implement the Heapsort algorithm over a generic array.
/// </summary>
/// <typeparam name="T">Type of the array elements.</typeparam>
/// <param name="arr">Reference to a generic array to be sorted in ascending order.
/// </param>
public static void HeapSort<T>( T[] arr ) where T : IComparable<T>
{
int n = arr.Length - 1;
BuildHeap( arr, n >> 1, n );
Console.Write( "After {BuildHeap}: " );
Console.WriteLine( "{0} swaps; {1} comparisons", Uvar.swapCount, Uvar.compCount );
TypedUfn<T>.DisplayTree( "after {BuildHeap}", arr );
SortNodes( arr, n );
}// HeapSort
函数 BuildHeap<T> 和 ReheapDown<T> 都是迭代的，并且不使用目标标签和相应的 goto 语句。但是，请注意 ReheapDown 函数中 break 语句的使用。没有它，函数中的 while 循环将不会终止。这说明了消除实现循环的标签和 goto 语句并非易事。
/// <summary>Move down the heap the contents of a parent node to its right position
/// in the ascending order of elements in an array.
/// </summary>
/// <typeparam name="T">Type of the array elements.</typeparam>
/// <param name="arr">Reference to a generic array containing the heap nodes.</param>
/// <param name="parent">Index into {arr} of a parent node.</param>
/// <param name="bottom">Index into {arr} of the bottom-most node.
/// <remarks>
/// On the initial call, {bottom} must index the LAST element of {arr}.
/// </remarks>
private static void ReheapDown<T>( T[] arr, int parent, int bottom )
where T : IComparable<T>
{
int maxChild, leftChild;
leftChild = ( parent << 1 ) + 1;
while ( leftChild <= bottom )
{
maxChild = MaxChildIndex( arr, leftChild, bottom );
int cmp = arr[ parent ].CompareTo( arr[ maxChild ] );
if ( UntypedUfn.IsLT( cmp ) )
{
TypedUfn<T>.Swap( "ReheapDown", arr, parent, maxChild );
parent = maxChild;
leftChild = ( parent << 1 ) + 1;
}
else // UntypedUfn.IsGE( cmp )
{
break;
}
}
}// ReheapDown
函数 ReheapDown<T> 在泛型数据类型的实例上调用 CompareTo 函数。根据 Microsoft 文档中的定义，如果 x 和 y 是相同数据类型的实例，则调用 x.CompareTo( y ) 返回一个整数值，如果 x 小于 y，则小于 0；如果 x 等于 y，则为 0；如果 x 大于 y，则大于 0。非类型化实用函数 UntypedUfn.IsLT 如果其参数小于 0 则返回 true（else 部分注释中的断言表明，给定相同的参数，函数 UntypedUfn.IsGE 将返回 true）。
/// <summary>Determine whether the result from a {CompareTo} function
/// is "less than".
/// </summary>
/// <param name="cmp">Result from a call to a {CompareTo} function.</param>
/// <returns>Whether or not {cmp} meets the requirement.
/// </returns>
public static bool IsLT( int cmp )
{
++Uvar.cmpCount;
return cmp < 0;
}// IsLT
还有其他非类型化比较函数（IsLE、IsEQ、IsGT），其含义显而易见。所有这些函数都会增加执行的比较全局计数。
在 if 子句中，ReheapDown 调用 TypedUfn<T>.Swap 的两个版本之一，该版本检查从枚举设置的全局变量的值以控制控制台输出。
// Enumeration to control console output
public enum OutMode { quiet, verbose }
/// <summary>Swap two generic array elements.
/// </summary>
/// <param name="fName">Name of function calling {Swap}.</param>
/// <param name="m">Reference to a generic array.</param>
/// <param name="i">Index of element to be swapped.</param>
/// <param name="j">Index of element to be swapped.
/// </param>
public static void Swap( string fName, T[] m, int i, int j )
{
++Uvar.swapCount;
if ( Uvar.OutMode == OutMode.verbose )
{
TypedUfn<T>.DisplayArray( "", m );
DisplaySwap( fName, i, m[ i ], j, m[ j ] );
}
Swap( ref m[ i ], ref m[ j ] );
}// Swap
请注意，函数 Swap 没有类型参数，因为它位于类型化类中。此函数增加全局交换操作计数，当 Uvar.outMode 等于 OutMode.verbose 时，它调用类型化函数 DisplayArray 和非类型化函数 DisplaySwap。最后，实际的交换由两参数函数 Swap 执行。
/// <summary>Swap two generic arguments passed by reference.
/// </summary>
/// <param name="x">First argument to be swapped.</param>
/// <param name="y">Second argument to be swapped.
/// </param>
public static void Swap( ref T x, ref T y )
{
T tmp = x;
x = y; y = tmp;
}// Swap
函数 MaxChildIndex<T> 的逻辑与第 3 节相同，但它调用 CompareTo 函数和实用函数 UntypedUfn.IsGT。函数 SortNodes<T> 是其尾递归对应项的泛型迭代版本。
/// <summary>Determine the index into {arr} of the maximum child of a parent
/// node in the heap.
/// </summary>
/// <typeparam name="T">Type of the array elements.</typeparam>
/// <param name="arr">Reference to a generic array containing the heap nodes.</param>
/// <param name="leftChild">Index into {arr} of the left child of a parent node.</param>
/// <param name="bottom">Index into {arr} of the bottom-most node.</param>
/// <returns>The index of the maximum child.
/// </returns>
private static int MaxChildIndex<T>( T[] arr, int leftChild, int bottom )
where T : IComparable<T>
{
int rightChild = leftChild + 1;
return ( leftChild == bottom )
? leftChild
: UntypedUfn.IsGT( arr[ leftChild ].CompareTo( arr[ rightChild ] ) )
? leftChild
: rightChild;
}// MaxChildIndex
/// <summary>Sort in ascending order the nodes of a heap stored in an array.
/// </summary>
/// <typeparam name="T">Type of the array elements.</typeparam>
/// <param name="arr">Reference to a generic array containing the heap nodes.</param>
/// <param name="bottom">Index into {arr} of the bottom-most heap node.
/// <remarks>
/// On the initial call, {bottom} must index the LAST element of {arr}.
/// </remarks>
private static void SortNodes<T>( T[] arr, int bottom ) where T : IComparable<T>
{
while ( bottom > 0 )
{
// Put { arr[ 0 ] } in its proper place.
TypedUfn<T>.Swap( " SortNodes", arr, 0, bottom-- );
ReheapDown( arr, 0, bottom );
}
}// SortNodes
为了比较，通用 HeapSort 的执行将与通用 SmoothSort 的执行并行说明。但是，对于好奇的读者，图 9 显示了 HeapSort 对按逆序（降序）排列的前 25 个素数数组的结果。请注意，函数 BuildHeap 不执行任何交换，因为原始数组已经是最大堆。
为了强调堆排序对于 N 元素数组具有相同的时间复杂度，无论它是否近似或完全排序，当在图 9 中使用结果数组运行时，函数 BuildHeap 执行 21 次交换和 42 次比较，排序结束时的总数为 108 次交换和 167 次比较。
由于函数 HeapSort<T> 是泛型的，图 10 显示了它在从字符 string 创建的字符数组上执行的结果。
5. 通用 Smoothsort
Edsger W. Dijkstra (EWD796a 1981) 提出的这种排序算法作为堆排序的替代方案，已有多人评论。在 Stack Overflow 网站上，有人指出该算法不稳定（一个借用自电气工程和控制理论的大词），并且稳定性比原地排序更可取。回想一下，不稳定排序不保留相同元素的顺序（对于排序目的来说不是什么大问题），并且快速排序（另一个优秀的排序算法）也不稳定。因此，原地排序以及当 N 元素数组接近或完全排序时从到执行时间的平滑过渡是 Smoothsort 的出色特性。另一方面，有人说关于该算法的资源非常稀缺，而且可用的资源非常难以理解。正如本节将演示的，Dijkstra 对 Smoothsort 的设计和实现不难理解。
作者至少知道一个 C++ 中的 Smoothsort 实现 (Schwarz 2011)。在重述其设计背后的数学原理（其中两幅图中列奥纳多子树的长度存在一些错误）后，Schwarz 以一个指向他自己的 Smoothsort 实现的链接结束了文章，该实现与 Dijkstra 的代码没有任何共同之处。实现 Dijkstra Smoothsort 算法的 GenericSmoothSort 命名空间中的类名、全局变量名和函数签名如图 11 所示。
Dijkstra 的代码是用后来他与 W.H.J. Feijen 在他们的著作《编程方法》(Dijkstra and Feijen 1988) 中使用的形式主义编写的。除了函数 Up 和 Down，本节中的代码几乎是 Dijkstra 代码到 C# 的直接翻译。C# 代码右侧的注释复制了原始代码。
/// <summary>Generic implementation of Professor Dijkstra's Smoothsort
/// (see EWD796a in the E.W. Dijkstra Archive).
/// </summary>
/// <typeparam name="T">Type of array {m} elements.</typeparam>
/// <param name="m">Reference to a generic array to be sorted.</param>
/// <remarks>
/// The comments to the right of the C# code reproduce the original code
/// in the EWD796a reference.
/// The '^' character denotes the logical "and" operator.
/// </remarks>
public static void SmoothSort<T>( T[] m ) where T : IComparable<T>
// smoothsort:
{
// |[
N = m.Length;
r1 = b1 = c1 = -1;
q = 1; r = 0; p = b = c = 1; // ; q := 1; r := 0; p, b, c := 1, 1, 1
// P3' && P4' // {invariant: P3' ^ P4'}
while ( q != N ) // ; do q != N
{
r1 = r; // -> r1 := r
if ( ( p % 8 ) == 3 ) // ; if p mod 8 = 3
{
b1 = b; c1 = c; // -> b1, c1 := b, c
Sift( m ); // ; sift
p = ( p + 1 ) >> 2; // ; p := (p + 1)/4
Up( ref b, ref c ); // ; up
Up( ref b, ref c ); // ; up
}
else if ( ( p % 4 ) == 1 ) // [] p mod 4 = 1
{
if ( ( q + c ) < N ) // -> if q + c < N
{
b1 = b; c1 = c; // -> b1, c1 := b, c
Sift( m ); // ; sift
}
else if ( ( q + c ) >= N ) // [] q + c >= N
{
Trinkle( m ); // -> trinkle
} // fi
Down( ref b, ref c ); p <<= 1; // ; down; p := 2 * p
while ( b != 1 ) // ; do b != 1
{
Down( ref b, ref c ); p <<= 1; // -> down; p := 2 * p
} // od
++p; // ; p := p + 1
} // fi;
++q; ++r; // q := q + 1; r := r + 1
} // od {P3' ^ P4'};
// P3' && P4'
r1 = r; Trinkle( m ); // r1 := r; trinkle {invariant: P3 ^ P4}
// P3 && P4
while ( q != 1 ) // ; do q != 1
{
--q; // -> q := q - 1
if ( b == 1 ) // ; if b = 1
{
--r; --p; // -> r := r - 1; p := p - 1
while ( UntypedUfn.IsEven( p ) ) // ; do even(p)
{
p >>= 1; // -> p := p/2
Up( ref b, ref c ); // ; up
} // od
}
else if ( b >= 3 ) // [] b >= 3
{
--p; r = r - b + c; // -> p := p - 1; r := r - b + c
if ( p == 0 ) // ; if p = 0
{
// -> skip
}
else if ( p > 0 ) // [] p > 0
{
SemiTrinkle( m ); // -> semitrinkle
} // fi
Down( ref b, ref c ); // ; down
p = ( p << 1 ) + 1; // ; p := 2*p + 1
r = r + c; // ; r := r + c
SemiTrinkle( m ); // ; semitrinkle
Down( ref b, ref c ); // ; down
p = ( p << 1 ) + 1; // ; p := 2*p + 1
} // fi
} // od
}// SmoothSort // ]|
本文不是重述 Dijkstra 的 Smoothsort 设计背后数学原理的地方。建议读者参考他的原始描述 (Dijkstra 1981)。为了完整性，图 12 中复制了函数 SmoothSort 中 while 循环维护的一些术语和不变量。
Smoothsort 的美妙之处在于在第一个 while 循环中重新排列数组元素以创建 Leonardo 树。Leonardo 树是大小为 Leonardo 数的二叉树，这些 Leonardo 数是可用的伸展长度（参见 EWD796a – 3），由以下递推关系定义。
$LP(0) = LP(1) = 1$
$LP(n+2)=LP(n+1)+LP(n)+1$
引用 Dijkstra 的话，“为了反复计算伸展长度，我们为每个伸展长度 b 引入其‘伴侣’ c，即我们保持”
$(En:n\geq 0:b=LP(n) and c=LP(n-1)$
换句话说，存在一个正整数 n，使得 b 和 c 分别是连续的 Leonardo 数 LP( n ) 和 LP( n - 1 )。
在基于 0 的数组中，大小为 LP( n ) 个节点的 Leonardo 树的根位于索引 LP( n ) – 1 处，其左子节点位于索引 LP( n – 1 ) – 1 处，其右子节点位于索引 LP( n ) – 2 处。因此，Dijkstra 对 Leonardo 数的选择保证了每个父节点始终有两个子节点（参见 EWD796a – 7，备注 2）。作为说明，图 13 和图 14 显示了通过对最初按降序排列的前 25 个素数数组执行 SmoothSort 获得的控制台输出摘录。数组声明和对 SmoothSort 的调用如下。
int[] a1 = { 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23,
19, 17, 13, 11, 7, 5, 3, 2 },
TypedUfn<int>.SortArray( "Smooth Sort a1 (worst case)",
SmS.SmoothSort<int>, a1 ); // Worst case, O( N log2 N ) time.
图 13 中所示的莱昂纳多树是无效的，因为两个子节点超出了它们的父节点。树的“无效”和“有效”名称对应于 Dijkstra 对“可疑”和“可信”伸展（即连续数组元素序列）的名称（参见 EWD796a – 6）。图 14 显示了交换 25 后数组和莱昂纳多树的状态。
函数 SmoothSort 中的第一个 while 循环从左到右扫描数组，第二个 while 循环从右到左扫描数组。图 15 说明了在第 30 次交换后数组和莱昂纳多树的状态。
本节的其余部分提供了实现 Smoothsort 的附加函数到 C# 的翻译。其 Intellisense 注释中的 summary 部分复制了 Dijkstra 的描述。
函数 Up 和 Down 分别包含原始代码中的函数 up/up1 和 down/down1。这两个函数中的临时变量是必需的，因为与 Algol 编程语言一样，原始函数对变量使用多重赋值，而 C# 不支持这种操作。
/// <summary>Function to subsume the {up} and {up1} functions.
/// </summary>
/// <param name="b">Reference to variable {b} or {b1} in the original code.</param>
/// <param name="c">Reference to variable {c} or {c1} in the original code.
/// </param>
/// <remarks>In the original code,
/// up: b, c := b + c + 1, b
/// up1: b1, c1 := b1 + c1 + 1, b1 .
/// The variables {tmp1} and {tmp2} are necessary because, unlike Algol,
/// C# does not support multiple assignment.
/// </remarks>
private static void Up( ref int b, ref int c )
{
int tmp1 = b + c + 1, tmp2 = b;
b = tmp1; c = tmp2;
}// Up
/// <summary>Function to subsume the {down} and {down1} functions.
/// </summary>
/// <param name="b">Reference to variable {b} or {b1} in the original code.</param>
/// <param name="c">Reference to variable {c} or {c1} in the original code.
/// </param>
/// <remarks>In the original code,
/// down: b, c := c, b - c - 1
/// down1: b1, c1 := c1, b1 - c1 - 1 .
/// The variables {tmp1} and {tmp2} are necessary because, unlike Algol,
/// C# does not support multiple assignment.
/// </remarks>
private static void Down( ref int b, ref int c )
{
int tmp1 = c, tmp2 = b - c - 1;
b = tmp1; c = tmp2;
}// Down
函数 Sift、Trinkle 和 SemiTrinkle 实现了 HeapSort 中“向下堆化”操作的等价功能。
/// <summary>Sift the root of a "stretch".
/// </summary>
/// <typeparam name="T">Type of array {m} elements.</typeparam>
/// <param name="m">Reference to the array in which the sift takes place.
/// </param>
/// <remarks>Routine {sift} is applied to the root { m(r1) } of a stretch of
/// length {b1}, of which {c1} is the "companion" (cf. EWD796a - 9).
/// The calls to function {DisplayState} are NOT in the original code.
/// </remarks>
private static void Sift<T>( T[] m ) where T : IComparable<T>
{ // sift:
while ( b1 >= 3 ) // do b1 >= 3
{
int r2 = r1 - b1 + c1, cmp; // |[ r2: int; r2 := r1 - b1 + c1
cmp = m[ r2 ].CompareTo( m[ r1 - 1 ] );
if ( UntypedUfn.IsGE( cmp ) ) // ; if m(r2) >= m(r1 - 1)
{
// -> skip
}
else if ( UntypedUfn.IsLE( cmp ) ) // [] m(r2) <= m(r1 - 1)
{
r2 = r1 - 1; // -> r2 := r1 - 1
Down( ref b1, ref c1 ); // ; down1
} // fi
cmp = m[ r1 ].CompareTo( m[ r2 ] );
if ( UntypedUfn.IsGE( cmp ) ) // ; if m(r1) >= m(r2)
{
b1 = 1; // -> b1 := 1
}
else if ( UntypedUfn.IsLT( cmp ) ) // [] m(r1) < m(r2)
{
TypedUfn<T>.Swap( " Sift",
m, r1, r2 ); // -> m:swap(r1, r2)
DisplayState( m );
r1 = r2; // ; r1 := r2
Down( ref b1, ref c1 ); // ; down1
} // fi
// ]|
} // od
}// Sift
/// <summary>Synonym of "trickle". To flow down by drops.
/// </summary>
/// <typeparam name="T">Type of array {m} elements.</typeparam>
/// <param name="m">The array in which the trinkle takes place.
/// </param>
/// <remarks>Routine {trinkle} is applied to the root { m(r1) } of the last stretch of
/// the standard concatenation represented by the triple (p, b, c); this
/// representation need not be normalized (cf. EWD796a - 9).
/// The calls to function {DisplayState} are NOT in the original code.
/// </remarks>
private static void Trinkle<T>( T[] m ) where T : IComparable<T>
{ // trinkle:
int p1 = p; b1 = b; c1 = c; // |[ p1: int; p1, b1, c1 := p, b, c
while ( p1 > 0 ) // ; do p1 > 0 ->
{
int r3; // |[ r3: int
while ( UntypedUfn.IsEven( p1 ) ) // ; do even(p1)
{
p1 >>= 1; // -> p1 := p1/2
Up( ref b1, ref c1 ); // ; up1
} // od
r3 = r1 - b1; // ; r3 := r1 - b1
int cmp;
if ( p1 == 1 // ; if p1 = 1
|| // cor
UntypedUfn.IsLE(
(cmp
= m[ r3 ].CompareTo( m[ r1 ] )) ) ) // m(r3) <= m(r1)
{
p1 = 0; // -> p1 := 0
}
else if ( p1 > 1 && UntypedUfn.IsGT( cmp ) ) // [] p1 > 1 cand m(r3) > m(r1)
{
--p1; // -> p1 := p1 - 1
if ( b1 == 1 ) // ; if b1 = 1
{
TypedUfn<T>.Swap( " Trinkle",
m, r1, r3 ); // -> m:swap(r1, r3)
DisplayState( m );
r1 = r3; // ; r1 := r3
}
else if ( b1 >= 3 ) // [] b1 >= 3
{
int r2 = r1 - b1 + c1; // |[ r2: int; r2 := r1 - b1 + c1
cmp
= m[ r2 ].CompareTo( m[ r1 - 1 ] );
if ( UntypedUfn.IsGE( cmp ) ) // ; if m(r2) >= m(r1 - 1)
{
// -> skip
}
else if ( UntypedUfn.IsLE( cmp ) ) // [] m(r2) <= m(r1 - 1 )
{
r2 = r1 - 1; // -> r2 := r1 - 1
Down( ref b1, ref c1 ); // ; down1
p1 <<= 1; // ; p1 := 2 * p1
} // fi
cmp = m[ r3 ].CompareTo( m[ r2 ] );
if ( UntypedUfn.IsGE( cmp ) ) // ; if m(r3) >= m(r2)
{
TypedUfn<T>.Swap( " Trinkle",
m, r1, r3 ); // -> m:swap(r1, r3)
DisplayState( m );
r1 = r3; // ; r1 := r3
}
else if ( UntypedUfn.IsLE( cmp ) ) // [] m(r3) <= m(r2)
{
TypedUfn<T>.Swap( " Trinkle",
m, r1, r2 ); // -> m:swap(r1,r2)
DisplayState( m );
r1 = r2; // ; r1 := r2
Down( ref b1, ref c1 ); // ; down1
p1 = 0; // ; p1 := 0
} // fi
} // ]|
} // fi
} // ]|
// od
// ]|
Sift( m ); // ; sift
}// Trinkle
/// <summary>Synonym of semi-trickle.
/// </summary>
/// <typeparam name="T">Type of array {m} elements.</typeparam>
/// <param name="m">Reference to the array in which the trinkle takes place.
/// </param>
/// <remarks>Routine {semitrinkle} is applied to the root { m(r) } of a
/// stretch of length {c} which is preceded by the nonempty
/// standard concatenation represented by the triple (p, b, c);
/// again this representation is not necessarily normalized
/// (cf. EWD796a - 9).
/// The call to function {DisplayState} is NOT in the original code.
/// </remarks>
private static void SemiTrinkle<T>( T[] m ) where T : IComparable<T>
{ // semitrinkle:
r1 = r - c; // r1 := r - c
int cmp = m[ r1 ].CompareTo( m[ r ] );
if ( UntypedUfn.IsLE( cmp ) ) // ; if m(r1) <= m(r)
{
// -> skip
}
else if ( UntypedUfn.IsGT( cmp ) ) // [] m(r1) > m(r)
{
TypedUfn<T>.Swap( "SemiTrinkle",
m, r, r1 ); // -> m:swap(r, r1)
DisplayState( m );
Trinkle( m ); // ; trinkle
} // fi
}// SemiTrinkle
Dijkstra 的原始代码中没有包含两个函数。它们用于在控制台上显示 SmoothSort 的状态变量（b、c、p、r、q），并且如图 13、14 和 15 所示，显示了排序数组中出现的莱昂纳多树的信息。
// Functions NOT defined in the original code.
/// <summary>Display on the console the state of the global variables,
/// of the array being sorted, and the Leonardo tree(s).
/// </summary>
/// <typeparam name="T">Type of array {m} elements.</typeparam>
/// <param name="m">Reference to the array in which the sorting is taking place.
/// </param>
private static void DisplayState<T>( T[] m ) where T : IComparable<T>
{
LPtree<T> tree = new LPtree<T>( m, b, c );
if ( Uvar.outMode == OutMode.verbose )
{
DisplayVars();
}
tree.TrySaveAndDisplay();
}// DisplayState
/// <summary>Display on the console the global variables {p, b, c, r, q}.
/// </summary>
private static void DisplayVars()
{
int idx, k = LPfn.InvLP( b );
string fmtStr1 = Uvar.elementFormat, fmtStr2 = "LP({0})";
UntypedUfn.SkipOB( out idx ); UntypedUfn.DisplayStr( " ", ref idx, b );
// idx == b
Console.Write( fmtStr1, "b" );
Console.WriteLine( fmtStr2, k );
UntypedUfn.SkipOB( out idx ); UntypedUfn.DisplayStr( " ", ref idx, c );
// idx == c
Console.Write( fmtStr1, "c" );
Console.WriteLine( fmtStr2, k - 1 );
Console.WriteLine( "p: {0} ({1})", p, UntypedUfn.ToBinaryStr( p ) );
UntypedUfn.SkipOB( out idx ); UntypedUfn.DisplayStr( " ", ref idx, r );
// idx == r
Console.Write( fmtStr1, "r" );
Console.WriteLine( fmtStr1, "q" );
Console.WriteLine();
}// DisplayVars
作为本节的最后一个例子，图 16a 和 16b 显示了一个包含前 50 个素数（最初按降序排列）的数组在第 45 次交换之前和之后的状态。
6. Smoothsort 与 Heapsort 的比较
对于任何按升序排序的算法来说，初始按降序排列的数组代表最坏情况。在前 50 个素数的示例中，终止时，SmoothSort 执行了 223 次交换和 1323 次比较，而 HeapSort 执行了 207 次交换和 379 次比较。图 17 显示了五个示例整数数组的声明、对 SmoothSort 和 HeapSort 的调用模板，以及每个情况下的交换次数和比较次数表。显然，当原始数组接近或完全排序时，SmoothSort 优于 HeapSort。
7. 实用函数
库 UtilSortLib 包含排序算法常用的类型化和非类型化函数。类型化函数位于 TypedUfn<T> 类中，非类型化函数位于 UntypedUfn 类中。最重要的类型化函数是用于使用对特定排序函数的引用对数组进行排序的函数，该函数的签名必须符合委托规范。
/// <summary>Delegate (i.e., function reference) for sorting functions.
/// </summary>
/// <param name="arr">Reference to a generic array to be sorted.
/// </param>
public delegate void SortingFunction( T[] arr );
/// <summary>Function to invoke a sorting function, displaying on the console
/// the sorting process (if so desired by the caller).
/// </summary>
/// <param name="msg">Message to display.</param>
/// <param name="SortFn">Reference (i.e., pointer) to a sorting function.</param>
/// <param name="arr">Reference to a generic array to be sorted.</param>
/// <param name="mode">Mode for console output.</param>
/// <param name="dispTree">Whether or not to display {arr} as a binary tree.
/// </param>
public static void SortArray( string msg, SortingFunction SortFn, T[] arr,
OutMode mode = OutMode.quiet, bool dispTree = false )
{
SetVariables( arr, mode );
Console.WriteLine();
if ( ! String.IsNullOrEmpty( msg ) )
{
Console.WriteLine( "{0}\n", msg );
}
if ( dispTree )
{
TypedUfn<T>.DisplayTree( "before " + msg, arr );
}
DisplayArray( "Original", arr ); Console.WriteLine();
SortFn( arr ); // Apply the sorting function to the array.
DisplayArray( "Sorted", arr );
if ( dispTree )
{
TypedUfn<T>.DisplayTree( "after " + msg, arr );
}
Console.WriteLine( "\n{0} swaps; {1} comparisons",
Uvar.swapCount, Uvar.compCount );
Console.WriteLine();
} // SortArray
调用函数 SetVariables 以初始化用于排序过程中显示目的的全局变量。如所示，此函数必须在首次调用 DisplayArray 和/或 DisplayTree 函数之前调用。
/// <summary>Set the global variables in class {Uvar}.
/// </summary>
/// <param name="arr">Generic array.</param>
/// <param name="mode">Mode for console output.
/// </param>
/// <remarks>This function MUST be called before calling functions
/// {DisplayArray} {DisplayIndices} and {DisplayTree} for
/// the first time.
/// </remarks>
public static void SetVariables( T[] arr, OutMode mode )
{
Uvar.elementWidth = MaxElementWidth( arr );
// Generate the element-format {string} to be used by
// functions {DisplayArray} and {DisplayTree}.
Uvar.elementFormat
= "{0"
+ String.Format( ",{0}", Uvar.elementWidth )
+ "} ";
Uvar.elementParams
= String.Format( "\nElement width: {0}, element format string: '{1}'",
Uvar.elementWidth, Uvar.elementFormat );
Uvar.swapCount = 0;
Uvar.compCount = 0;
Uvar.outMode = mode;
}// SetVariables
由于排序函数期望处理泛型数组，因此调用函数 MaxElementWidth 来确定用于显示时正确格式化的最大数组元素宽度。
/// <summary>Compute the maximum width of array elements for display purposes.
/// </summary>
/// <param name="arr">Reference to a generic array.
/// </param>
private static int MaxElementWidth( T[] arr )
{
int maxWidth = int.MinValue;
if ( arr[ 0 ] is char )
{
maxWidth = 3; // Account for single quotes.
}
else
{
int N = arr.Length, width = 0;
for ( int i = 0; i < N; ++i )
{
string str = arr[ i ].ToString();
width = str.Length;
if ( width > maxWidth )
{
maxWidth = width;
}
}
if ( arr[ 0 ] is string )
{
maxWidth += 2; // Account for double quotes.
}
}
return maxWidth;
}// MaxElementWidth
Swap 函数有两个版本。第一个版本只接收两个引用参数并交换它们。第二个版本通常应该在需要将交换操作显示在控制台时调用，如图 13、14 和 15 所示。
/// <summary>Swap two generic arguments passed by reference.
/// </summary>
/// <param name="x">First argument to be swapped.</param>
/// <param name="y">Second argument to be swapped.
/// </param>
public static void Swap( ref T x, ref T y )
{
T tmp = x;
x = y; y = tmp;
}// Swap
/// <summary>Swap two generic array elements.
/// </summary>
/// <param name="fName">Name of function calling {Swap}.</param>
/// <param name="m">Reference to a generic array.</param>
/// <param name="i">Index of element to be swapped.</param>
/// <param name="j">Index of element to be swapped.
/// </param>
public static void Swap( string fName, T[] m, int i, int j )
{
++Uvar.swapCount;
if ( Uvar.outMode == OutMode.verbose )
{
TypedUfn<T>.DisplayArray( "", m );
DisplaySwap( fName, m, i, j ); // i, m[ i ], j, m[ j ] );
}
Swap( ref m[ i ], ref m[ j ] );
}// Swap
/// <summary>Display on the console a message describing a {Swap} operation
/// to be performed.
/// </summary>
/// <param name="fName">Name of function that will call {Swap}.</param>
/// <param name="m">Reference to a generic array.</param>
/// <param name="idx1">Index of first argument to {Swap}.</param>
/// <param name="idx2">Index of second argument to {Swap}.</param>
/// </param>
public static void DisplaySwap( string fName, T[] m, int idx1, int idx2 )
{
int k, _1st, _2nd;
if ( idx1 > idx2 ) // As in a swap operation in Smoothsort.
{
_1st = idx2; _2nd = idx1;
}
else // idx1 < idx2
{
_1st = idx1; _2nd = idx2;
}
UntypedUfn.SkipOB( out k ); UntypedUfn.DisplayStr( " ", ref k, _1st );
// k == _1st
Console.Write( Uvar.elementFormat, "↑" );
++k;
UntypedUfn.DisplayStr( " ", ref k, _2nd );
// k == _2nd
Console.WriteLine( Uvar.elementFormat, "↑" );
Console.WriteLine(
"\t{0}: swap( m[ {1,2} ]:{2,2}, m[ {3,2} ]:{4,2} ), swapCount: {5}\n",
fName, idx1, ElementToString( m, idx1 ), idx2, ElementToString( m, idx2 ),
Uvar.swapCount );
}// DisplaySwap
最后四个类型化实用函数中的两个是 DisplayArray（用于在控制台上以线性形式显示数组）和 DisplayTree（用于将数组显示为二叉树）。这两个函数都负责以适当的格式显示数组元素，第二个函数还负责树节点的间距。函数 DisplayArray 调用函数 DisplayIndices 以在数组元素上方显示索引。
/// <summary>Display on the console an array of generic elements.
/// </summary>
/// <param name="msg">Description of {arr}.</param>
/// <param name="arr">Array to be displayed.</param>
/// <param name="leadSpace">Optional lead spacing.
/// </param>
public static void DisplayArray( string msg, T[] arr, string leadSpace = "" )
{
int N = arr.Length;
if ( !String.IsNullOrEmpty( msg ) )
{
Console.WriteLine( "\n{0} array:\n", msg );
}
DisplayIndices( N, leadSpace );
if ( !String.IsNullOrEmpty( leadSpace ) )
{
Console.Write( leadSpace );
}
Console.Write( "[ " );
for ( int i = 0; i < N; ++i )
{
Console.Write( Uvar.elementFormat, ElementToString( arr, i ) );
}
Console.WriteLine( "]" );
}// DisplayArray
/// <summary>Display the indices for the elements of an array.
/// </summary>
/// <param name="N">Array length.</param>
/// <param name="leadSpace">Optional lead spacing.
/// </param>
private static void DisplayIndices( int N, string leadSpace = "" )
{
if ( !String.IsNullOrEmpty( leadSpace ) )
{
Console.Write( leadSpace );
}
Console.Write( " " ); // Go past "[ ".
for ( int i = 0; i < N; ++i )
{
Console.Write( Uvar.elementFormat, i );
}
Console.WriteLine();
}// DisplayIndices
/// <summary>Display a complete binary tree whose nodes are
/// stored in a generic array.
/// </summary>
/// <param name="msg">Message describing the tree.</param>
/// <param name="a">Generic array containing a complete binary tree.</param>
/// <remarks>
/// If {N} is the length of {a}, then for every index {i} in the interval
/// [ 0 .. ( {N} - 3 ) / 2) ] of a parent node in the complete binary
/// tree, the left child is at index ( 2 * {i} + 1 ) and the right child
/// is at index ( 2 * {i} + 2 ).
/// </remarks>
public static void DisplayTree( string msg, T[] a )
{
if ( !String.IsNullOrEmpty( msg ) )
{
Console.WriteLine( "\nTree {0}:", msg );
}
int N = a.Length, // Number of array elements.
maxLevel, // Maximum level of a perfect binary tree
// containing at least {N} nodes.
level = 0, // Current tree level.
nodes = 1, // Number of nodes to display at {level}.
// Lead spacing for first node at {level}.
leadSp = UntypedUfn.CeilPof2forTree( N, out maxLevel ),
// Spacing between consecutive nodes at {level}.
elemSp = 0;
int k = 0; // Count of nodes displayed.
do
{
Console.WriteLine();
UntypedUfn.Spaces( leadSp );
for ( int j = 1; j <= nodes && k < N; ++j )
{
Console.Write( Uvar.elementFormat, ElementToString( a, k ) );
++k;
UntypedUfn.Spaces( elemSp - 2 );
}
Console.WriteLine( "\n" );
elemSp = leadSp;
leadSp >>= 1;
++level;
nodes <<= 1;
} while ( level <= maxLevel );
Console.WriteLine();
}// DisplayTree
DisplayArray 和 DisplayTree 都调用函数 ElementToString 来处理数组元素类型为 char 或 string 的情况。请注意，如果数组元素是非基本数据类型，则该类型的定义必须重写函数 ToString，并且必须实现一个整数值的 CompareTo 函数。
/// <summary>Generate a {string} representation of a generic array-element.
/// </summary>
/// <param name="arr">Reference to a generic array.</param>
/// <param name="i">Index into {arr}.</param>
/// <returns>The generated string.
/// </returns>
public static string ElementToString( T[] arr, int i )
{
string str = arr[ i ].ToString();
if ( arr[ i ] is char )
{
return Uvar._1quote + str + Uvar._1quote;
}
if ( arr[ i ] is string )
{
return Uvar._2quote + str + Uvar._2quote;
}
return str;
}// ElementToString
最后，函数 DisplayTree 调用函数 UntypedUfn.CeilPof2forTree 来计算可以包含给定节点数的完美树的最小二的幂，以及该树的最大层级。这些数字用于树中每层节点的间距和显示。
/// <summary>Compute the smallest power of two for a perfect binary
/// tree containing at least a given number of nodes.
/// </summary>
/// <param name="nodes">Minimum number of nodes in the tree.</param>
/// <param name="maxLevel">{out} parameter: Maximum 0-based level of the tree.</param>
/// <returns>The smallest power of two required.
/// </returns>
/// <remarks>Usually (as in Heapsort) {nodes} is the number of nodes in a
/// complete binary tree.
/// </remarks>
public static int CeilPof2forTree( int nodes, out int maxLevel )
{
maxLevel = 0;
int pOf2 = 1, // == 2 ↑ maxLevel
sum = 1; // Sum of nodes in the tree.
while ( sum < nodes )
{
++maxLevel;
pOf2 <<= 1; // == 2 ↑ maxLevel
sum += pOf2;
}
// sum >= nodes
return pOf2;
}// CeilPof2forTree
大多数非类型化实用函数（在 UntypedUfn 类中）通过其 Intellisense 注释不言自明，此处将不进行描述。
8. 排序其他数据类型
在本节中，将展示 SmoothSort 能够处理任意数据类型。首先，考虑对字符数组进行排序。以下代码适用于提供一个简单的示例。请注意，函数 SortArray 的两个可选参数的值已被覆盖。
string str2 = "a sample string";
char[] c2 = str2.ToCharArray();
TypedUfn<char>.SortArray( "Smooth Sort c2", SmS.SmoothSort<char>, c2,
OutMode.verbose, true );
使用给定参数执行 SortArray 会产生大量的控制台输出。数组在排序前后以树形结构显示，对 Swap 函数的调用进行了记录，并且在每次交换后显示状态变量（b、c、p、r、q）和唯一的 Leonardo 树。图 18 显示了控制台输出的摘录。
为了演示对任意数据类型元素的排序，考虑定义一个类来表示二维整数 x-y 平面中的点。（作者知道 System.Drawing 命名空间中定义的 struct Point。但是，该 struct 没有定义 CompareTo 函数，这正是用户定义数据类型需要说明的。）
/// <summary>Class to encapsulate points on the two-dimensional {int} x-y plane.
/// </summary>
public class _2Dpoint : IComparable<_2Dpoint>
{
private int x, y;
public _2Dpoint( int _x, int _y )
{
x = _x; y = _y;
}// _2Dpoint
public override string ToString()
{
return String.Format( "({0} {1})", x, y );
}// ToString
/// <summary>Point comparison by lexicographic (i.e., dictionary) order.
/// </summary>
/// <param name="p">{_2Dpoint} to compare against.</param>
/// <returns> -1 if {this} is less than {p},
/// 0 if {this} is equal to {p},
/// +1 if {this} is greater than {p}.
/// </returns>
public int CompareTo( _2Dpoint p )
{
return ( x < p.x || ( x == p.x && y < p.y ) )
? -1
: ( x == p.x && y == p.y ) ? 0 : 1;
}// CompareTo
public static _2Dpoint[] _2DpointArray( params int[] xyPairs )
{
int n = xyPairs.Length;
if ( ( n % 2 ) != 0 )
{
throw new Exception( "_2DpointArray: argument list length must be even" );
}
_2Dpoint[] arr = new _2Dpoint[ n >> 1 ];
int i = 0, j = 0;
while ( i < n )
{
arr[ j ] = new _2Dpoint( xyPairs[ i ], xyPairs[ i + 1 ] );
i += 2;
++j;
}
return arr;
}// _2DpointArray
}// _2Dpoint (class)
类 _2Dpoint 非常简单。它定义了基本构造函数，重写了函数 ToString，最重要的是，定义了排序所需的整数值 CompareTo 函数。两个点的比较是根据字典序进行的。该类还定义了一个 static 函数来生成 _2Dpoint 实例数组。这样的函数期望一系列定义点的对数字。
以下代码创建了一个包含 13 个点的数组，并对该数组应用 SmoothSort。图 19 显示了控制台输出的摘录。请注意，_2Dpoint 类的实例显示在花括号内，例如 {3 0}，以避免与它们与 LP_Index 实例的编码混淆，例如 ( 1 6)。（这通过红色高亮显示。）
_2Dpoint[] g = _2Dpoint._2DpointArray(
8, 3, 5, 5, 4, 1, 1, 9, 5, 4, 1, 0,
4, 4, 3, 0, 4, 2, 4, 1, 1, 0, 0, 0, -1, 0 );
TypedUfn<_2Dpoint>.SortArray( "Smooth Sort g", SmS.SmoothSort<_2Dpoint>, g, OutMode.verbose );
9. 关于莱昂纳多数和莱昂纳多树的函数
根据 Dijkstra 的设计，Leonardo 数和树是 Smoothsort 不可或缺的一部分。类库 LPlib 包含几个类和许多处理 Leonardo 数和 Leonardo 树的函数。为了便于测试和编辑，它们最初编写在 GenericSmoothSort 命名空间中，但现在它们位于自己的库中。类及其函数将按照其开发顺序进行介绍。
需要注意的是，LPlib 的功能对于 SmoothSort 的执行是非必需的。如果在文件 SmS.cs 中每次调用 Swap 后将所有对函数 DisplayState 的调用注释掉，则 LP 相关的类和函数将不需要，并且排序将按预期工作。它们仅用于在控制台上记录 SmoothSort 的操作。因此，如果读者愿意，可以跳过本节。
9.1. LPfn 类
这个 static 类包含一个 static 变量和与 Leonardo 数相关的 static 函数。函数 LP 在必要时计算并返回一个 Leonardo 数。如第 5 节所述，Leonardo 数由以下递推关系定义
$LP(0) = LP(1) = 1$
$LP(n+2)=LP(n+1)+LP(n)+1$
函数 LP 通过使用一个 Leonardo 数列表 Lpnumber 进行记忆化，该列表的元素数量在执行过程中可能会增加。因此，Leonardo 数不会递归计算，而是按需生成。
// List of generated Leonardo numbers. Used to memoize function {LP}.
private static List<int> LPnumber = new List<int>() { 1, 1, 3 };
/// <summary>Compute the Leonardo number indexed by {k}.
/// </summary>
/// <param name="k">Index into list {LPnumber}.</param>
/// <returns>The corresponding Leonardo number.</returns>
/// <remarks>
/// The sequence of Leonardo numbers is defined as (cf. EWD796a - 3):
///
/// LP(-1) LP(0) LP(1) LP(2) LP(3) LP(4) LP(5) LP(6) LP(7) ...
/// (-1) 1 1 3 5 9 15 25 41 ...
/// </remarks>
public static int LP( int k )
{
if ( k < 0 )
{
return -1;
}
else
{
int n = LPnumber.Count - 1; // Index of maximum Leonardo number generated.
while ( n < k ) // Generate { LPnumber[ n + 1 ] }.
{
LPnumber.Add( LPnumber[ n ] + LPnumber[ n - 1 ] + 1 );
++n;
}
// {n == k}
return LPnumber[ k ];
}
}// LP
函数 InvLP 计算 Leonardo 数的逆（即索引），如果它存在的话。此函数并非严格必要，因为它仅被调用过一次（由函数 SmS.DisplayVars）用于显示目的。
/// <summary>Compute the inverse of a Leonardo number if it exists.
/// </summary>
/// <param name="lp">Leonardo number.
/// </param>
/// <returns>The index into array {LPnumber} for index {lp},
/// if it exists.
/// </returns>
/// <remarks>The function returns {-1} if {lp} is determined
/// NOT to be a Leonardo number.
/// The array {LPnumber} is NOT extended during the
/// search for the index corresponding to {lp}.
/// </remarks>
public static int InvLP( int lp )
{
int i = -1;
if ( lp > 0 )
{
int n = LPnumber.Count;
i = 1;
while ( ( i < n ) && ( LPnumber[ i ] != lp ) )
{
if ( LPnumber[ i ] > lp )
{
break; // {lp} is NOT a Leonardo number.
}
++i;
}
}
return i;
}// InvLP
函数 LPnumbers 有两个版本用于计算两个连续的 Leonardo 数。第一个版本确定一个索引 n，使得 SmoothSort 中全局变量 b 和 c 的值等于由 n 索引的两个连续 Leonardo 数（参见 EWD796a – 3）。第二个版本，给定较大 Leonardo 数的索引，计算两个连续的 Leonardo 数。
/// <summary>Compute a value of { n >= 0 } such that
/// { LP( n ) == b} && { LP( n - 1 ) == c}.
/// </summary>
/// <param name="b">Value of {b}.</param>
/// <param name="c">Value of {c}.</param>
/// <returns>Computed value of {n}.</returns>
/// <remarks>
/// The computation of {n} is due to the following predicate
/// (cf. EWD796a - 3):
///
/// (E n: n >= 0: b = LP( n ) && c = LP( n - 1 )
///
/// In words, there exists a non-negative {n} such that
/// { b == LP( n ) } && { c == LP( n - 1 ) }, that is,
/// {b} and {c} are consecutive Leonardo numbers.
/// </remarks>
public static int LPnumbers( int b, int c )
{
int n = 0, LPn = 1, LPn_1 = -1;
// LPn == LP( n ); LPn_1 == LP( n - 1 )
while ( !( n > b ) && !( LPn == b && LPn_1 == c ) )
{
++n;
int tmp = LPn;
LPn = LPn + LPn_1 + 1; // LP( n ).
LPn_1 = tmp; // LP( n - 1 ).
}
if ( n > b ) // {b} and {c} are NOT consecutive Leonardo numbers.
{
n = -1; LPn = -1; LPn_1 = -1; // Return failure.
}
return n;
}// LPnumbers
/// <summary>Compute two consecutive Leonardo numbers for a given index.
/// </summary>
/// <param name="k">Index of the second (larger) Leonardo number.</param>
/// <param name="LPn">{out} parameter: {LP( k )}.</param>
/// <param name="LPn_1">{out} parameter: {LP( k - 1 )}.
/// </param>
public static void LPnumbers( int k, out int LPn, out int LPn_1 )
{
int n = 0; LPn = 1; LPn_1 = -1;
while ( n < k )
{
++n;
int tmp = LPn;
LPn = LPn + LPn_1 + 1; // == LP( n ).
LPn_1 = tmp; // == LP( n - 1 ).
}
// {n == k}
}// LPnumbers
9.2. LP_Index 类
此类别封装一个莱昂纳多数和一个数组索引。它是编码莱昂纳多树节点的基本构建块。该类别重写了 ToString 函数，并提供了 CompareTo 函数和用于确定编码是否简单对应于单例节点的函数。
public class LP_Index
{
private int lp; // LP (or Lk) Leonardo number.
private int index; // Index into a linear array.
// Properties
public int LP { get { return lp; } }
public int Index { get { return index; } }
public LP_Index( int _lp, int _index )
{
lp = _lp;
index = _index;
}// LP_Index (constructor)
/// <summary>Overriden function {ToString}.
/// </summary>
/// <returns>Formatted {string} "({lp}, {index})".
/// </returns>
public override string ToString()
{
return String.Format( "({0,2} {1,2})", lp, index );
}// ToString
/// <summary>Lexicographic-order comparison of {this} instance and
/// another {LP_Index} instance.
/// </summary>
/// <param name="other">{LP_Index} instance to compare against.</param>
/// <returns>{-1} if {this} is less than {other}.
/// {0} if {this} and {other} are equal.
/// {+1} if {this} is greater than {other}.
/// </returns>
public int CompareTo( LP_Index other )
{
if ( (lp < other.lp ) || ( lp == other.lp && index < other.index ) )
{
return -1;
}
if ( lp == other.lp && index == other.index )
{
return 0;
}
return +1;
}// CompareTo
/// <summary>Determine whether the node encoded by {this} is a
/// singleton (leaf) node.
/// </summary>
/// <returns>{true} if the node is singleton; {false} otherwise.
/// </returns>
/// <remarks>A node in a Leonardo tree is singleton if its leonardo
/// number equals 1.
/// </remarks>
public bool Is_Singleton()
{
return lp == 1;
}// Is_Singleton
}// LP_Index (class)
9.3. LPtriple 类
此类封装了三个 LP_Index 实例，它们编码了 Leonardo 树的节点：左子节点、右子节点及其父节点。此类实例由 LPtree 类用于描述在排序数组跨度上的 Leonardo 树，该跨度由 SmoothSort 中的全局变量 b 及其“伴侣” c 界定。
public class LPtriple<T> where T : IComparable<T>
{
// Encoding of three nodes of a Leonardo tree.
private LP_Index parent, leftChild, rightChild; // Node encodings.
private string pKey, lChKey, rChKey; // Keys into a dictionary.
private string strRepr; // String representation of the triple.
/// <summary>Empty constructor.
/// </summary>
public LPtriple()
{
parent = leftChild = rightChild = null;
pKey = lChKey = rChKey = null;
Displayed = false;
strRepr = null;
}// LPtriple
/// <summary>// Encode three nodes of a possible Leonardo tree.
/// </summary>
/// <param name="pairs">Sequence of three {LP, Index} pairs.
/// </param>
/// <remarks>The tree is labeled "possible" because the validity
/// of its nodes must be verified by the caller.
/// </remarks>
/// <returns>Array encoding three nodes of a possible Leonardo tree.
/// </returns>
public LPtriple( params int[] pairs )
{
parent = leftChild = rightChild = null;
pKey = lChKey = rChKey = null;
if ( pairs.Length != 6 )
{
throw new Exception( "LPtriple constructor: 6 {int} parameters expected" );
}
parent = new LP_Index( pairs[ 0 ], pairs[ 1 ] ); // Encoding of parent node.
leftChild = new LP_Index( pairs[ 2 ], pairs[ 3 ] ); // Encoding of left child node.
rightChild = new LP_Index( pairs[ 4 ], pairs[ 5 ] ); // Encoding of right child node.
Displayed = false;
// Keys into a dictionary
pKey = parent.ToString();
lChKey = leftChild.ToString();
rChKey = rightChild.ToString();
strRepr = ToString(); // {string} representation.
}// LPtriple
// Properties.
public LP_Index Parent { get { return parent; } }
public LP_Index LeftChild { get { return leftChild; } }
public LP_Index RightChild { get { return rightChild; } }
public string ParentKey { get { return pKey; } }
public string LchildKey { get { return lChKey; } }
public string RchildKey { get { return rChKey; } }
public bool Displayed { get; set; }
public int Width { get { return strRepr.Length; } }
public string StrRepr { get { return strRepr; } }
/// <summary>Generate a {string} representation of {this} triple.
/// </summary>
/// <returns>The generated string.
/// </returns>
public override string ToString()
{
return String.Format( "< {0} {1} {2} >",
LchildKey, RchildKey, ParentKey,
Displayed ? " *" : "" );
}// ToString
/// <summary>Generate a long {string} representation of {this} triple.
/// </summary>
/// <param name="m">Reference to a generic array.</param>
/// <returns>The generated string.
/// </returns>
/// <remarks>The generated string contains the string representations
/// of the array {m} elements indexed by the triple.
/// </remarks>
public string ToLongString( T[] m )
{
return String.Format( "< {0}: {1}, {2}: {3}, {4}: {5} >{6}",
LchildKey, TypedUfn<T>.ElementToString( m, leftChild.Index ),
RchildKey, TypedUfn<T>.ElementToString( m, rightChild.Index ),
ParentKey, TypedUfn<T>.ElementToString( m, parent.Index ),
Displayed ? " *" : "" );
}// ToLongString
/// <summary>Make a fresh copy of {this} triple.
/// </summary>
/// <returns>Copy of {this} triple.
/// </returns>
public LPtriple<T> Copy()
{
LPtriple<T> _copy = new LPtriple<T>();
_copy.parent = this.parent;
_copy.leftChild = this.leftChild;
_copy.rightChild = this.rightChild;
_copy.pKey = this.pKey;
_copy.lChKey = this.lChKey;
_copy.rChKey = this.rChKey;
_copy.strRepr = this.strRepr;
_copy.Displayed = this.Displayed;
return _copy;
}// Copy
/// <summary>Determine whether {this} triple is a valid Leonardo-tree triple.
/// </summary>
/// <param name="m">Reference to a generic array.</param>
/// <returns>{true} if {this} triple is valid; {false} otherwise.
/// </returns>
/// <remarks>A triple is considered valid if the children nodes in {m} do not exceed
/// their parent node.
/// </remarks>
public bool IsValid( T[] m )
{
return UntypedUfn.IsLE( m[ leftChild.Index ].CompareTo( m[ parent.Index ] ) )
&&
UntypedUfn.IsLE( m[ rightChild.Index ].CompareTo( m[ parent.Index ] ) );
}// IsValid
}// LPtriple (class)
该类重写了标准的 ToString 函数，并提供了一个 ToLongString 函数，该函数包含由三元组索引的数组元素的值，如果该三元组已在控制台显示，则包含一个星号。有一个 Copy 构造函数和一个函数用于确定三元组是否编码了一个有效的莱昂纳多树或子树，即子节点是否未超出其父节点。
9.4. LPvar 和 LPtree 类
static 类 LPvar 包含一个一次性全局变量，该变量已从 SmoothSort 中移除，因为它在 Dijkstra 的原始代码中未使用，没有理由存在。
using System;
using System.Collections.Generic;
namespace LPlib
{
/// <summary>Class to encapsulate a one-time global variable.
/// </summary>
public static class LPvar
{
// The following global variable is used to keep track of generated dictionaries of the
// elements from a generic array indexed by Leonardo trees, so that (sub-)trees of saved
// and displayed trees are not displayed again on the console.
//
// The index-dictionary keys are {string} representations of {LP_Index} instances, and the
// values are arrays containing the {string} representation of left-child, right-child and
// parent nodes, in that order, from the array elements indexed by {LPtriple} instances.
public static List<Dictionary<string, string[]>> nodeValuesDictList = null;
}// LPvar (static class)
}// LPlib (namespace)
变量 nodeValuesDictList 用于跟踪在 SmoothSort 执行期间生成的字典，以防止显示已经显示过的树或子树。自然的选择是使用 LP_Index 类的实例作为字典键。但是，它们不能使用，因为 C# 中的 Dictionary 类为键计算哈希码，并且只能将哈希应用于基本数据类型。因此，LP_Index 实例的 string 表示形式被用作字典键。由于 LPtree 类有几个字段和许多函数，因此将分别描述它们。
类 LPtree 包含几个 private 字段，在以下部分描述中声明。
using System;
using System.Collections.Generic;
using UtilSortLib;
namespace LPlib
{
public class LPtree<T> where T : IComparable<T>
{
private T[] mSnap; // Snapshot of a generic array.
private int b, c; // Values of global variables {b} and {c}
// declared in class {SmS}.
private List<List<LPtriple<T>>>
cTriples, // List of {LPtriple} triples lists for upper bound {c}.
bTriples; // List of {LPtriple} triples lists for upper bound {b}.
private string cBounds, bBounds; // Interval bounds for {cTriples} and {bTriples}.
private LP_Index rootNode; // Reference to the root of a "b-c" Leonardo tree.
// Dictionary of triples for (possibly disjoint) Leonardo trees.
private Dictionary<string, LPtriple<T>> triplesDict;
// Dictionary of values from {mSnap} elements.
private Dictionary<string, string[]> nodeValuesDict;
// Queue of {LP_Index} node descriptors.
private Queue<LP_Index> nodeQueue;
...
}// LPtree (class)
}// LPlib (namespace)
类构造函数在第一次调用时初始化所有字段和唯一的全局变量 LPvar.nodeValuesDictList。由于此构造函数在每次调用 TypedUfn<T>.Swap 后由函数 SmS.DisplayState 调用，因此它将当前排序数组的状态以及 SmoothSort 中全局变量 b 和 c 的值作为参数。然后它通过调用 GenerateTriples 来生成数组上半开区间 [ 0, c ) 和 [ c, b ) 中的三元组。
public LPtree( T[] _m, int _b, int _c )
{
mSnap = new T[ _m.Length ]; // Take a snapshot of array
_m.CopyTo( mSnap, 0 ); // referenced by {_m}.
b = _b; c = _c; // Copy arguments from class {SmS}
// global variables.
if ( LPvar.nodeValuesDictList == null )
{
// Initialization on first call to {LPtree} constructor.
LPvar.nodeValuesDictList = new List<Dictionary<string, string[]>>();
}
cTriples = new List<List<LPtriple<T>>>(); // Empty lists of triples.
bTriples = new List<List<LPtriple<T>>>();
cBounds = bBounds = String.Empty;
triplesDict
= new Dictionary<string, LPtriple<T>>(); // Empty dictionary of triples.
nodeValuesDict
= new Dictionary<string, string[]>(); // Empty dictionary of {string} array values.
rootNode = null; // Root node of a "b-c" Leonardo tree.
nodeQueue = null; // Queue of nodes at same level.
GenerateTriples();
}// LPtree (constructor)
只要 c 大于 1，然后在 b – c 大于 2 时，就会在指定的区间内生成三元组。它们由函数 IntervalTriples 生成，并通过函数 AddToDictionaries 添加到两个字典中。最后一个函数返回“b-c”莱昂纳多树根节点的 LP_Index 编码。
private void GenerateTriples()
{
// ( E n: n >= 0 && b == LPfn.LP( n ) && c == LPfn.LP( n - 1 ) )
// &&
// b >= c
triplesDict = new Dictionary<string, LPtriple<T>>();
rootNode = null;
int i = LPfn.InvLP( c );
if ( c > 1 )
{
cTriples = IntervalTriples( 0, c );
cBounds = String.Format( "[{0}, {1})", 0, c );
AddNewList( RootTriple( i, c ), cTriples );
rootNode = AddToDictionaries( cTriples, triplesDict );
}
if ( ( b - c ) > 2 )
{
bTriples = IntervalTriples( c, b );
bBounds = String.Format( "[{0}, {1})", c, b );
++i;
AddNewList( RootTriple( i, b ), bTriples );
rootNode = AddToDictionaries( bTriples, triplesDict );
}
nodeQueue = new Queue<LP_Index>();
if ( rootNode != null )
{
nodeQueue.Enqueue( rootNode );
}
}// GenerateTriples
函数 IntervalTriples 在排序数组的半开区间内生成 LPtriple 列表的列表。创建列表列表的原因是，某些三元组编码树层次结构中较上层的节点，而其他三元组编码与同一级别其他节点相同的节点。图 20 显示了这两种情况的示例。
/// <summary>Generate a list of {LPtriple} lists for a half-open interval
/// [ {lb}, {ub} ) of {mSnap}.
/// </summary>
/// <param name="lb">Lower bound on array {mSnap}.</param>
/// <param name="ub">Upper bound on array {mSnap}.</param>
/// <returns>The list of lists of triples generated.
/// </returns>
/// <remarks>The upper bound {ub} is NOT included in the last triple.
/// </remarks>
private List<List<LPtriple<T>>> IntervalTriples( int lb, int ub )
{
List<List<LPtriple<T>>> listOfTriplesLists = new List<List<LPtriple<T>>>();
int i = 1, // Index of Leonardo number.
LPi = LPfn.LP( i ), // Leonardo number {i}.
k = lb; // Running index into array {m}.
LPtriple<T> triple0 = new LPtriple<T>(), triple1 = new LPtriple<T>();
while ( LPi < ub )
{
++i;
LPi = LPfn.LP( i );
if ( lb + LPi >= ub )
{
break;
}
k = lb + LPi - 1;
MakeNewTriple( i, k, ref triple0, ref triple1, listOfTriplesLists );
};
i = 1;
while ( k < ub )
{
++i;
LPi = LPfn.LP( i );
k += LPi;
if ( k >= ub )
{
break;
}
MakeNewTriple( i, k, ref triple0, ref triple1, listOfTriplesLists );
};
return listOfTriplesLists;
}// IntervalTriples
创建新级别三元组或在当前最后一级别扩展三元组列表的决定由函数 MakeNewTriple 执行，该函数调用 AddNewList 或 ExtendLastList 来执行这些任务。
/// <summary>Generate a parent, left-child, right-child triple to index
/// elements from array {mSnap}.
/// </summary>
/// <param name="i">Index of a Leonardo number.</param>
/// <param name="k">Index into array {mSnap}.</param>
/// <param name="triple0">Reference to the last triple generated (if any).</param>
/// <param name="triple1">Reference to the variable that will get the new triple.</param>
/// <param name="listOfTriplesLists">Reference to a list of lists of triples.
/// </param>
private void MakeNewTriple( int i, int k,
ref LPtriple<T> triple0, ref LPtriple<T> triple1,
List<List<LPtriple<T>>> listOfTriplesLists )
{
triple0 = triple1.Copy();
triple1
= new LPtriple<T>( LPfn.LP( i ), k, // for mSnap[ k ],
LPfn.LP( i - 1 ), k - 2, // for mSnap[ k - 2 ],
LPfn.LP( i - 2 ), k - 1 ); // for mSnap[ k - 1 ] );
if ( ( listOfTriplesLists.Count == 0 )
||
UntypedUfn.IsEQ(
mSnap[ triple1.LeftChild.Index ].CompareTo( mSnap[ triple0.Parent.Index ] ) ) )
{
AddNewList( triple1, listOfTriplesLists );
}
else
{
ExtendLastList( listOfTriplesLists, triple1 );
}
}// MakeNewTriple
/// <summary>Create a new list containing a triple and add the list to a list
/// of lists of triples.
/// </summary>
/// <param name="triple">Triple to add to the new list.</param>
/// <param name="listOfTriplesLists">List of lists of triples.
/// </param>
private void AddNewList( LPtriple<T> triple, List<List<LPtriple<T>>> listOfTriplesLists )
{
List<LPtriple<T>> tripleList = new List<LPtriple<T>>();
tripleList.Add( triple );
listOfTriplesLists.Add( tripleList );
}// AddNewList
/// <summary>Add a triple to the last list of triples.
/// </summary>
/// <param name="listOfTriplesLists">List of lists of triples.</param>
/// <param name="triple">Triple to add.
/// </param>
private void ExtendLastList( List<List<LPtriple<T>>> listOfTriplesLists, LPtriple<T> triple )
{
List<LPtriple<T>> tripleList = listOfTriplesLists[ listOfTriplesLists.Count - 1 ];
tripleList.Add( triple );
}// ExtendLastList
函数 RootTriple 由 GenerateTriples 调用，为生成的 c- 和 b-三元组列表创建根节点三元组，并添加一个包含该节点的新列表。
/// <summary>Create the root triple for a list of triples.
/// </summary>
/// <param name="i">Index of Leonardo number.</param>
/// <param name="k">Index into array {mSnap}.</param>
/// <returns>The triple generated.
/// </returns>
private LPtriple<T> RootTriple( int i, int k )
{
// root index = k - 1
// left child index = LP( i - 1 ) - 1
// right child index = k - 2
int LPi_1 = LPfn.LP( i - 1 );
return new LPtriple<T>( LPfn.LP( i ), k - 1, // for mSnap[ k - 1 ],
LPi_1, LPi_1 - 1, // for mSnap[ LPfn.LP( i - 1 ) - 1 ],
LPfn.LP( i - 2 ), k - 2 ); // for mSnap[ k - 2 ] );
}// RootTriple
当 c- 和 b-三元组列表完成后，调用函数 AddToDictionaries 将每个列表中的三元组添加到用于显示 Leonardo 树的字典，以及用于避免多次显示 Leonardo 树的字典 nodeValuesDict。每个三元组中父节点的 LP_Index 编码的 string 表示形式用作两个字典的键。第一个字典中的值是三元组，而第二个字典中的值是包含排序数组快照 (mSnap) 中索引元素的 string 表示形式的数组。
/// <summary>Add to two dictionaries the corresponding elements from
/// a list of lists of triples.
/// </summary>
/// <param name="listOfTriplesLists">List of lists of triples.</param>
/// <param name="dictionary">Reference to a dictionary.</param>
/// <returns>Reference to the {LP_Index} encoding the parent
/// (a root node) from the last triple (if any).
/// </returns>
private LP_Index AddToDictionaries( List<List<LPtriple<T>>> listOfTriplesLists,
Dictionary<string, LPtriple<T>> dictionary )
{
LPtriple<T> lastTriple = null;
foreach ( List<LPtriple<T>> triplesList in listOfTriplesLists )
{
foreach ( LPtriple<T> triple in triplesList )
{
string key = triple.Parent.ToString();
dictionary.Add( key, triple );
string[] valueArr =
new string[ 3 ] { mSnap[ triple.LeftChild.Index ].ToString(),
mSnap[ triple.RightChild.Index ].ToString(),
mSnap[ triple.Parent.Index ].ToString() };
nodeValuesDict.Add( key, valueArr );
lastTriple = triple;
}
}
return lastTriple == null ? null : lastTriple.Parent;
}// AddToDictionaries
正如图 20 的标题中提到的，如果函数 TrySaveAndDisplay 的可选参数值为 true，则通过调用函数 DisplayTriples 在控制台上显示 c- 和 b-三元组。然后，如果有节点要显示，并且如果字典 nodeValuesDict 不在 LPvar.nodeValuesDictList（全局字典列表）中，则将其添加到该列表，并显示 Leonardo 树，从由 c 和 b 子树跨越的树开始，并继续显示不相交的树。
/// <summary>Try to save in a list, and display on the console the c- and b-triples
/// (if requested), the dictionary of triples, the (L, R, ↑) labels for
/// array elements, and the nodes of the Leonardo tree(s).
/// </summary>
/// <param name="dispTriples">Optional parameter indicating whether to display
/// the generated c- and b-triples (if any).
/// </param>
public void TrySaveAndDisplay( bool dispTriples = false )
{
if ( triplesDict.Count > 0 )
{
if ( dispTriples )
{
if ( cTriples.Count > 0 )
{
DisplayTriples( "c", cBounds, cTriples );
if ( bTriples.Count > 0 )
{
DisplayTriples( "b", bBounds, bTriples );
}
}
}
if ( ( nodeQueue.Count > 0 ) )
{
if ( !InDictionaryList( LPvar.nodeValuesDictList ) )
{
LPvar.nodeValuesDictList.Add( nodeValuesDict );
DisplayLabels( triplesDict );
DisplayNodes( nodeQueue, triplesDict ); // Tree spanned by the
// "b" and "c" sub-trees.
DisplayDisjointTrees( triplesDict );
}
}
}
}// TrySaveAndDisplay
函数 DisplayTriples 由 TrySaveAndDisplay 调用，用于显示 c 和 b 三元组列表。函数 InDictionaryList 借助函数 SubTreeOf 和 SameElementValues，确定节点值字典是否在全局字典列表中。这些函数的 Intellisense 注释非常直观。
/// <summary>Display on the console a list of triples encoding a Leonardo tree.
/// </summary>
/// <param name="msg">Name of the list.</param>
/// <param name="listOfTriplesLists">List of lists of triples.
/// </param>
private void DisplayTriples( string name, string bounds,
List<List<LPtriple<T>>> listOfTriplesLists )
{
Console.WriteLine( "\n{0} sub-tree triples {1} :\n", name, bounds );
foreach ( List<LPtriple<T>> triplesList in listOfTriplesLists )
{
foreach ( LPtriple<T> triple in triplesList )
{
Console.Write( triple.ToLongString( mSnap ) );
Console.Write( " " );
}
Console.WriteLine();
}
}// DisplayTriples
/// <summary>Determine whether the dictionary {nodeValuesDict} contains the
/// same node values as another dictionary in the global list of
/// node-values dictionaries.
/// </summary>
/// <returns>{true} if there is a saved dictionary with the same node values.
/// {false} otherwise.
/// </returns>
private bool InDictionaryList( List<Dictionary<string, string[]>> nodeValsDictList )
{
bool inList = false;
if ( nodeValsDictList.Count > 0 )
{
foreach ( Dictionary<string, string[]> otherDict in nodeValsDictList )
{
if ( SubTreeOf( otherDict ) )
{
inList = true; break;
}
}
}
return inList;
}// InDictionaryList
/// <summary>Determine whether dictionary {nodeValuesDict} and another
/// dictionary contain the same node values.
/// </summary>
/// <param name="otherDict">Reference to another dictionary.</param>
/// <returns>{true} if both dictionaries contain the same node values.
/// {false} otherwise.
/// </returns>
/// <remarks>By definition, a tree is a sub-tree of itself. Hence, this
/// function also tests tree equality.
/// </remarks>
private bool SubTreeOf( Dictionary<string, string[]> otherDict )
{
foreach ( KeyValuePair<string, string[]> kvp in nodeValuesDict )
{
if ( otherDict.ContainsKey( kvp.Key ) )
{
if ( !SameElementValues( kvp.Value, otherDict[ kvp.Key ] ) )
{
return false;
}
}
else
{
return false;
}
}
return true;
}// SubTreeOf
/// <summary>Determine whether two {string} arrays contain the same values.
/// </summary>
/// <param name="idxArr1">Reference to first array.</param>
/// <param name="idxArr2">Reference to second array.</param>
/// <returns>{true} if the arrays contain the same values; {false} otherwise.
/// </returns>
private bool SameElementValues( string[] idxArr1, string[] idxArr2 )
{
return idxArr1[ 0 ].Equals( idxArr2[ 0 ] ) // Left child.
&&
idxArr1[ 1 ].Equals( idxArr2[ 1 ] ) // Right child.
&&
idxArr1[ 2 ].Equals( idxArr2[ 2 ] ); // Parent
}// SameElementValues
如果节点值字典不在全局列表中，函数 TrySaveAndDisplay 会将其添加到列表中，并调用 DisplayLabels，以一些前导空格显示排序数组的快照，并逐行显示节点编码的三元组和标签（“L”、“R”和“↑”），以标记由三元组编码的莱昂纳多树的左子节点、右子节点和根节点。前导空格由函数 MaxTripleWidth 计算。
/// <summary>Display on the console the array being sorted, the triples
/// in a dictionary, and "L", "R" and "↑" labels under the
/// array elements.
/// </summary>
/// <param name="dictionary">Dictionary of {LPtriple} instances.
/// </param>
private void DisplayLabels( Dictionary<string, LPtriple<T>> dictionary )
{
string fmtStr = Uvar.elementFormat,
leadSpFmt = "{0," + MaxTripleWidth( dictionary ).ToString() + "}",
leadSpace = String.Format( leadSpFmt, " " );
Console.WriteLine();
TypedUfn<T>.DisplayArray( "", mSnap, leadSpace );
foreach ( KeyValuePair<string, LPtriple<T>> kvp in dictionary )
{
LPtriple<T> triple = kvp.Value;
int idx;
Console.Write( triple.StrRepr );
UntypedUfn.SkipOB( out idx );
UntypedUfn.DisplayStr( " ", ref idx, triple.LeftChild.Index );
Console.Write( fmtStr, "L" );
UntypedUfn.DisplayStr( " ", ref idx, triple.RightChild.Index - 1 );
Console.Write( fmtStr, "R" );
UntypedUfn.DisplayStr( " ", ref idx, triple.Parent.Index - 2 );
Console.WriteLine( fmtStr, "↑" );
}
Console.WriteLine();
}// DisplayLabels
/// <summary>Compute the maximum width (number of characters) of the {string}
/// representations of triples in a dictionary.
/// </summary>
/// <param name="dictionary">Dictionary of triples.</param>
/// <returns>The maximum width.
/// </returns>
private static int MaxTripleWidth( Dictionary<string, LPtriple<T>> dictionary )
{
int maxWidth = 0;
foreach ( KeyValuePair<string, LPtriple<T>> kvp in dictionary )
{
LPtriple<T> triple = kvp.Value;
if ( triple.Width > maxWidth )
{
maxWidth = triple.Width;
}
}
return maxWidth;
}// MaxTripleWidth
由 TrySaveAndDisplay 调用的最后两个函数是 DisplayNodes 和 DisplayDisjointTrees。第一个函数与 UtilSortLib 的 TypedUfn<T> 类中的 DisplayTree 函数非常相似，但它使用队列来处理树的逐层遍历（即广度优先搜索中使用的技术）。在显示“b-c”莱昂纳多树后，调用函数 DisplayDisjointTrees 以显示该树无法访问的任何树，如图 14、16a 和 16b 所示。
/// <summary>Level-by-level (i.e., breadth-first) display on the console
/// the nodes of a Leonardo tree.
/// </summary>
/// <param name="nodeQueue">Queue of {LP_Index} elements encoding nodes from
/// array {mSnap} to be displayed.</param>
/// <param name="dictionary">Dictionary of node-encoding triples.</param>
/// <remarks>The elements in the queue encode nodes at the same level
/// of a binary tree.
/// </remarks>
private void DisplayNodes( Queue<LP_Index> nodeQueue,
Dictionary<string, LPtriple<T>> dictionary )
{
int maxLevel,
// Leading space for first node.
leadSp = UntypedUfn.CeilPof2forTree( 2 * dictionary.Count + 2,
out maxLevel ),
// Space between consecutive nodes at the same level.
elemSp = 0;
bool valid = true; // Whether or not the tree is valid.
Queue<LP_Index> childrenQueue;
List<string> absentKeys = new List<string>();
Console.WriteLine();
do
{
UntypedUfn.Spaces( leadSp );
childrenQueue = new Queue<LP_Index>();
while ( nodeQueue.Count > 0 )
{
LP_Index node = nodeQueue.Dequeue();
string key = node.ToString();
Console.Write( Uvar.elementFormat,
TypedUfn<T>.ElementToString( mSnap, node.Index ) );
UntypedUfn.Spaces( elemSp - 2 );
if ( dictionary.ContainsKey( key ) ) // {node} is a parent.
{
LPtriple<T> triple = dictionary[ node.ToString() ];
childrenQueue.Enqueue( triple.LeftChild );
childrenQueue.Enqueue( triple.RightChild );
if ( valid ) // The tree is valid so far.
{
valid = triple.IsValid( mSnap );
}
triple.Displayed = true;
}
else if ( !node.Is_Singleton() ) // Not a singleton node.
{
absentKeys.Add( key );
}
}
Console.WriteLine( "\n\n" );
if ( childrenQueue.Count > 0 )
{
nodeQueue = childrenQueue;
elemSp = leadSp;
leadSp >>= 1;
}
} while ( childrenQueue.Count > 0 );
Console.WriteLine( "{0} Leonardo tree\n", valid ? "Valid" : "Invalid" );
}// DisplayNodes
/// <summary>Display on the console the isolated Leonardo trees (if any).
/// </summary>
/// <param name="dictionary">Dictionary of triples.
/// </param>
private void DisplayDisjointTrees( Dictionary<string, LPtriple<T>> dictionary )
{
Dictionary<string, LPtriple<T>> subDict;
Queue<LP_Index> nodeQueue;
LP_Index lastParent;
do
{
subDict = new Dictionary<string, LPtriple<T>>();
nodeQueue = new Queue<LP_Index>();
lastParent = null;
foreach ( KeyValuePair<string, LPtriple<T>> kvp in dictionary )
{
LPtriple<T> triple = kvp.Value;
if ( !triple.Displayed )
{
subDict.Add( kvp.Key, kvp.Value );
lastParent = triple.Parent;
}
}
if ( lastParent != null )
{
nodeQueue.Enqueue( lastParent );
DisplayNodes( nodeQueue, subDict );
}
} while ( lastParent != null );
}// DisplayDisjointTrees
10. 结论
本文介绍了 Edsger W. Dijkstra 的 Smoothsort 算法几乎字面上的 C# 翻译。它被实现为一组通用的 C# 函数。由于 Smoothsort 被提议作为原地排序的 Heapsort 的替代方案，因此也介绍了后者在 C# 中的通用实现。两种算法都在整数和字符数据类型以及表示整数 x-y 平面上点的类实例上进行了测试。在示例执行中，当原始数组接近或完全排序时，Smoothsort 被证明优于 Heapsort。
11. 使用代码
本文描述的代码位于多个目录中。目录的路径在图 21 中列出并解释，因为代码存储在驱动器号为“F:”的 USB 驱动器中。路径中的每个终端目录都包含一个完整的 Visual Studio 解决方案，因此代码可以直接使用。TESTS 目录下的解决方案（TestHeapSort 和 TestSmoothSort）是控制台应用程序。所有其他解决方案都是库，不能独立执行。测试应用程序提供了如何使用代码的示例，并且无需更改库即可运行。大多数示例都被注释掉了，读者可以取消注释特定的示例以运行排序算法的测试。
如果对库进行了任何更改，则应重新构建它们。库 _2DpointsLib 和 UtilSortLib 彼此独立，可以按任何顺序构建，但它们必须在 GenericHeapSort 之前构建。库 LPlib 必须在 UtilSortLib 之后和 GenericSmoothSort 之前构建。这两个排序库也彼此独立。重新构建库后，测试应用程序可以按任何顺序重新构建。
图 21 中列出的每个 Visual Studio 解决方案都包含一个 _TXT 子目录，其中包含一个或多个描述解决方案 C# 源文件更新历史的文本文件。
12. 参考文献
Dijkstra, E.W., 1981。
“Smoothsort，一种原地排序的替代方案。”文章 EWD796a，1981 年 8 月 16 日。可在E.W.Dijkstra 档案中获取，由德克萨斯大学奥斯汀分校计算机科学系提供。
Dijkstra, E.W. 和 W.H.J. Feijen, 1988。
《编程方法》。Addison-Wesley Publishing Co., Inc. Reading, Massachusetts。1988 年首次英文版印刷。1989 年重印。
Orejel, J.L., 2003。
“应用算法与数据结构”。未出版教材。附录 VI 第 6 章习题 VI.2.1 节解决方案，第 VI-8 - VI.9 页。
Schwarz, K., 2011。
“Smoothsort 揭秘。”未出版文章。发布于 https://www.keithschwarz.com/smoothsort/。
van Gasteren, A.J.M, E.W. Dijkstra, 和 W.H.J Feijen, 1981。
“堆排序。”文章 AvG8/EWD794/WF39，1981 年 6 月 22 日。在 E.W.Dijkstra 档案中，可从德克萨斯大学奥斯汀分校计算机科学系获取。
Williams, J,W.J., 1964。
“算法 232 HEAPSORT。”ACM 通讯，第 7 卷，第 6 期，1964 年 6 月，第 347-348 页。重印于《ACM 算法集，第二卷，算法 221-492》，Association for Computing Machinery, Inc.，纽约，1980 年，第 232-P 1-0 页。
13. 附言
在 1986-87 学年春季学期，作为一名博士生，作者有幸在德克萨斯大学奥斯汀分校计算机科学系修读了 Edsger Wybe Dijkstra 教授的“计算科学精选专题”课程。（是的，我通过了艰苦但迷人的期末口试，必须证明著名的 Knaster-Tarski 定理，并以“A”的成绩通过了该课程）。本文谨以此献给 Edsger 的记忆。
历史
- 2023 年 12 月 11 日：初始版本