我需要帮助计算这些函数所做的比较次数。我已经声明了一个变量compCount，它存储比较的数量，但请帮助找出将compCount++增量放在哪里。
我理解你在做比较函数时放置计数增量器，但也有像这样复杂的循环：
for (i = low, j = high - 1;;) {
while (a[++i].compareTo(pivot) < 0) {
}
while (pivot.compareTo(a[--j]) < 0) {
}
if (i >= j) {
break;
}
swapReferences(a, i, j);
}
以及在insertionSort((函数中
这是代码：
public class QuickSort implements Sort {
long compCount;
/**
* Quicksort algorithm.
*
* @param a an array of Comparable items.
*/
@SuppressWarnings("rawtypes")
public void QuickSort(Comparable[] a) {
compCount = 0;
sort(a);
}
private static final int CUTOFF = 10;
/**
* Method to swap to elements in an array.
*
* @param a an array of objects.
* @param index1 the index of the first object.
* @param index2 the index of the second object.
*/
public static void swapReferences(Object[] a, int index1, int index2) {
Object tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
/**
* Internal quicksort method that makes recursive calls. Uses median-of-three
* partitioning and a cutoff of 10.
*
* @param a an array of Comparable items.
* @param low the left-most index of the subarray.
* @param high the right-most index of the subarray.
*/
@SuppressWarnings({ "rawtypes", "unchecked" })
private void quicksort(Comparable[] a, int low, int high) {
if (low + CUTOFF > high)
insertionSort(a, low, high);
else {
// Sort low, middle, high
int middle = (low + high) / 2;
if (a[middle].compareTo(a[low]) < 0) {
swapReferences(a, low, middle);
}
if (a[high].compareTo(a[low]) < 0) {
swapReferences(a, low, high);
}
if (a[high].compareTo(a[middle]) < 0) {
swapReferences(a, middle, high);
}
// Place pivot at position high - 1
swapReferences(a, middle, high - 1);
Comparable pivot = a[high - 1];
// Begin partitioning
int i, j;
for (i = low, j = high - 1;;) {
while (a[++i].compareTo(pivot) < 0) {
}
while (pivot.compareTo(a[--j]) < 0) {
}
if (i >= j) {
break;
}
swapReferences(a, i, j);
}
// Restore pivot
swapReferences(a, i, high - 1);
quicksort(a, low, i - 1); // Sort small elements
quicksort(a, i + 1, high); // Sort large elements
}
}
/**
* Internal insertion sort routine for subarrays that is used by quicksort.
*
* @param a an array of Comparable items.
* @param low the left-most index of the subarray.
* @param n the number of items to sort.
*/
@SuppressWarnings({ "unchecked", "rawtypes" })
private void insertionSort(Comparable[] a, int low, int high) {
for (int p = low + 1; p <= high; p++) {
Comparable tmp = a[p];
int j;
for (j = p; j > low && tmp.compareTo(a[j - 1]) < 0; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
@SuppressWarnings("rawtypes")
@Override
public void sort(Comparable[] a) {
// TODO Auto-generated method stub
compCount = 0;
quicksort(a, 0, a.length - 1);
}
@Override
public long getCompares() {
// TODO Auto-generated method stub
return compCount;
}
}
好吧，多亏了我的朋友，我才明白了。事实证明，你应该计算if语句之外的比较，而不是内部的比较，还有一些条件我错过了：
这是代码：
public class QuickSort implements Sort {
long compCount;
/**
* Quicksort algorithm.
*
* @param a an array of Comparable items.
*/
@SuppressWarnings("rawtypes")
public void QuickSort(Comparable[] a) {
compCount = 0;
sort(a);
}
private static final int CUTOFF = 10;
/**
* Method to swap to elements in an array.
*
* @param a an array of objects.
* @param index1 the index of the first object.
* @param index2 the index of the second object.
*/
public static void swapReferences(Object[] a, int index1, int index2) {
Object tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
/**
* Internal quicksort method that makes recursive calls. Uses median-of-three
* partitioning and a cutoff of 10.
*
* @param a an array of Comparable items.
* @param low the left-most index of the subarray.
* @param high the right-most index of the subarray.
*/
@SuppressWarnings({ "rawtypes", "unchecked" })
private void quicksort(Comparable[] a, int low, int high) {
if (low + CUTOFF > high) {
insertionSort(a, low, high);
}
else {
// Sort low, middle, high
int middle = (low + high) / 2;
if (a[middle].compareTo(a[low]) < 0) {
swapReferences(a, low, middle);
}
compCount++;
if (a[high].compareTo(a[low]) < 0) {
swapReferences(a, low, high);
}
compCount++;
if (a[high].compareTo(a[middle]) < 0) {
swapReferences(a, middle, high);
}
compCount++;
// Place pivot at position high - 1
swapReferences(a, middle, high - 1);
Comparable pivot = a[high - 1];
// Begin partitioning
int i, j;
for (i = low, j = high - 1;;) {
while (a[++i].compareTo(pivot) < 0) {
compCount++;
}
compCount++;
while (pivot.compareTo(a[--j]) < 0) {
compCount++;
}
compCount++;
if (i >= j) {
break;
}
swapReferences(a, i, j);
}
// Restore pivot
swapReferences(a, i, high - 1);
quicksort(a, low, i - 1); // Sort small elements
quicksort(a, i + 1, high); // Sort large elements
}
}
/**
* Internal insertion sort routine for subarrays that is used by quicksort.
*
* @param a an array of Comparable items.
* @param low the left-most index of the subarray.
* @param n the number of items to sort.
*/
@SuppressWarnings({ "unchecked", "rawtypes" })
private void insertionSort(Comparable[] a, int low, int high) {
for (int p = low + 1; p <= high; p++) {
Comparable tmp = a[p];
int j;
for (j = p; j > low && tmp.compareTo(a[j - 1]) < 0; j--) {
compCount++;
a[j] = a[j - 1];
}
if(j > low)
compCount++;
a[j] = tmp;
}
}
@SuppressWarnings("rawtypes")
@Override
public void sort(Comparable[] a) {
// TODO Auto-generated method stub
compCount = 0;
quicksort(a, 0, a.length - 1);
}
@Override
public long getCompares() {
// TODO Auto-generated method stub
return compCount;
}
}