1

我想知道如何计算我在 Rosettacode 上得到的 HeapSort 进行的比较次数？我试图通过添加一个变量来计算它，每次调用比较方法时，这个变量都会增加。但不知何故，我没有得到正确的结果。我想我必须以某种方式覆盖比较方法并使用 getter 和 setter 来增加计数变量。一个提示将不胜感激......

using System;
using System.Collections.Generic;
using System.Text;


public class Program
{
    public static void HeapSort<T>(T[] array)
    {
        HeapSort<T>(array, 0, array.Length, Comparer<T>.Default);
    }

    public static void HeapSort<T>(T[] array, int offset, int length, IComparer<T> comparer)
    {
        HeapSort<T>(array, offset, length, comparer.Compare);
    }

    public static void HeapSort<T>(T[] array, int offset, int length, Comparison<T> comparison)
    {
        int count = 0;
        // build binary heap from all items
        for (int i = 0; i < length; i++)
        {
            int index = i;
            T item = array[offset + i]; // use next item

            // and move it on top, if greater than parent
            while (index > 0 &&
                comparison(array[offset + (index - 1) / 2], item) < 0)
            {
                int top = (index - 1) / 2;
                array[offset + index] = array[offset + top];
                index = top;
            }
            count++;
            array[offset + index] = item;
            //Console.WriteLine(item);
        }

        for (int i = length - 1; i > 0; i--)
        {
            // delete max and place it as last
            T last = array[offset + i];
            array[offset + i] = array[offset];

            int index = 0;

            // the last one positioned in the heap
            while (index * 2 + 1 < i)
            {

                int left = index * 2 + 1, right = left + 1;

                if (right < i && comparison(array[offset + left], array[offset + right]) < 0)
                {
                    if (comparison(last, array[offset + right]) > 0)
                    {
                        break;
                    }

                    array[offset + index] = array[offset + right];
                    index = right;

                    //Console.WriteLine("1st if ");

                }
                else
                {

                    if (comparison(last, array[offset + left]) > 0)
                    {
                        break;
                    } 
                    count++;

                    array[offset + index] = array[offset + left];
                    index = left;

                    //Console.WriteLine("2nd if ");

                }
            }
            array[offset + index] = last;

            //Console.WriteLine("\nRun");
            //for (int j = 0; j <= 3; j++)
            //    Console.WriteLine(array[j]);
        }
        Console.WriteLine("\nThe case needed " + count + " comparisons!");
    }

    static void Main()
    {
        // hardcoded arrays according to the assignment
        int[] arrOne = { 503, 087, 512, 061, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703 };
        int[] arrTwo = { 908, 897, 765, 703, 677, 653, 612, 512, 509, 503, 426, 275, 170, 154, 087, 061 };
        int[] arrThree = { 4, 7, 2, 3 };
        int[] arrFour = { 0, 1, 0, 0, 1, 1, 1, 0, 1, 0 };
        int n = 0;
        string c = String.Empty;

        // the application runs until the user agrees to quit at the end of a sorting run
        do
        {
            // displays the 4 arrrays
            Console.WriteLine("Assignment: Given are 4 different arrays; You have the choice which one you want to sort.");
            Console.WriteLine("\n1. Knuths entry sequence:\n   503,087,512,061,908,170,897,275,653,426,154,509,612,677,765,703");
            Console.WriteLine("\n2. Knuths entry sequence descended:\n   908,897,765,703,677,653,612,512,509,503,426,275,170,154,087,061");
            Console.WriteLine("\n3. Just one number:\n   300");
            Console.WriteLine("\n4. A set of 0 and 1:\n   0,1,0,0,1,1,1,0,1,0");
            Console.WriteLine("\n Which array do you want to sort?");
            n = Convert.ToInt32(Console.ReadLine());
            // creating an comparer instance
            //var comp = new CountingComparer<int>();
            Console.Clear();

            switch (n)
            {
                case 1:
                    HeapSort(arrOne);
                    DisplayArray(arrOne);
                    break;
                case 2:
                    HeapSort(arrTwo);
                    DisplayArray(arrTwo);
                    break;
                case 3:
                    HeapSort(arrThree);
                    DisplayArray(arrThree);
                    break;
                case 4:
                    HeapSort(arrFour);
                    DisplayArray(arrFour);
                    break;
                default:
                    Console.WriteLine("\nArray does not exist!");
                    break;
            }

            //Console.WriteLine("\nThe case needed " + comp.Count + " comparisons!");
            Console.WriteLine("\nDo you want to quit the application? (y/n) ");
            c = Console.ReadLine();
            Console.Clear();

        }
        while (c != "y");
    }

    public static void DisplayArray(int[] arr)
    {
        Console.WriteLine("\nSorted Array!\n");

        for (int i = 0; i < arr.Length; i++)
            Console.WriteLine("   " + arr[i]);
    }
}
4

1 回答 1

0

我认为在比较方法中进行计数是个好主意。这是一种快速而肮脏的方法：

public class Program
{
  public static int Count = 0;
  public static int MyCompare<T>(T first, second)
  {
    Count++;
    return Comparer<T>.Default.Compare(first, second);
  }
  // Update your first sort to use the new compare.
  public static void HeapSort<T>(T[] array)
  {
    HeapSort<T>(array, 0, array.Length, MyCompare);
  }
  // Now all of the rest of your original code inside of Program.
}

在调用排序之前设置Count为 0，然后在排序完成后读取计数。我确认在第一次排序时，它确实设置为 85，如您所料。

于 2013-11-13T17:56:57.350 回答