C - 循环次数减少的冒泡排序

Question

我已经编写了对给定数组进行冒泡排序的函数，并在数组已经排序时停止执行。

int sort(int *arr, int size) {
    int i, j, temp, st = 1, count = 0;
    for(i = 0; (i < size - 1) && (st == 1); i++)
    {
        st = 0;
        for(j = 0; j < size - 1; j++)
        {
            if(arr[j] < arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                st = 1;
            }
            count++;
        }
    }
   return count;
}

如您所见，当数组在 size^2 移动之前排序时，循环应该被打破。

但是，有些地方不对劲，count 变量始终是 size * size，无论我传递什么数组，即使是 {1, 2, 3, 4, 5} 也会给出相同的结果。

怎么了？

Answer 1

有条件

if(arr[j] < arr[j + 1])

您正在按降序对数组进行排序。所以如果你通过它[5, 4, 3, 2, 1] ，您将获得小于 size*size 的值.

请注意，外循环的每次迭代都会将一个元素移动到数组末尾的最终位置，因此您可以减少内循环以仅运行

for(j = 0; j < size - 1 - i; j++)

如果我们运行

#include <stdio.h>

int sort(int *arr, int size) {
    int i, j, temp, st = 1, count = 0;
    for(i = 0; (i < size - 1) && (st == 1); i++)
    {
        st = 0;
        for(j = 0; j < size - 1; j++)
        {
            if(arr[j] < arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                st = 1;
            }
            count++;
        }
    }
   return count;
}

int main(void) {
#ifdef ASCENDING
    int ar[] = { 1, 2, 3, 4, 5 };
#else
    int ar[] = { 5, 4, 3, 2, 1 };
#endif
    int i, ct = sort(ar, sizeof ar / sizeof ar[0]);
    printf("%d\n",ct);
    for(i = 0; i < (int)(sizeof ar / sizeof ar[0]); ++i) {
        printf("%d ", ar[i]);
    }
    printf("\n");
    return 0;
}

编译时没有 ASCENDING定义，输出为

4
5 4 3 2 1

因此外层循环在第一次迭代后中断，因为数组已经按需要排序。使用 -DASCENDING 编译时，数组本来是升序排列的，需要完整的循环才能变成有序的，即输出为

16
5 4 3 2 1

(如果内循环仅针对 j < size - 1 - i 运行，则计数减少到 10)。