0

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

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} 给出相同的结果。

怎么了？

4

1 回答 1

3

有条件

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

（如果内部循环仅运行，则计数减少到 10 j < size - 1 - i）。

于 2012-11-15T19:01:23.223 回答