C++中如何使用蠻力法求解冒泡排序

算法思想：

比較列表中相鄰的元素，如果是逆序的話，就交換他們的位置。重復(fù)多次之后，最大的元素就排到了最后一個位置。第二遍操作將第二個元素排到了倒數(shù)第二個位置上，這樣一直依次比較下去，直到 n-1 遍之后，就排好了整個列表。

下面是我的代碼實現(xiàn)：C++

#includeusing namespace std;
int main()
{
   int i,j,temp,N;
   cin>>N;
   int *Arr=new int[N];
   for(i=0;i>Arr[i];

   for(i=0;ifor(j=0;jif(Arr[j]>Arr[j+1])//如果逆序，就交換
           {
               temp=Arr[j];
               Arr[j]=Arr[j+1];
               Arr[j+1]=temp;
           }
       }
   }

   for(i=0;i" ";
   return 0;
}

算法分析：輸入的規(guī)模完全由N決定，基本操作是比較：Arr[j]>Arr[j+1]，時間復(fù)雜度C(n)=Θ(n2).

但是鍵的交換次數(shù)是取決于特定的輸入，最差的情況是與我們要求的排序相反的，這時候鍵的交換次數(shù)=鍵的比較次數(shù)=Θ(n2).

但是在有的輸入情況下，如果在對列表比較一遍之后，沒有交換元素的位置，那么這個列表已經(jīng)有序了，我們就可以停止該算法了。具體改進版本如下：

#includeusing namespace std;
int main()
{
   int i,j,temp,N;
   bool change=false;
   cin>>N;
   int *Arr=new int[N];
   for(i=0;i>Arr[i];

   for(i=0;ifalse;
       for(j=0;jif(Arr[j]>Arr[j+1])//如果逆序，就交換
           {
               temp=Arr[j];
               Arr[j]=Arr[j+1];
               Arr[j+1]=temp;
               change=true;
           }
       }
       if(!change)//沒有發(fā)生交換，則不用繼續(xù)比較了。
       {
           break;
       }
   }

   for(i=0;i" ";
   return 0;
}

但是在最差情況下，時間復(fù)雜度還是Θ(n2).