JWorld@TW the best professional Java site in Taiwan
      註冊 | 登入 | 全文檢索 | 排行榜  

» JWorld@TW » 交流、聊天、灌水  

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友   
reply to postflat modego to previous topicgo to next topic
本主題所含的標籤
無標籤
作者 shell sort舉世第一個快速排序法
tigereye30100





發文: 23
於 2007-10-02 18:19 user profilesend a private message to usersend email to tigereye30100reply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
我的部落格:
http://www.wretch.cc/blog/tigereye3010
http://www.wretch.cc/video/tigereye3010

多層loop迴圈的一般結構 :
外層loop index variables初值設定
外層loop條件
內層loop index variables初值設定(可能與外層loop index variables有關)
內層loop條件
內層loop index variables如何變化
End loop
外層loop index variables如何變化
End loop

Shell sort是由美國Cincinnati大學的數學博士Donald L. shell所發明,是舉世第一個快速排序演算法,他在數學與軟體上有重要的貢獻,不過卻以此演算法聞名。
我們先簡略的說明一下演算法:
所謂回合(pass)就是從陣列的第1個元素掃描到最後一個元素。
所謂增量(incre)就是區段數目。此演算法會將一個陣列視為由多個區段所組成。
每一個pass對應一個incre,每一個pass之後,對於個別區段來說,一定是完全排序好的,但是整個陣列卻未必。經過多個passes之後,陣列才會完全排序好,此時incre為1。
陣列索引: 0 1 2 3 4 5 6 7 8 9
陣列元素: 77 62 14 9 30 21 80 25 70 55
區段編號: 一 二 三 四 五 一 二 三 四 五
在此例之中,incre為5,代表一共有5個區段,區段一包含陣列的第0個、與第6個元素。同一個區段的元素並沒有相鄰。
在此,假設你已經對shell sort有清楚地了解,不過,你也許可以由以下發展程式碼的過程中,反而了解或更了解此演算法。可以嘗試一下,根本不去看演算法。

最內層loop: (解決fall back one partition)SmileSmileSmileSmileSmileSmileSmile
陣列名稱為list。
陣列索引: 0 … incre … 2*incre … k*incre ……
元素 … 元素 … 元素 … 元素 ……
區段編號: 一 … 一 … 一 … 一 ……
工作說明:
這個loop是輔助『將某一個區段完全排序好』的,也就是說,要將某一個區段完全排序好,需要此功能,再以程式碼來說,當檢查到某一區段的兩個相鄰元素(在陣列中不相鄰歐)的順序不對時,會進入此loop之中執行。
舉例說明:
陣列索引: 0 … incre … 2*incre … 3*incre … 4*incre ……
20 … 30 … 40 … 50 … 25 ……
區段編號: 一 … 一 … 一 … 一 … 一 ……
假設經由演算法的運作,此一區段的前4個元素都排序好了,正在檢查此一區段的第4個與第5個元素,發現第5個元素的順序不對,必須要往前移動。但是如果只將50、25交換,也還不夠,因為第3個元素也比25大。因此:
(1).只要有交換發生,就要繼續往回檢查(如檢查50、25),注意,當然是往回檢查同一個區段的。
(2).往回檢查,一直到不必交換、或是到達區段的第1個元素為止。
(3).在往回檢查結束前,雖然25在區段中的正確位置還不知道,但是與25發生交換的元素,應該放在區段的哪個位置是確定的,所以在往回檢查前,先將25保留在一個變數之中(以下的程式碼中是保留在變數hold之中),而與25發生交換的元素,就可以直接進行移動。

陣列索引: 0 … incre … 2*incre … 3*incre … 4*incre ……
20 … 30 … 40 … 50 … 25 ……
區段編號: 一 … 一 … 一 … 一 … 一 ……
Loop index variables walker current

