計數歸併排序和選擇的操作排序

Question

我想要的排序算法合併排序和選擇排序比較操作的次數，但我有搞清楚一些問題來算，其操作和不..

這裏有我的實現。我想，我指望在正確的道路選擇排序的操作，但我不知道歸併排序：

選擇排序：

public class SelectionSort { 
private int exchanges, comparisons; 

public void selectionSort(int[] x) {  
    for (int i=0; i<x.length-1; i++) { 
     for (int j=i+1; j<x.length; j++) { 
      if (x[i] > x[j]) 
      { 
       //... Exchange elements 
       int temp = x[i]; 
       x[i] = x[j]; 
       x[j] = temp; 
       exchanges++; 
      } 
      comparisons++; 
     } 
    } 
    System.out.println("SelSort_Exchanges: "+exchanges); 
    System.out.println("SelSort_Comparisons: "+comparisons); 
    System.out.println("SelSort_Operations: "+(exchanges+comparisons)); 
} 
} 

如果我把10 INT我的數組得到：

SelSort_Comparisons: 45 
SelSort_Exchanges: 27 
SelSort_Operations: 72 

權在我看來，現在的歸併排序：

public class Mergesort { 
private int[] numbers; 
private int[] helper; 

private int number; 
private int comparisons, exchanges; 

public void sort(int[] values) { 
    this.numbers = values; 
    number = values.length; 
    this.helper = new int[number]; 
    mergesort(0, number - 1); 
    System.out.println("MerSort_Comparisons "+comparisons); 
    System.out.println("MerSort_Exchanges "+exchanges); 
    System.out.println("MerSort_Operations "+(comparisons+exchanges)); 
    System.out.println(); 
} 

private void mergesort(int low, int high) { 
    // Check if low is smaller then high, if not then the array is sorted 
    if (low < high) 
    { 
     // Get the index of the element which is in the middle 
     int middle = (low + high)/2; 
     // Sort the left side of the array 
     mergesort(low, middle); 
     // Sort the right side of the array 
     mergesort(middle + 1, high); 
     // Combine them both 
     merge(low, middle, high); 
    } 
} 

private void merge(int low, int middle, int high) { 

    // Copy both parts into the helper array 
    for (int i = low; i <= high; i++) { 
     helper[i] = numbers[i]; 
     exchanges++; 
    } 
    int i = low; 
    int j = middle + 1; 
    int k = low; 
    // Copy the smallest values from either the left or the right side back 
    // to the original array 
    while (i <= middle && j <= high) { 
     if (helper[i] <= helper[j]) { 
      numbers[k] = helper[i]; 
      i++; 
      exchanges++; 
     } else { 
      numbers[k] = helper[j]; 
      j++; 
      exchanges++; 
     } 
     k++; 
     comparisons++; 

    } 
    // Copy the rest of the left side of the array into the target array 
    while (i <= middle) { 
     numbers[k] = helper[i]; 
     exchanges++; 
     k++; 
     i++; 
    } 
} 
} 

現在我得到

MerSort_Comparisons 22 
MerSort_Exchanges 61 
MerSort_Operations 83 

的結果，但我不知道它的權利。比較的結果對我來說似乎是正確的，但是如果我以20個數組爲例，它看起來不再合適。

任何人都可以幫助我，告訴我在哪裏我必須把我的比較和交換增量？

在此先感謝！ :)

Answer 1

最簡單的方法是創建兩個方法，Compare和Swap，並增加它們內部的計數器。無論你使用什麼sorting algorithm，它只應該使用這些方法與數組進行交互。

另外，this page可以幫助您直觀地分析不同的排序算法。