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; 
} 

正如你所看到的，當數組在大小^ 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 

因此OU ter循環在第一次迭代之後中斷，因爲數組已按需要排序。當與-DASCENDING編譯，陣列是原本按升序排列，需要完整的週期成爲排序，即，輸出是

16 
5 4 3 2 1 

（與計數被減少到10，如果內環只爲j < size - 1 - i運行）。