計算選擇排序中的交換次數

我已閱讀所有試圖找到答案的討論，但沒有任何答案對我有效，因此我正在以此方式嘗試。計算選擇排序中的交換次數

public static int SelectionSort(long[] num) 
{ 
    int i, j, first; 
    long temp; 
    int swap = 0; 
    int pass = 0; 
    int count = 0; 
    boolean Mini = false; 

    for (i = num.length - 1; i &gt; 0; i--) 
    { 
     for(int k = 0; k &lt; num.length; k++) 
     { 
      System.out.println(" k = " + k 
      + " \t X[i] = " + num[k] + " swap count: " + swap); 
     } 
     System.out.println(""); 
     first = 0; //initialize to subscript of first element 
     for(j = 1; j &lt;= i; j ++) //locate smallest element between positions 1 and i. 
     { 
      if(num[j] &lt; num[first]) 
      { 
       first = j; 
       //Mini = true; 
      } 
     } 

     //if(Mini){ 
      // swap++; 
     //} 
     temp = num[first]; //swap smallest found with element in position i. 
     num[first] = num[i]; 
     num[i] = temp; 
    } 
    return swap; 
}

使用一個簡單的數組作爲我的測試案例：

long[] X = {1, 4, 3, 2, 5};

互換的數量應該只等同於1，因爲它只是交換的第一和最後一個元素。但是，它不起作用。雖然我知道如果條件不起作用，我想不出會發生什麼。我似乎無法使用它實際交換項目時增加交換的邏輯。

來源

2014-02-09 tjg92

爲什麼在實際執行交換時不增加計數器？

//swap smallest found with element in position i. 
swap++ 
temp = num[first]; 
num[first] = num[i]; 
num[i] = temp;

編輯：
在評論好一點。如果數組排序當前的代碼仍然執行一個多餘的交換（即first和i相同）：

if (first != i) { 
    swap++ 
    temp = num[first]; 
    num[first] = num[i]; 
    num[i] = temp; 
}

來源

2014-02-09 20:50:27 Mureinik

唯一的問題是程序每次都會增加交換。我只希望它在交換時增加。現在如果我增加交換，它會給我一個4的交換。它應該只給我一個交換1. – tjg92

是的！工作！非常感謝！ – tjg92

您的實現，你將永遠有n個掉期（其中n是元素的個數您數組）。

我認爲你想要的只是當它實際上有所作爲時才進行交換......所以當「第一個」和「我」具有不同的值時。否則，你用自己切換元素。

if (first != i) { 
    temp = num[first]; 
    num[first] = num[i]; 
    num[i] = temp; 
    swapp++; 
    }

來源

2014-02-09 20:53:42 Preli

計算選擇排序中的交換次數

回答

相關問題