Re: [問題] 找出最小的10個值
※ 引述《harristime (瀚宇)》之銘言：
: 開發平台(Platform): Linux
: 問題(Question): 一個執行500次的while loop,
: 每跑一次會得到一個值a,
: 如何在這500個"a"內找出最小的10個值呢?
: 謝謝
a[100]={......} 100個元素
取出前10個到B[10] (a[0]~a[9] ->b[10] )
Case1: b[10]不排序
if a[10] < b[0] 那b[0]被取代下來，但卻不保證原來b[0]比b[1]~b[9]小
Case2: b[10]排序
a[11]~a[99]共90元素都向b[]比較
if a[11]>b[0] a[11]<b[1]則只要比較2次
(運氣差最多比較完全b[] 10個元素)
最差整體速度a[N] b[B]:
複製進b[B]速度+Bubllesort + 比較次數+ 複製+bubblesort速度
B + (B-1+1)*(B-1)/2+ (N-B)*B + (N-B)+0
B + (B-1+1)*(B-1)/2+ (N-B) + (N-5)+(N-B)*B
case:
a[N]={9,8,7,6,5,4,3,2,1,15,14,13,12,11,10}
= 10+ (9+1)*9/2+ (N-10)*10+ ( N-10)+N-10
a[N]={16,15,14,13,12,11,10,9,8,7,6,5,4,3,2}
= 10+ (9+1)*9/2+ (N-10) + (N-10)*(9)+N-10
http://codepad.org/7RaaOm7O
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.117.8.99
→
05/11 02:10, , 1F
05/11 02:10, 1F
→
05/11 02:35, , 2F
05/11 02:35, 2F
→
05/11 02:39, , 3F
05/11 02:39, 3F
※ 編輯: kingofsdtw 來自: 122.117.8.99 (05/11 02:56)
→
05/11 03:52, , 4F
05/11 03:52, 4F
→
05/11 03:53, , 5F
05/11 03:53, 5F
討論串 (同標題文章)