上一道數學謎題
下一道數學謎題

排序演算法 (Sorting algorithm)數學謎題

答對率:86%
睽違3年經案牘勞形終於回歸......

排序演算法大致上分成穩定排序和不穩定排序
穩定排序以氣泡排序為主 不穩定排序則以選擇排序為主
氣泡排序(bubble sort):
排序時重複檢查要排序的數列,一次比較相鄰之兩個元素,如果他們的順序錯誤就進行交換,當最後兩元素比較完畢後則從第一和第二元素繼續重新比較並重複地進行直到不需再交換
選擇排序(Selection sort):
首先在未排序序列中經由比較找到最小(大)元素,存放到排序序列的起始位置,然後再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。以此類推,直到所有元素均排序完畢

(1)
某學校資訊科技班有35位學生,若老師要依照身高排序以進行座位分發,如果使用氣泡排序法,請問最多需要比較幾次?

(2)
要從未排序的任意12個不同數字中使用選擇排序法比較數字大小的方式找出第四大的數,在最差情況下,最少要幾次比較?
Tim930218(凱哥)2019-08-07提供(2019-08-08修改)
看答案
(1)595次
(2)38次

解析

我要編輯
(1)
1.比較相鄰的元素。如果第一個比第二個大,就交換他們兩個
2.對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。這步做完後,最後的元素會是最大的數
3.針對所有的元素重複以上的步驟,除了最後一個
4.持續每次對越來越少的元素重複上面的步驟,直到沒有任何一對數字需要比較。
因此,從35位同學中要找出最高的一位同學,需要兩兩比較34次。
從剩下34位同學中要找出最高的一位同學,需要兩兩比較33次。
從剩下32位同學中要找出最高的一位同學,需要兩兩比較31次。
……………………
從剩下2位同學中要找出最高的一位同學,需要兩兩比較1次。
所以,全部比較的次數為:34+33+32+….+2+1=(34+1)*34/2=595
(2)
在12個數字中要找出最大的數,需要比較11次。 在剩下11個數字中要找出最大(第二大)的數,需要比較10次。 在剩下10個數字中要找出最大(第三大)的數,需要比較9次。
在剩下9個數字中要找出最大(第四大)的數,需要比較8次。因此,要找出第四大的數,需要先找到第一大、第二大、第三大,全部最多需要比較次數為:11+10+9+8=38(次)
4,390
上一道數學謎題
下一道數學謎題