时间戳

首页 > 解决方案 > 如何计算和返回算法中的交换 - MergeSort 和 QuickSort？

c - 如何计算和返回算法中的交换 - MergeSort 和 QuickSort？

问题描述

我有这个快速排序的代码

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 次交换。但是，我需要修改代码，以便函数返回交换次数。这可能吗？如果可以，怎么做？请尽可能简单地解释，因为我是这方面的新手。我需要对 mergeSort 做同样的事情，但我仍然没有找到不太复杂的工作代码。当我这样做时，我会更新问题。谢谢你。

标签： calgorithmsortingquicksortmergesort

解决方案

您可以将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++;
       }
    }
    ...
    swap(&L[pivot], &L[right]);
    (*num)++;
    sum++;
    return right;
}

在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; 
}

推荐阅读