如何计算堆排序键比较

Question

我写了一个小的C#命令应用程序。四个数组应该使用堆排序算法进行排序。我从一个网站上获取了一个算法，它运行得很好。现在我想计算算法对一个数组进行排序所需的键比较。我试图通过 for 循环计算比较，但它似乎是错误的......有什么想法可以计算在哪里吗？

这是我的排序算法方法。 GlobalVar.CountVal只是一个public static int属性。

public static void HeapSort(int[] array, int arr_ubound)
{
    int i, j;
    int lChild, rChild, pNode, root, temp;
    root = (arr_ubound - 1) / 2;
    for (j = root; j >= 0; j--)
    {
        for (i = root; i >= 0; i--)
        {
            GlobalVar.CountVal += 1;
            lChild = (2*i)+1;
            rChild = (2*i)+2;
            if ((lChild <= arr_ubound) && (rChild <= arr_ubound))
            {
                if (array[rChild] >= array[lChild])
                    pNode = rChild;
                else
                    pNode = lChild;
            }
            else
            {
                if (rChild > arr_ubound)
                    pNode = lChild;
                else
                    pNode = rChild;
            }
            if (array[i] < array[pNode])
            {
                temp = array[i];
                array[i] = array[pNode];
                array[pNode] = temp;
            }
        }
    }
    temp = array[0];
    array[0] = array[arr_ubound];
    array[arr_ubound] = temp;
    return;
}

以下是完整的代码： http://pastebin.com/4Y0NQECP

Answer 1

通过使用这个比较器而不是比较运算符（>=和<），你可以正确地计算比较。

public class CountingComparer<T> : Comparer<T>
{
    public int Count { get; private set; }
    IComparer<T> defaultComparer = Comparer<T>.Default;
    public override int Compare(T left, T right)
    {
        this.Count++;
        return defaultComparer.Compare(left, right);
    }
}

若要使用这样的比较器，请按以下步骤修改代码：

x [op] y // becomes
comparer.Compare(x, y) [op] 0
// e.g.
if (array[rChild] >= array[lChild]) // becomes
if (comparer.Compare(array[rChild], array[lChild]) >= 0)

然后，只需确保将此比较器用于堆排序中的每个比较（但仅在该排序中）。完整的代码（因为我在 LINQPad 中运行）在 http://pastebin.com/UXAQh9B3。我将您的方法从硬编码更改为通用，以便更轻松地识别需要使用比较器的位置。

数据的比较计数如下所示：

1 - 652
2 - 652
3 - 0
4 - 155