#1
|
||||
|
||||
一些和電腦語言有關的數學問題
我剛在看一個c語言的數字排序方法,用所謂的泡泡式排法。有看沒有懂
我是想先了解一下,假設有n個數字(n>=3)要兩兩比大小,來排序,有沒有公式知道是要比幾次? 例如有abc三個數字,先拿a比b,再來a比c,再拿b比c,這樣是三次。但如果是有abcd四個數字,a:b, a:c, a:d, b:c, b:d, c:d好像就要六次?到底有規律嗎? thanks |
#2
|
|||
|
|||
比较次数=n*(n-1)/2
__________________
收购各位版友的四字母com、数字米com/net/cc、三杂米com、拼音米。价格随行市价。站内联系。 |
#3
|
|||
|
|||
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}) |
#4
|
||||
|
||||
例如五個數字原本由左至右為 ④, ⑤, ②, ③, ①
想要將它由左至右~ 變成從小到大的順序~ 由 ④ 開始,將其依序與它左邊的 ⑤, ②, ③, ① 比大小, 如果發現對方比較小就交換位置~ ④, ⑤, ②, ③, ① └──┘ 第一次比較: 沒有比較小,不換 ④, ⑤, ②, ③, ① └────┘ 第二次比較: 有比較小,交換,變成 ②, ⑤, ④, ③, ① ②, ⑤, ④, ③, ① └───────┘ 第三次比較: 沒有比較小,不換 ②, ⑤, ④, ③, ① └─────────┘ 第四次比較: 有比較小,交換,變成 ①, ⑤, ④, ③, ② 經過四次比較,可以挑出最小的放在最左邊, ①, ⑤, ④, ③, ② ^^^^^^^^^^^^^^還沒有挑選的 同上述程序,可以 "再" 經由三次比較挑出 ⑤, ④, ③, ② 中最小的, 放在這四個數字的最左邊,變成 ①, ②, ⑤, ④, ③ ^^^^^^^^^^還沒有挑選的 餘同理。 因此,五個數字的泡泡排序法,須經過 4+3+2+1 = 4*(4+1)/2 次比較,完成排序。 因此, n 個數字的泡泡排序法,須經過 (n-1)+(n-2)+(n-3)+....+2+1 = (n-1)*[(n-1)+1]/2 次比較,完成排序。
__________________
Life, it is. https://sky.tw
|
#5
|
||||
|
||||
十分感謝各位。
果然是有公式的,數學不學好還真是不行啊,我抽象觀念差,光靠想的真的想不出來,後來自己用指頭算 但以下這個程式寫法,我就是搞不懂紅藍字的部份,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; } 這樣說吧,剛開始a=1,b=count-1就是從9開始往下減,最後減到>=a就是減到1,可是陣列的第一個元素排序不是0嗎?最前面那個就不比了嗎? |
#6
|
|||
|
|||
請看這行 if (item[b-1]>item[b]) {
當b = 1 時,這行就會是 item[0]>item[1] 這樣第0個也有比到 |
#9
|
||||
|
||||
引用:
不過我學這個的初始目的只是要讓腦筋活動一下,所以不趕時間也沒啥目的,因此可以慢慢地去搞通一些邏輯上的東西,這剛好有助於延緩我的老年痴呆進程 其實我也建議各位到中年以上的版友們,再找些新的東西來讓腦筋活動一下。活動的標準就是你看了會覺得傷腦筋,一個頭兩個大的新東西才比較有效。雖說保持閱讀是讓大腦不退化的好方法,但一般人的閱讀傾向是專挑自己能輕鬆閱讀的內容,據說這樣的效果不是很好。腦力和肌力一樣,練完如果沒有酸痛感,效果就比較差一點。 |