|
|
|
#1
2014-02-13, 08:29 PM
|
||||
|
||||
一些和電腦語言有關的數學問題
我剛在看一個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 
|
|
#3
2014-02-13, 08:58 PM
|
|||
|
|||
|
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
2014-02-13, 09:13 PM
|
||||
|
||||
|
例如五個數字原本由左至右為 ④, ⑤, ②, ③, ①
想要將它由左至右~ 變成從小到大的順序~ 由 ④ 開始，將其依序與它左邊的 ⑤, ②, ③, ① 比大小， 如果發現對方比較小就交換位置~ ④, ⑤, ②, ③, ① └──┘ 第一次比較： 沒有比較小，不換 ④, ⑤, ②, ③, ① └────┘ 第二次比較： 有比較小，交換，變成 ②, ⑤, ④, ③, ① ②, ⑤, ④, ③, ① └───────┘ 第三次比較： 沒有比較小，不換 ②, ⑤, ④, ③, ① └─────────┘ 第四次比較： 有比較小，交換，變成 ①, ⑤, ④, ③, ② 經過四次比較，可以挑出最小的放在最左邊， ①, ⑤, ④, ③, ② ^^^^^^^^^^^^^^還沒有挑選的 同上述程序，可以 "再" 經由三次比較挑出 ⑤, ④, ③, ② 中最小的， 放在這四個數字的最左邊，變成 ①, ②, ⑤, ④, ③ ^^^^^^^^^^還沒有挑選的 餘同理。 因此，五個數字的泡泡排序法，須經過 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
2014-02-13, 09:24 PM
|
||||
|
||||
|
十分感謝各位。
果然是有公式的，數學不學好還真是不行啊，我抽象觀念差，光靠想的真的想不出來，後來自己用指頭算  但以下這個程式寫法，我就是搞不懂紅藍字的部份，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嗎？最前面那個就不比了嗎？
|
|
#9
2014-02-14, 03:56 PM
|
||||
|
||||
|
引用:
  不過我學這個的初始目的只是要讓腦筋活動一下  ，所以不趕時間也沒啥目的，因此可以慢慢地去搞通一些邏輯上的東西，這剛好有助於延緩我的老年痴呆進程 其實我也建議各位到中年以上的版友們，再找些新的東西來讓腦筋活動一下。活動的標準就是你看了會覺得傷腦筋，一個頭兩個大的新東西才比較有效。雖說保持閱讀是讓大腦不退化的好方法，但一般人的閱讀傾向是專挑自己能輕鬆閱讀的內容，據說這樣的效果不是很好。腦力和肌力一樣，練完如果沒有酸痛感，效果就比較差一點。
|
