-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」の配列の比較を数えます。例: "a[左] > a[i]". 比較用のカウンターをグローバルとして追加し、比較を行うたびに ++ して比較カウントを取得できます。

ところで、ヒープソートは理論的には興味深いものですが、安定しておらず、一般に timsort ほど高速ではなく、部分的にソートされたデータも利用していません。

于 2013-06-04T01:54:20.383 に答える