合并排序比较计数器

我似乎无法弄清楚我的比较计数器放在合并类的位置。虽然它完美地对数组进行排序，但它不会计算它所做交换（或比较）的次数。请帮助，这是我的除了最后的项目合并排序比较计数器

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

    } 

    return comparisons; 

    } 

    public static int Merge(int[] intArray, int first, int mid, int last) { 

    //int count = 0; 
    comparisons = 0; 
    int first1 = first, last1 = mid; 
    int first2 = mid + 1, last2 = last; 
    int temp[] = new int[intArray.length]; 
    int index = first1; 

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

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

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

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


    return comparisons; 
    }

来源

2013-05-07 KyleG

你从别人复制这个代码？与编写mergeSort – 2013-05-07 00:03:24

的任务相比，放置“比较”的地方是微不足道的。还记得仅仅因为您缩进，并不意味着代码将会在没有正确括号的情况下执行。你的其他人缺少parens。 – greedybuddha 2013-05-07 01:27:20

在你这里包括，你没有表现出可变comparisons定义的代码，但因为你使用它没有定义它，我假设这是你班上的一个领域。如果是这样的话，我认为这个问题是这一行Merge：

comparisons = 0;

既然你做比较的数量的一个全局计数器，这条线的存在意味着，只要您拨打Merge，你即使在执行mergesort的过程中，您已经进行了一堆比较，将总数比较重置为零。

作为一个快速修复，只需删除这一行。不过，我认为你最好是通过不把它作为一个字段来解决这个问题，并使用返回值来反馈所做比较的次数。下面是做到这一点的一种方法：

public static int mergeSort(int[] intArray, int first, int last) { 
    int compares = 0; 
    if(first < last) { 
     int mid = (first + last)/2; 
     compares += mergeSort(intArray, first, mid); 
     compares += mergeSort(intArray, mid + 1, last); 
     compares += Merge(intArray, first, mid, last); 

} 

return compares;

}

公共静态INT合并（INT [] intArray，诠释第一，诠释中旬，INT去年）{ INT比较= 0; int first1 = first，last1 = mid; int first2 = mid + 1，last2 = last; int temp [] = new int [intArray.length]; int index = first1;

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

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

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

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


return comparisons;

}

来源

2015-08-26 17:09:38 templatetypedef

合并排序比较计数器

回答

相关问题