用蠻力法解冒泡排序

冒泡排序是蠻力法的另一個經典體現。

演算法思想：比較列表中相鄰的元素，如果是逆序的話，就交換他們的位置。重複多次之後，最大的元素排到了最後一個位置。第二遍操作將第二個元素排到了倒數第二個位置上，這樣一直依次比較下去，直到  n-1  遍之後，就排好了整個列表。

以下是我的程式碼實作：C

#include 
using namespace std;
int main()
{
    int i,j,temp,N;
    cin>>N;
    int *Arr=new int[N];
    for(i=0;i<n cin>>Arr[i];
 
    for(i=0;i<n for if>Arr[j+1])//如果逆序，就交换
            {
                temp=Arr[j];
                Arr[j]=Arr[j+1];
                Arr[j+1]=temp;
            }
        }
    }
 
    for(i=0;i<n cout return>
<p>演算法分析：輸入的規模完全由N決定，基本操作是比較：Arr[j]>Arr[j 1]，時間複雜度C(n)=Θ(n2).</p>
<p>但是鍵的交換次數是取決於特定的輸入，最差的情況是與我們要求的排序相反的，這時候鍵的交換次數=鍵的比較次數=Θ(n2).</p>
<p>但是在有的輸入情況下，如果在對列表比較一遍之後，沒有交換元素的位置，那麼這個列表已經有序了，我們就可以停止該演算法了。具體改進版本如下：</p>
<pre class="brush:php;toolbar:false">#include 
using namespace std;
int main()
{
    int i,j,temp,N;
    bool change=false;
    cin>>N;
    int *Arr=new int[N];
    for(i=0;i<n cin>>Arr[i];
 
    for(i=0;i<n change="false;" for if>Arr[j+1])//如果逆序，就交换
            {
                temp=Arr[j];
                Arr[j]=Arr[j+1];
                Arr[j+1]=temp;
                change=true;
            }
        }
        if(!change)//没有发生交换，则不用继续比较了。
        {
            break;
        }
    }
 
    for(i=0;i<n cout return>
<p>但是在最差情況下，時間複雜度還是Θ(n2).</p></n></n></n>

以上是用蠻力法解冒泡排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！