冒泡排序执行

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