建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
使用蠻力法求解冒泡排序
蠻力法是一種簡單直接的解決問題的方法，常常直接基于問題的描述和所涉及的定義。由于蠻力法是基于問題的定義來思考的，那么可以說它是一種幾乎什么問題都能解決的一般性的方法。
目前創(chuàng)新互聯(lián)建站已為1000多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)絡(luò)空間、網(wǎng)站托管、服務(wù)器租用、企業(yè)網(wǎng)站設(shè)計、南澗網(wǎng)站維護(hù)等服務(wù)，公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。
算法思想：
比較列表中相鄰的元素，如果是逆序的話，就交換他們的位置。重復(fù)多次之后，最大的元素就排到了最后一個位置。第二遍操作將第二個元素排到了倒數(shù)第二個位置上，這樣一直依次比較下去，直到 n-1 遍之后，就排好了整個列表。
下面是我的代碼實現(xiàn)：C++
#include
using 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;i
for(j=0;j
if(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)有序了，我們就可以停止該算法了。具體改進(jìn)版本如下：
#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
>Arr[i];
for(i=0;i
false;
for(j=0;j
if(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).
網(wǎng)頁題目：使用蠻力法求解冒泡排序
URL分享：http://fisionsoft.com.cn/article/dpechjc.html
