如果这两个bubble排序实现的步骤和交换数量相似，为什么它们在运行时会有显著差异

Question

我试图在C中实现冒泡排序。

我实现了维基百科文章中关于气泡排序的算法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 swapsnn", 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 swapsnn", 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

也就是说，交换的数量是相同的，sort_bubble实际上只需要更少的步骤，但对于这种大小的数组来说，它几乎需要两倍的时间！

我怀疑这种差异与控制结构本身、指数等有关。但我对c编译器的工作原理还不太了解，无法进一步猜测，甚至不知道如何通过调试来确定这一点。

所以我想知道为什么，但也想知道我如何从经验上弄清楚这一点。

Answer 1

您的bubble_sort实际上不是一个冒泡排序：它不仅比较相邻的对。

这是一种插入排序，内部循环奇怪地反转，仍然可以按预期工作。它可以按如下方式重写，而无需更改步骤或交换的数量。

bubble_sort_stats_t bubble_sort(int arr[], int n) {
bubble_sort_stats_t stats;
stats.num_swaps = 0;
stats.num_steps = 0;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
stats.num_steps++;
if (arr[j-1] > arr[j]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
stats.num_swaps++;
}
}
}
return stats;
}

要从中获得正确的插入排序，只需将if条件移动到内部循环中，如下所示。

bubble_sort_stats_t bubble_sort(int arr[], int n) {
bubble_sort_stats_t stats;
stats.num_swaps = 0;
stats.num_steps = 0;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && arr[j-1] > arr[j]; j--) {
stats.num_steps++;
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
stats.num_swaps++;
}
}
return stats;
}

这样，您可以看到步骤的数量实际上等于交换的数量，并且小于实际气泡排序(sort_bubble(的步骤数量。