冒泡排序執行

Question

我想降低嵌套循環的使用，並且被用於利用氣泡的排序技術排序的變量數。在傳統的代碼中，將有兩個for循環或一個for循環的組合。在這種情況下，如果有內循環的唯一原因是穿越回數組，直到數組大小的最近遞減長度的開始索引，我認爲這可能與一個避免「如果」下一個檢查如下圖所示。

1. 用「if」檢查替換內部循環的執行是否會使運行時間比傳統算法中的內部for循環更糟？實際上是否需要使用for循環而不是「if」？如果傳統算法是包含太多不可避免的嵌套循環和其他實現的「if」語句的代碼的一部分，則會增加圈複雜度。

2. 我想問一下，當字節序到圖片，會有關於交換在這種情況下使用的算法產生影響？

下面的代碼：

void Bubble_Sort(int *arr, int size) 
{ 
    int index = 0; 
    /* pointer to array */ 
    int* temp = arr; 

    while(size > 1) 
    { 
     /* Initial check if i has traversed up till 
      last but one element of array 
     */ 
     if(index == (size-1)) 
     { 
      /* Set loop counter again from beginning*/ 
      index =0; 
      /* Decrement the number of elements to traverse upto */ 
      size--; 
      /* Set back pointer to start index of array */ 
      temp = arr; 
     } 

     /* Swapping algorithm */ 
     if(*temp > *(temp+1)) 
     { 
      *temp ^= *(temp+1); 
      *(temp+1) ^= *temp; 
      *temp ^= *(temp+1); 
     } 

     /* Go to next element in array */ 
     temp++; 

     index++; 
    } 
} 

Answer 1

冒泡排序，雖然非常低效的排序算法，已經被推崇計算機科學家最優化。當前的最優算法是（在種僞代碼）：

sort (A, n)  // bubble sort array A[0..n-1] 
{ 
    k= n-1;   // k holds position of last interchange. All higher elements are sorted. 
    while (k > 0) 
    { 
     l= 0; 
     for (j=0; j < k; j++) 
     { 
      if (A[j] > A[j+1]) 
      { 
       tmp = A[j]; 
       A[j] = A[j+1]; 
       A[j+1]= tmp; 
       l= j; 
      } 
     } 
     k= l; 
    } 
}