java排序方法在哪裏比較？

Question

問題：在每個單獨的排序方法中進行比較的地方在哪裏？
另外，如果你知道，請告訴我哪些方法計數是錯誤的，以及在哪裏放置我的計數器。試着瞭解排序方法進行比較的位置和次數。

Method  A  B 
Selection 4950  4950 
Bubble  99  9900 
Insertion  99  5049 
Merge   712  1028 
Shell   413  649 
Quick  543  1041 

好了解釋一些部分，基本上Array A是一個從1到100的數組，從小到大排列順序。所以這應該是最少的比較次數。
數組B按100-1降序排列。所以我相信它應該是最大數量的比較。數組C只是隨機生成的數字，因此每次都會更改。

我覺得我的選擇和冒泡排序都被正確計算。隨時讓我知道哪些比較正在進行，我還沒有計算在內，或者如果我計算錯誤的比較。

備註：使用一些全局變量來計算多節中遞歸的方法。

class Sorting 
    { 
     static int[] X = new int[100]; 
     static int mergecount = 0; 
     static int quickcount = 0; 
     public static void selectionSort(int list[]) 
     { 
     int count = 0; 
     int position = 0, n = list.length; 
     for(int j = 0; j < n-1; j++) 
     { 
      position = j; 
      for(int k = j+1; k < n; k++) 
      { 
       count++; 
       if(list[k] < list[position]) 
        position = k; 
      } 
      Swap(list, j, position); 
     } 
     System.out.println("counter" + count); 
     } 

    public static void Swap(int list[], int j, int k) 
    { 
    int temp = list[j]; 
    list[j] = list[k]; 
    list[k] = temp; 
    } 

    public static void bubbleSort(int list[]) 
    { 
    int count = 0; 
    boolean changed = false; 
    do 
    { 
     changed = false; 
     for(int j = 0; j < list.length - 1; j++) 
     { 
      count++; 
      if(list[j] > list[j + 1]) 
      { 
       Swap(list, j, j+1); 
       changed = true; 
      } 
     } 
    } while(changed); 
    System.out.println("counter" + count); 
    } 

    public static void insertionSort(int list[]) 
    { 
    int count = 0; 
    for(int p = 1; p < list.length; p++) 
    { 
     int temp = list[p]; 
     int j = p; 
     count++; 
     for(; j > 0 && temp < list[j - 1]; j = j-1) 
     { 
      list[j] = list[j - 1]; 
      count++; 
     } 
     list[j] = temp; 
    } 
    System.out.println("counter" + count); 
    } 

    public static void mergeSort(int list[]) 
    { 
    mergeSort(list, 0, list.length - 1); 
    System.out.println("counter" + mergecount); 
    } 

    public static void mergeSort(int list[], int first, int last) 
    { 
    if(first < last) 
    { 
     int mid = (first + last)/2; 
     mergeSort(list, first, mid); 
     mergeSort(list, mid + 1, last); 
     Merge(list, first, mid, last); 
    } 

    } 

    public static void Merge(int list[], int first, int mid, int last) 
    { 
    int count = 0; 
    int first1 = first, last1 = mid; 
    int first2 = mid + 1, last2 = last; 
    int temp[] = new int[list.length]; 
    int index = first1; 

    while(first1 <= last1 && first2 <= last2) 
    { 
     if(list[first1] < list[first2]) 
     { 
      temp[index] = list[first1++]; 
      mergecount++; 
     } 
     else 
      temp[index] = list[first2++]; 
     index++; 
     mergecount++; 
    } 

    while(first1 <= last1) 
     temp[index++] = list[first1++]; 

    while(first2 <= last2) 
     temp[index++] = list[first2++]; 

    for(index = first; index <= last; index++) 
     list[index] = temp[index]; 


    } 

    public static void shellSort(int list[]) 
    { 
    int count = 0; 
    int n = list.length; 
    for(int gap = n/2; gap > 0; gap = gap == 2 ? 1: (int) (gap/2.2)) 
     for(int i = gap; i < n; i++) 
     { 
      int temp = list[i]; 
      int j = i; 
      count++; 
      for(; j >= gap && (temp < (list[j - gap])); j -= gap) 
      { 
       list[j] = list[j - gap]; 
       count++; 
      } 

      list[j] = temp; 
     } 
    System.out.println("counter" + count); 
    } 

    public static void quickSort(int start, int finish, int list[]) 
    { 
    int count = 0; 
    int left = start, right = finish, pivot, temp; 
    pivot = list[(start + finish)/2]; 
    do 
    { 
     while(list[left] < pivot) 
     { 
      left++; 
      quickcount++; 
     } 

     while(pivot < list[right]) 
     { 
      right--; 
      quickcount++; 
     } 

     if(left <= right) 
     { 
      temp = list[left]; 
      list[left++] = list[right]; 
      list[right--] = temp; 
      quickcount++; 
     } 
    } while(left < right); 

    if(start < right) 
     quickSort(start, right, list); 


    if(left < finish) 
     quickSort(left, finish, list); 

    } 

    public static void copy(int list[]) 
    { 
    for(int i = 0; i < list.length; i++) 
     X[i] = list[i]; 
    } 

    public static void restore(int list[]) 
    { 
    for(int i = 0; i < list.length; i++) 
     list[i] = X[i]; 
    } 

    public static void displayArray(int list[]) 
    { 
    for(int k = 0; k < list.length; k++) 
     System.out.print(list[k] + " "); 
    System.out.println(); 
    } 

    public static void main(String args[]) 
    { 
    int[] A = new int[100]; 
    for(int i = 0; i < A.length; i++) 
     A[i] = i + 1; 

    int[] B = new int[100]; 
    int q = 100; 
    for(int i = 0; i < B.length; i++) 
     B[i] = q--; 

    int[] C = new int[100]; 
    for(int i = 0; i < C.length; i++) 
     C[i] = (int)(Math.random() * 100 + 1); 

    displayArray(A); 
    copy(A); 
    selectionSort(A); 
    displayArray(A); 
    restore(A); 
} 

Answer 1

請注意，QuickSort性能受您選擇的數據透視的影響很大。隨着你的測試數組排序（升序/降序），並且因爲你選擇數組[長度/ 2]作爲樞軸，你實際上總是選擇最佳樞軸。所以你的測試用例B不會爲快速排序產生最大數量的比較。如果您選擇array [0]作爲關鍵點，則可以獲得測試用例A和B的最大比較次數。

計數比較最簡單的方法是使用比較函數並在那裏進行比較。

static int compareCount = 0; 
int compareInt(int a, int b) { 
    compareCount++; 
    return a - b; // if 0 they are equal, if negative a is smaller, if positive b is smaller 
} 

現在只需在所有算法中使用compareInt，就可以得到準確的計數。你必須在每次運行之間重置compareCount。