如果这两个bubble-sort实现的步骤数和交换数相似,为什么它们在运行时显著不同?

我试图在C语言中实现冒泡排序。 I've done so in this gist.

我实现了维基百科文章中关于气泡排序的算法, sort_bubble ,并将其与我在github上找到的引用实现进行了比较, bubble_sort :

typedef struct Bubble_Sort_Stats {
    int num_swaps;
    int num_steps;
} bubble_sort_stats_t;

bubble_sort_stats_t bubble_sort(int arr[], int n) {
    bubble_sort_stats_t stats;
    stats.num_swaps = 0;
    stats.num_steps = 0;

    int temp;
    int i;
    int j;

    while (i < n) {
        j = 0;
        while (j < i) {
            stats.num_steps++;
            if (arr[j] > arr[i]) {
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
                stats.num_swaps++;
            }
            j++;
        }
        i++;
    }
    return stats;
}

bubble_sort_stats_t sort_bubble(int array[], int length_of_array) {
    bubble_sort_stats_t stats;
    stats.num_swaps = 0;
    stats.num_steps = 0;

    int n = length_of_array;
    int new_n;
    while (n >= 1) {
        new_n = 0;
        for (int i = 0; i < n - 1; i++) {
            stats.num_steps++;

            if (array[i] > array[i+1]) {
                int l = array[i];
                stats.num_swaps++;
                new_n = i + 1;
                array[i] = array[i + 1];
                array[i + 1] = l;
            }
        }
        n = new_n;
    }

    return stats;
}

#define BIG 10000

int main() {
    int nums1[BIG], nums2[BIG];
    for (int i = 0; i < BIG; i++) {
        int newInt = rand() * BIG;;
        nums1[i] = newInt;
        nums2[i] = newInt;
    }

    long start, end;
    bubble_sort_stats_t stats;

    start = clock();
    stats = bubble_sort(nums2, BIG);
    end = clock();
    printf("It took %ld ticks and %d steps to do %d swaps\n\n", end - start, stats.num_steps, stats.num_swaps);

    start = clock();
    stats = sort_bubble(nums1, BIG);
    end = clock();
    printf("It took %ld ticks and %d steps to do %d swaps\n\n", end - start, stats.num_steps, stats.num_swaps);

    for (int i = 0; i < BIG; i++) {
        if (nums1[i] != nums2[i]) {
            printf("ERROR at position %d - nums1 value: %d, nums2 value: %d", i, nums1[i], nums2[i]);
        }

        if (i > 0) {
            if (nums1[i - 1] > nums1[i]) {
                printf("BAD SORT at position %d - nums1 value: %d", i, nums1[i]);
            }
        }
    }

    return 0;
}

现在,当我运行这个程序时,会得到以下结果:

It took 125846 ticks and 49995000 steps to do 25035650 swaps

It took 212430 ticks and 49966144 steps to do 25035650 swaps

也就是说,互换的数量是相同的,并且 肥皂泡 实际上 较少的 步数,但是这个数组的长度几乎是它的两倍!

我的怀疑是,这种差异与控制结构本身、指数等有关。但是我对C编译器的工作原理了解得还不够,我甚至不知道如何通过调试来确定这一点。

所以我想知道为什么,同时也想知道我是如何从经验上解决这个问题的。