2

我正在编写一个计算合并排序和快速排序操作的程序。我不知道我应该把count++放在哪里；（计算操作）。有人可以帮我吗？

以下是合并排序和快速排序的代码。

合并排序：

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.

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++)];
        else
        temp[copied++] = data[first + n1 + (copied2++)];
    }

    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.

这是快速排序的代码：

public void quickSort(int data[], int left, int right){

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

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++;
        while (data[j] > pivot)
        j--;
        if (i <= j)
        {

            tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
            i++;
            j--;
        }
    }
    return i;
}//ends partition method.
4

3 回答 3

4

您应该将++“操作”放在任何地方。你所说的操作取决于你。我可以是一个比较，一个交换或每一行。你可以决定什么是适合你的。

于 2012-10-01T18:47:57.080 回答
1

假设您正在进行“大 O”分析，您的“操作计数”是最内层循环的迭代次数。

  • 对于您的 QuickSort 示例，这很简单：将您的计数器放在后面while (i <= j)
  • 对于您的 MergeSort 示例，您需要将计数器放在每个while循环中（我没有仔细查看这些循环，但它们似乎做的远远超出了必要的范围）。

此计数不会告诉您正在执行的实际操作数，而只是“大 O”操作数。虽然 MergeSort 和 QuickSort 可能具有相同的“大 O”特征（因此应该具有相似的计数），但在最内层循环内完成的工作量会有所不同。

于 2012-10-01T19:57:25.623 回答
1

在合并排序中，下面的方法正是做这些事情的方法：-

merge(data,first,n1,n2);

所以，把一个计数++放在那里..

快速排序..它是：-

partition(data, left, right)

因此，在此处添加count++ ..

您的其他方法调用： -mergesort()并且quicksort()只是递归调用..它们最终只会导致上述两个methods..

但最终这一切都取决于你的意思我的“计算操作”。你认为是什么operation是至关重要的。

它可能是一个method execution，或者every statement可以是一个操作..或者你的循环..它可以意味着任何东西..

于 2012-10-01T18:47:56.917 回答