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。