氣泡排序法

程式內容
當我們使用氣泡排序法進行 N 個數值的排序時，必須執行兩層FOR迴圈(nested for-loop)。其中內層迴圈需執行 (N-1) 次 IF 的測試，外層迴圈也需執行 (N-1)次，總共會執行 (N-1)*(N-1)次 (大約為N^2，若 N值夠大的話) IF 測試。即使數字已經完全按照順序排列，仍需要進行 N*N 次的比較。
問題：有沒有可能降低 N*N 比較的次數？
請提出你的解法，並產生三組資料，數量分別為 1000, 10000, 100000 個亂數，重複進行 5 次實驗，列出執行次數與時間的比較。...

瀏覽完整內容，請先 註冊 或 登入會員

問題：有沒有可能降低 N*N 比較的次數？

請提出你的解法，並產生三組資料，數量分別為 1000, 10000, 100000 個亂數，重複進行 5 次實驗，列出執行次數與時間的比較。

bruce2000

很多阿
quick sorrt
merge Sort

還有作弊的
counting sort

ssssssz

若是指名「限用氣泡排序法」的話，那降不了時間複雜度，頂多在內層迴圈動點小手腳。內層迴圈檢查：若沒有數值再對調時，代表已經排序好了，這時可以中途停止，不用弄到最後。

for(i=1; i<MAX; i++)
{
　　fllag=1;
　　for(j=0; j<(MAX-1); j++)
　　{
　　　　if(array[j]>array[j+1]) //前大於後，把大的往後移
　　　　exchange(array[j], array[j+1])
...

瀏覽完整內容，請先 註冊 或 登入會員

iloveamy0204

int a[MAX],temp;
for(i=0;i<MAX;i++)
for(j=i+1;j<MAX;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}