複習整理:
大致上來說,我們作的工作就是比較兩個數字的大小。
在最開始,是此區段中已完全排序部分(20、30、40、50)的最後一個元素(50),與此區段中尚未處理部份(25、…)的第1個元素(25),作大小的比較,以判斷是否要交換(如果是,會引發之前提到的fall back one partition,也就是要進入loop之中,不斷的進行往回檢查)。因此顯然loop要能進行此『重複動作』:
『必須有一個loop index variable,在往回檢查loop的每一次執行,能夠指向此區段下一個待比較大小的元素的陣列索引位置』
所以我們宣告walker,作為內層loop index variable。
另外,我們設定一個陣列索引current,指向區段中尚未處理部份的第1個元素(25)。請注意,等一下,當我們建立外層loop時,current會成為外層loop的index variable,並設定給內層loop的index variable,就是walker。
最後,還要宣告一個變數hold,將list[current]暫存於hold。
程式碼:

1 walker = current - incre
2 hold = list[current]
3 loop( walker >= 0 AND hold < list[walker] )
4 list[walker + incre] = list[walker]
5 walker = walker – incre
6 end loop
7 list[walker + incre] = hold

line 1: walker = current - incre
此指令是進入迴圈之前的準備工作。只會執行一次。
既然current是指向區段中尚未處理部份的第1個元素,那(current – incre)當然就是指向區段中已完全排序部分的最後一個元素。所以此指令就是內層loop index variable的初值設定。我們之前有預告,current是外層loop的index variable,所以在此我們可以了解到:
『內層loop index variable需要外層loop index variable作初值設定,而且是一個簡單的代數關係』

line 2: hold = list[current]
此指令是進入迴圈之前的準備工作。只會執行一次。
hold的用途,暫存list[current]。如果有進入迴圈,則在跳出迴圈、執行line 7時,將hold放置到區段中正確的位置。

總結line 1與line 2,current指向區段中尚未處理部份的第1個元素,而且在整個loop執行時,都不會改變,而hold則暫存此元素,在整個loop執行時,也都不會改變。loop執行時,會不斷改變的是walker,進行往回檢查的作業。

line 3:
loop( walker >= 0 AND hold < list[walker] )
迴圈的條件。第1個條件是walker >= 0,因為在迴圈的每一次,walker都會遞減incre,如果hold比此區段已排序部分的所有元素都小時,walker就會因為多次的遞減而小於0(但是陣列索引不可以為負),所以要加上此條件,以便跳出迴圈。第2個條件是hold < list[current],此條件成立,表示hold在區段中的的位置還沒有確定,要繼續往回檢查。

line 4: list[walker + incre] = list[walker]
迴圈的每一次會執行這個指令一次。此指令將元素list[walker]往後移到位置walker + incre。因為list[walker] 比hold大,所以這樣作是正確的。

line 5: walker = walker – incre
迴圈的每一次會執行這個指令一次。此指令為往回檢查作業做準備。

line 6: end loop
迴圈結束,接著進行line 3的條件檢查。

line 7: list[walker + incre] = hold
此指令在迴圈完全結束之後執行,但是要注意的是,不管有沒有進入迴圈(就是有沒有進行往回檢查)都會執行此指令,所以我們對此指令的討論要分為兩個部份:
有進入迴圈:
表示hold的位置要依據往回檢查作業,才能確定。要注意的是hold儲存在陣列位置walker + incre,為詳細解釋,又要分為兩種情況:
(1).hold比『此區段中已完全排序部分』的每一個元素都要小,所以迴圈會跳出是因為walker >= 0這個條件,此時walker是-incre―假設我們正在作第1區段、-incre + 1―假設我們正在作第2區段、-incre + 2―假設我們正在作第3區段,以此類推。所以line 7的list[walker + incre]就是list[0](第1區段的第1個位置)、list[1] (第2區段的第1個位置)、或list[2] (第3區段的第1個位置),而將hold儲存在此,的確沒有錯。
(2).hold的位置介於『此區段中已完全排序部分』的第1個元素與最後一個元素之間,所以迴圈會跳出是因為hold < list[walker]這個條件,所以hold的位置是緊接著在list[walker]之後,也就是相鄰的意思,不過請注意,是指在此區段相鄰,而不是指整個陣列,所以緊接著在list[walker]之後的位置就是walker + incre。

