當考慮堆比較時，你認爲什麼是比較？

-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; 
     }  
    }

我知道有些計數器可能是錯的，建議？

來源

2013-06-04 Ceelos

這是不是很清楚你在這裏問什麼。 –

關鍵是要找出算法的有效性。手工操作時，必須對數組中的值進行比較。我何時應該考慮進行比較，以便可以在比較計數中加上+1？這是爲了找到算法的最佳情況和最壞情況 – Ceelos

好吧;您的問題中沒有任何內容描述您正在嘗試**計數**比較的事實。 –

計數數組的比較，有時/總是「a」。 EG：「a [left]> a [i]」。您可以爲比較添加一個計數器作爲全局值，每當您進行比較以獲取比較值時，都可以使用++計數器。

順便說一下，堆排序在理論上很有趣，但它不穩定，一般不像timsort那麼快，也不會利用部分排序的數據。

來源

2013-06-04 01:54:20 dstromberg

這是實際解決方案中更好的方法。原來，我們典型的堆排序算法有時會遺漏或增加我們手動完成的比較。答案真的取決於手動執行算法，而不是在計算機上運行。感謝您的意見，但它給了我一個更好的主意。 – Ceelos

儘管數組中的元素是整數，但通常只計算元素比較，而不是整數比較。

爲了讓這更有意義 - 如果要將數組更改爲字符串數組（例如），只需計算字符串比較的數量。字符串比較通常比整數比較方式更昂貴（如果你有一個包含很多字段的大對象，那麼它更是如此），所以只有對這些進行計數纔有意義。

因此，這些比較元素：

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

這些只是比較整數：

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

我建議寫一個compare功能也增加了你的計數（和剛剛更換上述2元比較與它並刪除其他地方，你增加了計數）。我還建議堅持convention函數返回。

你的功能只是看起來像這樣：（預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，以及類似的其他一個。

A Comparator會爲更通用的解決方案，但它可能在這種情況下有點矯枉過正。

來源

2013-06-04 07:19:37 Dukeling

當考慮堆比較時，你認爲什麼是比較？

回答

相關問題