计算递归BubbleSort算法的迭代次数。

Question

我有一个公式来手动做这个？这段代码一定会返回正确的迭代量吗？

int global = 0;
void bubbleSort(int arr[], int n){
    if (n == 1)
        return;
    for (int i = 0; i < n-1; i++){
        if (arr[i] > arr[i+1]) {
            swap(&arr[i], &arr[i+1]);
        }
        global++;
    }
    bubbleSort(arr, n-1);
}

Answer 1

它正确地计算了迭代次数，但是。

• 你需要设置 global 回零后再使用 bubbleSort 第二次。
• 迭代次数是确定的，等于 n(n-1)2.
• 如果在一般情况下，你需要在递归函数中计算迭代次数，你可以让函数 返回 算。对于你的代码，这意味着。

int bubbleSort(int arr[], int n) {
    if (n == 1)
        return 0;
    int count = 0;
    for (int i = 0; i < n-1; i++) {
        if (arr[i] > arr[i+1]) {
            swap(&arr[i], &arr[i+1]);
        }
        count++;
    }
    return count + bubbleSort(arr, n-1);
}

同样的，这对于计数来说也太夸张了 迭代 因为结果是注定的。如果算上 掉期因为这取决于数组数据本身。