0

我正在编写一个程序来计算每种排序方法中的操作。我在这里计算的是数组中两个值之间的比较。那么有人可以检查我是否正确放置了 count[]++ 吗？

排序方法：

public void selectionSort (int [] data) {
    int mindex,
           tmp;

    for (int x = 0; x <= data.length-2; x++) {
        mindex = x;

        for (int y = x+1; y <= data.length-1; y++) {
            if (data [y] < data[mindex]){
                mindex = y;                     
            }
            count[0]++;// counts the operations for selectionSort method.
        }//ends for (int y=x+1;...).

    tmp = data[x];
    data[x] = data[mindex];
    data[mindex] = tmp;

    }//ends for (int x = 0;...).     
 }//ends selectionSort method.

/*
 * insertionSort method that sorts the array by using the insertionsort algorithm and counts the operations. 
 */
public void insertionSort(int [] data){
    int x,
        y,
        tmp;

    for (x = 1; x < data.length; x++){
        tmp = data[x];           
        for (y = x; y > 0 && data[y-1] > tmp; y--,count[1]++){ // count[1] counts the operations for insertionSort method.  
            data[y] = data[y-1];               
        }//ends for (y=x;...). 

        data[y] = tmp;               
    }//ends for(x=1;...).

}//ends insertionSort method.

/*
 * mergeSort method that sorts the array by using the mergesort algorithm.
 */
public void mergeSort(int [] data, int first, int n){
    int n1;
    int n2;

    if (n>1) {
        n1 = n/2;
        n2 = n-n1;
        mergeSort(data,first,n1);
        mergeSort(data,first+n1,n2);
        merge(data,first,n1,n2);
    }         
}//ends mergeSort method.

/*
 * merge method that is called by mergeSort method to sort the array and counts the operations. 
 */
public void merge(int [] data, int first, int n1, int n2){
    int [] temp = new int[n1+n2];
    int copied = 0, copied1 = 0, copied2 = 0, i;

    while((copied1<n1) && (copied2<n2)){
        if(data[first+copied1] < data[first + n1 + copied2]){
            temp[copied++] = data[first + (copied1++)];
            count[2]++;//counts the operations for mergeSort method.
        } else {
            temp[copied++] = data[first + n1 + (copied2++)];
            count[2]++; // counts the operations for mergeSort method.
          }
    }// ends while.

    while (copied1<n1)
        temp[copied++] = data[first + (copied1++)];
    while(copied2<n2)
        temp[copied++] = data[first + n1 + (copied2++)];

    for (i=0;i<n1+n2;i++)
        data[first+i] = temp[i];
}//ends merge method.

/*
 * quickSort method that sorts the array by using the quicksort algorithm.
 */
public void quickSort(int data[], int left, int right)
{
      int index = partition(data, left, right);// Creates an integer variable (index) and calls partition method to find the index value.

      if (left < index - 1){
            quickSort(data, left, index - 1);    
      }
      if (index < right){
            quickSort(data, index, right);
      }
}//ends quickSort method.

/*
 * partition method that is called by quickSort to sort the array and counts the operations. 
 */
int partition(int data[], int left, int right){

  int i = left, j = right;
  int tmp;
  int pivot = data[(left + right) / 2];

  while (i <= j)
  {
        while (data[i] < pivot) {
              i++;
              count[3]++;// counts the operations for quickSort method.
        }// ends while loop.

        while (data[j] > pivot) {
              j--;
              count[3]++;// counts the operations for quickSort method.
        }// ends while loop.

        if (i <= j)
        {
              tmp = data[i];
              data[i] = data[j];
              data[j] = tmp;
              i++;
              j--;
        }// ends if.

  }// ends while loop.
  return i;// returns i value to the method.
}//ends partition method.
4

1 回答 1

2

由于您的问题未标记为作业，因此我假设您主要想了解在排序过程中进行了多少比较。为此，我会

  • 不是重新发明排序，而是使用 Java 库中的高效排序
  • 使用自己的 Comparator 来装饰现有的 compare() 或 compareTo() 来计算比较次数。
于 2012-10-07T15:14:32.830 回答