一些和電腦語言有關的數學問題

[哈啦]

我剛在看一個c語言的數字排序方法，用所謂的泡泡式排法。有看沒有懂:XD:

我是想先了解一下，假設有n個數字（n>=3)要兩兩比大小，來排序，有沒有公式知道是要比幾次？
例如有abc三個數字，先拿a比b，再來a比c，再拿b比c，這樣是三次。但如果是有abcd四個數字，a:b, a:c, a:d, b:c, b:d, c:d好像就要六次？到底有規律嗎？

thanks

[yumi]

比较次数=n*(n-1)/2

[lukawa]

bubble sort 算是用來瞭解排序跟練習排序程式最好的algorithm
他的最佳時間複雜度是O(n)
最差的時間複雜度是 O(n^{2})
重點是平均時間複雜度 O(n^{2}) !!

所以大一點的資料，千萬不要用bubble sort，那會排死

舉個例子

1 2 3 4 5 6 7

由小排到大，只要比較n=6次，得到最佳時間複雜度

但是如果要由大排到小
那就慘了

第一次比較6次會變成

2 3 4 5 6 7 1

第二次比較5次會變成

3 4 5 6 7 2 1

....一直下去

所以得到最差的時間複雜度 O(n^{2})

[weiye]

例如五個數字原本由左至右為 ④, ⑤, ②, ③, ①

想要將它由左至右~ 變成從小到大的順序~

由 ④ 開始，將其依序與它左邊的 ⑤, ②, ③, ① 比大小，

如果發現對方比較小就交換位置~

　　　　　　 ④, ⑤, ②, ③, ①
　　　　　　 └──┘
第一次比較：　沒有比較小，不換


　　　　　　 ④, ⑤, ②, ③, ①
　　　　　　 └────┘
第二次比較：　有比較小，交換，變成 ②, ⑤, ④, ③, ①

　　　　　　 ②, ⑤, ④, ③, ①
　　　　　　 └───────┘
第三次比較：　沒有比較小，不換

　　　　　　 ②, ⑤, ④, ③, ①
　　　　　　 └─────────┘
第四次比較：　有比較小，交換，變成 ①, ⑤, ④, ③, ②

經過四次比較，可以挑出最小的放在最左邊，

　　　　　　　①, ⑤, ④, ③, ②
　　　　　　　　　^^^^^^^^^^^^^^還沒有挑選的

同上述程序，可以 "再" 經由三次比較挑出 ⑤, ④, ③, ② 中最小的，

放在這四個數字的最左邊，變成 ①, ②, ⑤, ④, ③

　　　　　　　　　　　　　　　　　　 ^^^^^^^^^^還沒有挑選的

餘同理。

因此，五個數字的泡泡排序法，須經過 4+3+2+1 = 4*(4+1)/2 次比較，完成排序。

因此， n 個數字的泡泡排序法，須經過 (n-1)+(n-2)+(n-3)+....+2+1 = (n-1)*[(n-1)+1]/2 次比較，完成排序。

[哈啦]

十分感謝各位。

果然是有公式的，數學不學好還真是不行啊，我抽象觀念差，光靠想的真的想不出來，後來自己用指頭算~greenlau:



但以下這個程式寫法，我就是搞不懂紅藍字的部份，why它會如此寫 ？

#include <stdio.h>
#include <stdlib.h>

int main(void)
{

int item[100];
int a,b,t;
int count;

printf("how many numbers? \n");
scanf("%d",&count);
for(a=0;a<count;a++) scanf("%d", &item[a]);

for(a=1;a<count;a++)
for(b=count-1;b>=a;b--)
{
if (item[b-1]>item[b]) {
t=item[b-1];
item[b-1]=item[b];
item[b]=t;
}
}
for(t=0;t<count;t++) printf("%d\n",item[t]);
return 0;
}

假設我要將十個數字排序，紅字的地方顯然是從1開始而小於count(10)就是只從1到9，算9次而已。

這樣說吧，剛開始a=1，b=count-1就是從9開始往下減，最後減到>=a就是減到1，可是陣列的第一個元素排序不是0嗎？最前面那個就不比了嗎？

[lukawa]

請看這行 if (item[b-1]>item[b]) {
當b = 1 時，這行就會是 item[0]>item[1]
這樣第0個也有比到

[哈啦]

請看這行 if (item[b-1]>item[b]) {
當b = 1 時，這行就會是 item[0]>item[1]
這樣第0個也有比到

I see, thank you!~yes

[some]

哈大～

一點建議... 如果不是瘋狂的程式設計者.. 這種東西找現成函式來套就好, 才省時間
把大部份的思考用在想呈現的邏輯上

比方說~ 開車老強的舒馬克, 用不著知道輪胎要用什麼摩擦系數的最好, 換輪胎的技師也不用知道輪胎怎麼做的~~

我寫過很多程式 類似這種的東西我也練習過, 但想通了寫成了過沒幾個月再看一次, "又得重想一下".. 所以我現在都直接跳過節省我寶貴的時間

[哈啦]

哈大～

一點建議... 如果不是瘋狂的程式設計者.. 這種東西找現成函式來套就好, 才省時間
把大部份的思考用在想呈現的邏輯上

比方說~ 開車老強的舒馬克, 用不著知道輪胎要用什麼摩擦系數的最好, 換輪胎的技師也不用知道輪胎怎麼做的~~

我寫過很多程式 類似這種的東西我也練習過, 但想通了寫成了過沒幾個月再看一次, "又得重想一下".. 所以我現在都直接跳過節省我寶貴的時間

thanks~yes :bow

不過我學這個的初始目的只是要讓腦筋活動一下?:teeth，所以不趕時間也沒啥目的，因此可以慢慢地去搞通一些邏輯上的東西，這剛好有助於延緩我的老年痴呆進程~cici

其實我也建議各位到中年以上的版友們，再找些新的東西來讓腦筋活動一下。活動的標準就是你看了會覺得傷腦筋，一個頭兩個大的新東西才比較有效。雖說保持閱讀是讓大腦不退化的好方法，但一般人的閱讀傾向是專挑自己能輕鬆閱讀的內容，據說這樣的效果不是很好。腦力和肌力一樣，練完如果沒有酸痛感，效果就比較差一點。?:teeth