沒有進入迴圈:
這表示當walker指向此區段中已完全排序部分(20、30、40、50)的最後一個元素(50)、而current指向此區段中尚未處理部份(25、…)的第1個元素(25)時(也就是初次檢查line 3的條件時),line 3的條件『walker >= 0 AND hold < list[walker]』就不成立(所以迴圈中的指令line 4、5,一次也沒有作),而且不成立一定是因為hold < list[walker]這個條件(在進入迴圈之前,walker可能的最小值是0,所以walker >= 0是一定成立的。原因要在建立外層迴圈之後才會明朗,容後說明)。hold < list[walker]不成立,表示尚未處理部份的第1個元素小於或等於已完全排序部分的最後一個元素,當然不必作任何處理,所以也就不必進行為了找到hold的正確位置,而作的往回檢查作業,可以直接將hold,也就是list[current],加入『已完全排序部分』,成為『已完全排序部分』的最後一個元素。在此,還要提醒一點:
因為完全沒有進入迴圈,所以這段程式碼只作了
line 1、2、7(當然line 3的條件檢查也作了一次),而重點是line 7,因為它動到了陣列,並且將hold儲存在陣列位置walker + incre。根據我們上面的敘述,如果有進入迴圈,位置walker + incre是正確的,可是在這裡,並沒有進入迴圈,會不會有問題呢?換句話說,不管有沒有進入迴圈,hold都是存入位置walker + incre。如過你將line 1與7一起看,也就是連續執行這兩個指令,就會知道這是正確無誤的。

複習:
此loop重複的動作―
『walker不斷的往前移動incre的距離,並且將list[walker]儲存到list[walker+incre]之中。』

中層loop: (執行一個pass的作業,使各各區段是排序好的)SmileSmileSmileSmileSmileSmileSmile
因為shell sort一共有3層loop,所以最內層loop之外的那一層loop,稱之為中層loop。
工作說明:
從頭到尾掃描一次陣列(就是一個pass),如果發現需要交換(內層loop的條件判斷),則進入內層loop,作往回檢查(也就是fall back one partition)。
請注意,所謂一個pass是從頭到尾掃描一次陣列,但是我們也知道,同一個區段的元素是分散在陣列之中的,所以就整個中層loop而言(也就是一個pass),會依區段的順序,交替在不同的區段之中作業,但是如果進入到內層loop,進行往回檢查,就一定是針對單一的某一個區段。這種安排,就好像一件工作可以分成許多個子工作,而完成整個工作的方式,是輪流針對所有子工作,完成某一個子工作的一部份,而不是完成某一個子工作之後,再接著完成另一個子工作。學習完shell sort之後,應該要有這個認識。
因為是從頭到尾掃描一次陣列,所以一開始,是針對第1區段的前兩個元素(陣列索引位置為0與incre):
陣列索引: 0 … incre … 2*incre … k*incre ……
元素 … 元素 … 元素 … 元素 ……
區段編號: 一 … 一 … 一 … 一 ……
walker current
在walker與current設定之後,進行內層loop的條件判斷,以便決定要不要進行往回檢查作業。
接著,針對第2區段的前兩個元素(陣列索引位置為1與incre+1):
陣列索引: 0 1 … incre incre+1 … …
元素 元素 … 元素 元素 … …
區段編號: 一 二 … 一 二 … …
walker current
在walker與current設定之後,進行內層loop的條件判斷,以便決定要不要進行往回檢查作業。
依此類推,一直到所有區段的前兩個元素都作過了,則又回到第1區段,不過現在是針對第2與第3個元素:
陣列索引: 0 … incre … 2*incre … k*incre ……
元素 … 元素 … 元素 … 元素 ……
區段編號: 一 … 一 … 一 … 一 ……
walker current
在walker與current設定之後,進行內層loop的條件判斷,以便決定要不要進行往回檢查作業。不過現在是針對第1區段的第2與第3個元素(陣列索引位置為incre與2*incre),而第1區段的已排序部份就是第1與第2個元素。
依據以上的討論,我們知道,要宣告current作為中層loop的index variable,其初值設定為incre,而迴圈的每一次執行,current就要增加1。
在此,我們可以介紹一下incre的角色了。之前有提到一個pass對應一個incre,而在中層loop(負責一個pass的工作),incre作為中層loop的index variable的初值。事實上,incre是外層loop的index variable,而incre與current的關係,就好像是在內層loop所提到的current與walker的關係。
因此,中層loop有一個特殊的地位,它是內層的外層,也是外層的內層。換句話說,中層是內層也是外層,可以好好體會中層的index variable,與它的內層與外層的index variables的關係。

