Re: [問題] 想要請教Shear sort
看板Prob_Solve (計算數學 Problem Solving)作者yauhh (喲)時間15年前 (2009/06/01 19:58)推噓6(6推 0噓 15→)留言21則, 5人參與討論串2/2 (看更多)
※ 引述《sakurarain (茫然不知所以)》之銘言：
: 不知道是不是有誰可以跟我大略講解一下這是個怎樣的演算法?
: 像是這個sort是如何做到的?時間複雜度那些方面的
: 或是有中文的網頁可以提供來讓小女子慢慢去研究就更好了
看了一點點,大意是說
要排 n 筆資料,是把資料排列成 n^(0.5) * n^(0.5) 方陣,
然後做 k 次以下步驟,據說這個 k 可以是 log_2 n + 1.
這 k 次分成單數次和偶數次,單數次將奇數列從右向左排序,將偶數列從左向右排序.
偶數次將每一行從上向下排序.
然後,時間複雜度起碼是從 n^(0.5) 算起,而不是從 n 算起了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.113.142
推
06/01 23:50, , 1F
06/01 23:50, 1F
→
06/02 00:22, , 2F
06/02 00:22, 2F
→
06/02 00:23, , 3F
06/02 00:23, 3F
→
06/02 00:51, , 4F
06/02 00:51, 4F
推
06/02 04:06, , 5F
06/02 04:06, 5F
→
06/02 04:06, , 6F
06/02 04:06, 6F
→
06/02 07:11, , 7F
06/02 07:11, 7F
推
06/02 09:04, , 8F
06/02 09:04, 8F
→
06/02 09:06, , 9F
06/02 09:06, 9F
→
06/02 09:07, , 10F
06/02 09:07, 10F
→
06/02 09:07, , 11F
06/02 09:07, 11F
→
06/02 09:09, , 12F
06/02 09:09, 12F
→
06/02 09:10, , 13F
06/02 09:10, 13F
→
06/02 09:10, , 14F
06/02 09:10, 14F
→
06/02 09:11, , 15F
06/02 09:11, 15F
→
06/02 09:13, , 16F
06/02 09:13, 16F
推
06/02 09:16, , 17F
06/02 09:16, 17F
推
06/04 02:15, , 18F
06/04 02:15, 18F
→
06/04 02:16, , 19F
06/04 02:16, 19F
→
06/04 02:16, , 20F
06/04 02:16, 20F
推
06/05 11:49, , 21F
06/05 11:49, 21F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
