问题描述
我写了一个C#命令应用程序。假设使用堆叠算法对四个数组进行排序。我从一个网站的算法,它的运行就好了。现在我想计算算法需要排序一个数组的键比较。我试图通过for循环计数比较,但它似乎是错误的...任何想法,我必须计数吗?
I wrote a little C# command application. Four arrays are supposed to be sorted with a heapsort algorithm. I took an algorithm from a website and its running just fine. Now I want to count the key-comparisons the algorithm needs to sort one array. I tried to count the comparisons via for loop but its seems to be wrong... Any ideas where I have to count for it?
这是我的排序算法方法。 GlobalVar.CountVal
只是一个 public static int
属性。
Here's my sorting algorithm method. GlobalVar.CountVal
is simply a public static int
property.
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;
}
以下是完整代码:
推荐答案
使用这个比较器而不是比较运算符(> =
和<
),可以正确计算比较。 / p>
By using this comparer instead of the comparison operators (>=
and <
), you can count the comparisons properly.
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);
}
}
要使用类似这样的比较器,您的代码:
To use a comparer like this, here's how you modify your code:
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中运行)位于。
Then just make sure that you use this comparer for every comparison in the heapsort (but only in that one sorting). The full code (as I ran in LINQPad) is at http://pastebin.com/UXAQh9B3. I changed your method from hardcoded to generic to more easily identify where the comparer needed to be used.
您的数据的比较计数如下:
The comparison counts for your data are as follows:
1 - 652
2 - 652
3 - 0
4 - 155
这篇关于如何计数堆栈密钥比较的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!