程式碼:
1 current = incre
2 loop(current <= last)
3 walker = current - incre
4 hold = list[current]
5 loop( walker >= 0 AND hold < list[walker] )
6 list[walker + incre] = list[walker]
7 walker = walker – incre
8 end loop
9 list[walker + incre] = hold
10 current = current + 1
11 end loop

line 1:
設定current的初值。

line 2:
中層loop的條件檢查,last是陣列的最後一個元素的位置。

line 10:
中層loop每執行一次,其index variable的變化設定。

外層loop:SmileSmileSmileSmileSmileSmileSmile
(進行多個passes,最後,當incre為1,也就是區段數目為1時,完成整個排序作業)
一開始,我們有提到所謂的回合、區段、與incre,在此,討論到最後一個loop,我們可以對這些名詞有完整的交代。
Shell sort一開始將區段數目(也就是incre)定為last/2(陣列大小的一半),這也是第1個pass的區段數目,當執行此pass的陣列掃描時,依靠往回檢查,將各各區段排序好。接著再將incre除以2(所以每一pass的區段數目是逐漸減小的),並重複相同的作業。所以,最終incre會為1,也就是區段數目為1,也就是整個陣列就是1個區段,當往回檢查將此區段排序好時,就是將整個陣列排序好。
所以要為外層loop宣告一個incre的index variable,其初值為last/2,loop每執行一次,incre的變化是再小一半。

程式碼:
1 incre = last/2
2 loop(incre not 0)
3 current = incre
4 loop(current <= last)
5 walker = current - incre
6 old = list[current]
7 loop( walker >= 0 AND hold < list[walker] )
8 list[walker + incre] = list[walker]
9 walker = walker – incre
10 end loop
11 list[walker + incre] = hold
12 current = current + 1
13 end loop
14 incre = incre/2
15 end loop

line 1:
Incre初值設定。

line 2:
loop的條件,incre為0時跳出。

line 14:
loop的index variable的變化。


tigereye30100 edited on 2007-10-02 18:23
reply to postreply to post
話題樹型展開
人氣 標題 作者 字數 發文時間
5205 shell sort舉世第一個快速排序法 tigereye30100 8492 2007-10-02 18:19
4386 Re:shell sort舉世第一個快速排序法 Disk 49 2007-10-03 15:30
4616 Re:shell sort舉世第一個快速排序法 worookie 177 2007-10-03 16:07
5747 Re:shell sort舉世第一個快速排序法 tigereye30100 359 2007-10-03 17:23
4956 Re:shell sort舉世第一個快速排序法 yahoo1234tw 57 2007-10-03 17:46
4708 Re:shell sort舉世第一個快速排序法 hkdennis2k 343 2007-10-04 00:45
» JWorld@TW »  交流、聊天、灌水

reply to postflat modego to previous topicgo to next topic
  已讀文章
  新的文章
  被刪除的文章
Jump to the top of page

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8