-1

我已经编写了堆排序算法，但我很难决定应该将什么视为比较。我认为以下内容会有助于比较，但我获得的结果对我来说似乎很不合适（可能很多？）这是代码

       public class heapsort{
      static int counter = 0;

      public static void main(String[] args) { 
         //int[] a1={1, 16, 2, 3, 14, 4, 5, 12, 7, 10, 8, 9, 17, 19, 21, 23, 26, 27}; 

            int[] a1 = {1, 2};
            System.out.println(sort(a1)); 
         for(int i=0;i<a1.length;i++){ 
            System.out.print(a1[i] + " "); 
         } 
      } 

      private static int[] a; 
      private static int n; 
      private static int left; 
      private static int right; 
      private static int largest;

      public static void buildheap(int[] a){ 
         n= a.length-1; 
         for(int i= n/2; i >= 0; --i){ 
            maxheap(a,i); 
         } 
      } 

      public static void maxheap(int[] a, int i){ 
         left=2*i; 
         right=2*i+1; 
         if(left <= n && a[left] > a[i]){ 
            counter++;
            largest=left; 
         } 
         else{ 
            counter++;
            largest=i; 
         } 

         if(right <= n && a[right] > a[largest]){ 
            counter++;

            largest=right; 
         } 
         if(largest!=i){ 
            counter++;     
            exchange(i,largest); 
            maxheap(a, largest); 
         } 
      } 

      public static void exchange(int i, int j){ 
         int t=a[i]; 
         a[i]=a[j]; 
         a[j]=t; 
      } 

      public static int sort(int []a0){ 
         a=a0; 
         buildheap(a); 

         for(int i=n;i>0; --i){ 
            exchange(0, i); 
            n=n-1; 
            maxheap(a, 0); 
         } 
         return counter;
      }       
   }

我知道一些柜台可能是错误的，建议？

4

2 回答 2

1

您通常只计算元素比较，而不是整数比较，即使数组中的元素是整数。

为了使这更有意义 - 如果您要将数组更改为字符串数组（例如），只需计算字符串比较的次数。字符串比较通常比整数比较昂贵得多（如果你有一个包含许多字段的大对象，情况会更糟），所以只计算这些是有意义的。

所以这些比较元素：

a[left] > a[i]
a[right] > a[largest]

这些只是比较整数：

i >= 0
left <= n
right <= n
largest != i
i > 0

我建议编写一个compare函数来增加你的计数（只需用它替换上面的 2 个元素比较并删除你增加计数的其他地方）。我还建议在函数返回的内容中坚持约定。

您的函数可能看起来像这样：（您必须使用 Java 7 之前的Integer.valueOf(a).compareTo(b)版本）

int compare(int a, int b)
{
  counter++;
  return Integer.compare(a, b);
}

所以a[left] > a[i]会变成compare(a[left], a[i]) > 0，对于另一个也是如此。

Comparator可以提供更通用的解决方案，但在这种情况下可能有点矫枉过正。

于 2013-06-04T07:19:37.363 回答
1

计算数组的比较，有时/总是“a”。例如：“a[left] > a[i]”。您可以为比较添加一个计数器作为全局计数器，并在每次进行比较时 ++ 它以获得比较计数。

顺便说一句，堆排序在理论上很有趣，但它不稳定，通常不如 timsort 快，也没有利用部分排序的数据。

于 2013-06-04T01:54:20.383 回答