2010-02-27 96 views
-5

我想實現在C.這裏冒泡排序算法是我到目前爲止有:如何實現冒泡排序在C.

#include<stdio.h> 
void bubble_sort(int m, int a[100000]); 
void main() 
{ 
int a[100000], i, m; 
FILE * be; 

be=fopen("be.txt","r"); 
for (i=0; !(feof(be)); ++i) 
    fscanf(be,"%i", a+i); 
m=i-1; 
bubble_sort(m ,a); 
fclose(be); 
} 
void bubble_sort(int m, int a[100000]) 
{ 
int i, ok, v, n=m;; 
for (;!ok;ok=1) 
{ 
    ok=0; 
    for (i=0;i<=m-1;++i) 
    { 
     if (*(a+i)>*(a+i+1)) { v=*(a+i); *(a+i)=*(a+i+1); *(a+i+1)=v; ok=0;} 
    } 
    m=m-1; 
} 

for (i=0; i<n; ++i) 
    printf("%i ", a[i]); 
} 

我的僞代碼:

Bubblesort2(A) 
m:=length(A) - 1 
repeat 
    OK := true 
    for i := 0 to m-1 do 
     if Ai > Ai+1 then 
      Ai <=>Ai+1 
      OK := false 
    m := m - 1 
until OK 

這不正確。在C中實現泡沫排序的代碼是什麼?

+5

因爲這是一項功課:你的第一步應該是使代碼可讀...我,好吧,V,M,N,A是不可理解的變量名。你的控制流結構也可以改進 - 爲什麼你使用的結構像((!!ok; ok = 1)? – tanascius

+2

我見過'*(a + i + 1)'在初學者的問題中經常出現 - 教授是這樣教的,或者爲什麼不是人們使用'a [i + 1]'? – AndiDog

+0

你真的會嘗試冒泡排序一個100K數組嗎? –

回答

2

試試這個:

void bubble_sort(int m, int a[100000]) 
{ 
    int i, ok = 0, v, n = m; 
    while (!ok) 
    { 
     ok = 1; 
     for (i=0; i < m-1; ++i) 
     { 
      if (*(a+i) > *(a+i+1)) 
      { 
       v = *(a+i); 
       *(a+i) = *(a+i+1); 
       *(a+i+1) = v; 
       ok = 0; 
      } 
     } 

     m--; 
    } 

    for (i = 0; i < n; ++i) 
     printf("%i ", a[i]); 
} 

基本上,初始化OK(局部變量與垃圾值初始化)。進入循環時,您還必須設置ok = 1,如果發生交換,則ok = 0。使用for循環沒有意義,while循環更具可讀性。 m = m - 1可以替換爲m--,它是一樣的東西,你寫的代碼少。

+10

提供完整的作業題目代碼通常在這裏不受歡迎。它鼓勵人們在不理解問題的情況下複製和粘貼。 –

+0

for(i = 1; i Kalozka1

+3

@Mark Byers:我解釋了這些問題,OP顯示了他自己試圖解決問題的嘗試。對不起,如果我不應該發佈完整的代碼,我認爲在這種情況下可以確定(幾乎是工作)。 – IVlad

1

您未初始化ok的值,因此行爲未定義。

無論如何,您似乎都將ok的值設置爲零。

另外,沒有意義的優化氣泡排序。只要簡單一點就行了。如果你想要很好的性能,那麼你根本不應該使用這個算法。

我建議你閱讀維基百科上的algorithm description,嘗試用你自己的語言寫成僞代碼,確保你理解它,然後實現它。

+0

減少m很好:在每一步中,最大的元素將達到它的最終位置,所以在下一步中沒有必要檢查它。 – IVlad

+0

@IVlad:是的,只是解決了這個問題。不幸的是,即使進行了這種優化,它仍然是O(n * n)。 –

+0

+1對於維基建議 – Shaihi

2
void bubble_sort(int m, int a[]) 
    { 
    int i, ok, v, n=m; 
    for (ok = 0;!ok;) 
    { 
     ok=1; 
     for (i=0;i<=m-1;++i) 
     { 
      if (*(a+i)>*(a+i+1)) { v=*(a+i); *(a+i)=*(a+i+1); *(a+i+1)=v; ok=0; } 
     } 
     m=m-1; 
    } 
    } 

兩個問題與您的代碼:

  1. 確定在開始未定義所以它不是明確的條件是否for循環會滿意與否。
  2. for語句中的第3個子句(update子句)在迭代括號中的代碼之後,但在再次檢查條件之前執行。所以你設置爲1,然後檢查ok = 0。因此,它只進行1次迭代。

這個程序還是一團糟。外循環應該是一個while循環。你應該使用適當的數組訪問器a[i]而不是+ i。源代碼中的間隔和換行符也不需要任何費用。