如何计算和返回算法中的掉期-MergeSort和QuickSort？

Question

我有用于快速排序的代码

int sum = 0;
int partition(int *L, int left, int right) {
        int pivot = left;
        int p_val = L[pivot];
        while (left < right) {
            while (L[left] <= p_val)
                left++;
            while (L[right] > p_val)
                right--;
            if (left < right) {
                swap(&L[left], &L[right]);
                sum++;
                }
            }
        swap(&L[pivot], &L[right]);
        sum++;
        return right;
        }

    void quicksort(int *L, int start, int end) {
        if (start >= end)
            return;
        int splitPoint = partition(L, start, end);
        quicksort(L, start, splitPoint - 1);
        quicksort(L, splitPoint + 1, end);
        }

而且我认为它很好用。对于给定的数组{8,4,2,1}，我已经进行了3次交换。但是，我需要修改代码，以便函数RETURNS交换数量。这可能吗？如果可以，怎么办？请尽您所能，因为我是新手。我需要对mergeSort进行相同的操作，但是我仍然没有找到不太复杂的工作代码。当我这样做时，我将更新问题。谢谢。

Answer 1

您可以将int指针用作partition和quicksort函数的参数：

int partition(int *num, int *L, int left, int right) {
    ...
    if (left < right) {
       swap(&L[left], &L[right]);
       (*num)++; // increment number of swap
       sum++;
       }
    }
    ...
}

并且在quicksort函数中：

void quicksort(int *num, int *L, int start, int end) {
  if (start >= end)
      return;
  int splitPoint = partition(num, L, start, end);
  quicksort(num, L, start, splitPoint - 1);
  quicksort(num, L, splitPoint + 1, end);
}

然后在主要功能中：

int main() 
{ 
    int arr[] = {8, 4, 2, 4, 5, 7, 8, 9, 1}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int num = 0;
    quicksort(&num, arr, 0, n-1); 
    printf("sum = %d num = %d\n", sum, num);
    return 0; 
}