排序算法外文翻譯

1、<p><b>　　中文3355字</b></p><p><b>　　畢 業(yè) 論 文</b></p><p>　　外 文 文 獻 譯 文 及 原 文</p><p>　　學(xué) 生： </p><p>　　學(xué) 號：

2、 </p><p>　　院 （系）： 理學(xué)院 </p><p>　　專 業(yè)： 信息與計算科學(xué) </p><p>　　指導(dǎo)教師： </p><p>　　2014 年 6 月 20 日</p><p><b>　　排序&

3、lt;/b></p><p><b>　　1 內(nèi)部排序</b></p><p>　　目前已經(jīng)發(fā)明了許多不同的排序算法，我們將在本書討論其中大約25個算法。這樣頗使人驚訝的眾多方法，實際上還只是迄今已經(jīng)想出算法的一小部分；在我們的討論中，將略取許多現(xiàn)在已經(jīng)被廢棄的方法，或者緊緊的提及他們。為什么會有那么多的排序算法呢？在計算機的程序設(shè)計中，常有“為什么會有這樣多的

4、x方法呢？”的問題，其中x就是某個問題的集合。這個問題的答案是：每種方法都有它的優(yōu)點和缺點，對于某些數(shù)據(jù)和硬件的配置來說，它就有可能超過其它的方法?？上?，還不知道“最好”的排序方法；目前許多最好的方法，都是針對的、特定的機器，根據(jù)特定的目的，對特定對象進行排序所得到的。用Rudyard Kipling的話說：“有69種進行部落安置的方法，而且它們每一種都是對的?！?lt;/p><p>　　一個好的想法是學(xué)習(xí)每種排序方

5、法，它能幫助你具體的應(yīng)用做出明智的選擇。幸而，學(xué)習(xí)這些算法并不是一項艱難的任務(wù)，因為他們都以有趣的方式相互關(guān)聯(lián)著。</p><p>　　在本章開始時，已經(jīng)定義了將在排序研究中使用的基本術(shù)語和符號：記錄</p><p><b>　　（1-1）</b></p><p>　　有待安排你鍵碼的非減次序進行排序，實質(zhì)上要求找出一個排列使得</p&g

6、t;<p><b>　　（1-2）</b></p><p>　　在本節(jié)中，我們討論內(nèi)部排序，此時，有待排序的記錄個數(shù)足夠小，以致整過過程都能在一臺計算機的高速存儲器中實現(xiàn)。</p><p>　　在某些情況下，會要求在存儲器中對這些記錄物理地重新排列，使得它們的鍵碼按次序排列。但在另外的情況下，則可能只要指明這個排序的某個輔助表就能夠了。如果每個記錄或鍵碼

7、要占用相當多的計算機存儲器，則構(gòu)造一個新的指向記錄的鏈接地址表，并處理這些鏈表地址，而不是到處移動龐大的記錄，通常更好些。這種方式稱為地址表排序。如果鍵碼很短，但是記錄的附屬信息很長，則為了獲得更高的速度，這個鍵碼即可用作鏈接地址，這就是所謂的鍵碼排序。另外一種排序方案利用了包括在每個記錄中的一個輔助鏈接字段；鏈接的方式是使這些記錄最終被鏈接在一起形成一個直接的線性表，每個鏈接指向下一個記錄，這就是所謂的表排序。</p>

8、<p>　　在用地址表方法或表方法進行排序之后，諸記錄可像所希望的那樣，重新排成遞增的順序。只要求足夠容納所有記錄的新區(qū)域。后一方法通常比頭一個方法快兩倍，但是幾乎要兩倍的存儲空間。在許多應(yīng)用中，全然不需要移動記錄，因為對于隨后的尋址操作而言，使用鏈接字段通常已經(jīng)足夠了。 </p><p>　　我們將通過4個方面來說明將要深入討論的所有排序方法，即</

9、p><p>　　a）算法的一個英語語言描述；</p><p><b>　　b）一個框圖</b></p><p>　　c）一個MIX程序；</p><p>　　d）一個排序方法的實例，它應(yīng)用與某個16個數(shù)的集合。 </p><p>　　為了方便起見，MIX程序通常都假定鍵碼是數(shù)值，并且能放到一個單子中

10、去；有時，甚至把鍵碼限制為一個字的一部分。次序關(guān)系“<”將是通常的算術(shù)次序；記錄將只由鍵碼</p><p>　　組成，而沒有附屬的信息。這些假定使得程序更短和更容易理解。讀者應(yīng)當發(fā)現(xiàn)，使用地址表排序或表排序，將通過MIX程序進行。 </p><p>　　1.1 通過計數(shù)進行排序 </p><p>　　作為研究內(nèi)部排序的一個簡單示例，考慮在本章開頭的“計數(shù)”思

11、想。這個簡單的方法是這樣一個思想為基礎(chǔ)的，即在最后排好序的序列中，第j個鍵碼恰恰大于（j-1）個其它鍵碼，換言之。如果知道某個鍵碼確實超過27個其它鍵碼，而且沒有兩個鍵碼相同，則在排序之后對應(yīng)的記錄應(yīng)當進入位置28。所以，這個思想是比較每對鍵碼，計算有多少個鍵碼小于每一個特地給的鍵碼。</p><p>　　進行這些比較的明顯方式是</p><p><b>　　對于</b&g

12、t;</p><p><b>　　對于</b></p><p>　　但容易看出，這些比較中有一半以上是多余的，因為沒有必要把一個鍵碼同它自己進行比較。沒有必要比較Ka和Kb。我們只需要比較</p><p><b>　　對于</b></p><p><b>　　對于</b><

13、;/p><p>　　只需比較Ki和Kj。因此導(dǎo)出了下列算法。</p><p><b>　　算法c</b></p><p>　　本算法通過一張輔助表COUNT[1],......,COUNT[N],，對于小于一個給定鍵碼的鍵碼個數(shù)進行計數(shù)，來實現(xiàn)用鍵碼對記錄進行排序，算法結(jié)束時，COUNT[j]+1來確定Ri的最后位置。</p><

14、;p>　　C1：[清空COUNT] 把COUNT[1]至COUNT[N]都置成0。</p><p>　　C2：[對i進行循環(huán)] 對i=N，N-1,....2實施步驟C3，然后結(jié)束次算法。</p><p>　　C3：[對j進行循環(huán)] 對j=i-1，i-2,...,1實施步驟C4.</p><p>　　C4：[比較Ki和Kj] 如果Ki<Kj，則COUNT[

15、j]加1，否則COUNT[i]+1。</p><p>　　注意：次算法不涉及記錄的移動，它類似地址表排序，因為COUNT表確定這些記錄最后安排，但是由于COUNT[j]高速我們往何處移動Rj，而不是哪一個記錄應(yīng)當被移動Ri的位置，故它與地址表排序略有不同。</p><p>　　通過計數(shù)進行排序，還有另外一個方法，從有效的觀點看，它十分重要的：它主要應(yīng)用于許多相同的鍵碼出現(xiàn)，且所有的鍵碼都落

16、入范圍u≤kj≤v的情況，其中（v-u）很小。這些假定看來十分嚴格的限制，但是事實上將看到這一思想有不少的應(yīng)用。列如，如果把這個算法的應(yīng)用與鍵碼的頭幾位數(shù)，而不是整個鍵碼，則這個文件被部分地排序，而且這項任務(wù)將相當簡單。</p><p>　　1.2 通過插入進行排序</p><p>　　有一類重要的排序技術(shù)，是以1.2節(jié)開頭處提到的“玩橋牌者”的方法為基礎(chǔ)的，在考察記錄Rj之前，假定以前的

17、記錄已經(jīng)排好序，然后已經(jīng)把Ri插入到已經(jīng)排好的諸多記錄的適當位置。這個基本主題可以由若干有趣的變形。</p><p>　　1.2.1 直接插入</p><p>　　最簡單的插入排序也是最顯然的。假定，而且已經(jīng)把記錄重新排好序，使得</p><p>　　把新鍵碼Kj依次地和Kj-1,...,k3,k2..進行比較，直到發(fā)現(xiàn)Rj應(yīng)當插入到Ri和Ri+1處。如下列算法所示

18、那樣，宜于把比較和移動操作組合在一起，互相穿插，由于Rj“被安放到適當?shù)膶哟沃袇^(qū)”，這種排序方式通常稱為篩選或陷入技術(shù)。</p><p>　　算法S（直接插入排序）重新安排記錄到適當位置；在完成排序之后，它們的鍵碼是有序的，即有。</p><p>　　S1 [對j進行循環(huán)] 對于j=2,3,...,N實施步驟S2到S5；然后終止本算法。</p><p>　　S2 [

19、給i，K，R賦值] 置i←j-1，K←Kj，R←Rj</p><p>　　S3 [比較K:Ki] 如果則轉(zhuǎn)向步驟S5.</p><p>　　S4 [移動Ri，i減值] 置Ri+1←Ri，然后i←i-1。如果i>0，則返回到步驟S3。</p><p>　　S5 [R進入Ri+1] 置Ri+1←R。</p><p>　　1.2.2 二叉插入

20、和兩路插入</p><p>　　在一個直接插入排序期間，在處理第j個記錄時，平均說來要把它的鍵碼大約同1/2j個此前已排好的鍵碼進行比較，因此所實施比較的總數(shù)大約是1/2（1+2+3+...+N）=1/4N2,當N適當大時，這就已經(jīng)非常之大了。在6.2.1小節(jié)，將研究“二分查找”技術(shù)，該技術(shù)使我們能夠在僅僅lgN次仔細選擇的比較之后，就指出在那里插入第j項。例如，當插入第64個記錄時，可以由對K64和K32進行比

21、較開始。如果是小于，則就把它同K16進行比較，但如果是大于，則就把它同K65進行比較，等等。于是僅僅做6次比較之后，就可知道R64應(yīng)查如得位置。插入所有N項所作的比較總數(shù)就大學(xué)時NlgN，這是對于1/4N2的實質(zhì)性的改進。而6.2.1小節(jié)表示，它早在1946年就由John Mauchly在計算機排序的第一個公開討論中述及。</p><p>　　二叉插入的困難時，它只解決問題的一半。在已經(jīng)發(fā)現(xiàn)記錄Rj應(yīng)插入到那里之

22、后，仍然需要移動大的1/2j個此前已排序好的記錄，以便Ri騰出位置，所以總共的運行時間實質(zhì)上仍同N2成正比。</p><p>　　當然，一個靈巧的程序員可以相處各種方式來減少所需要移動的數(shù)量；頭一個這樣的技巧，如表2所示，是早在50年代時就提出的，表中排序的頭一項被放置在一個輸出區(qū)域的中心，而且通過向右或向左移動騰出空間。此法比普通二叉插入節(jié)省一半運行時間，其代價是程序稍微復(fù)雜一點，使用此法時，還可以不必使用N個

23、記錄所需要的更多的空間；但對于這個“兩路”插入的方法，將不作更詳細的敘述因為已有更多有趣的方法。</p><p>　　1.2.3 Shell方法</p><p>　　如果有這樣的一份排序算法，它一次只把諸多項目移動一個位置，則它的平均運行時間最好也是同N2的成比例。因為在這個排序過程中每個記錄都必須平均遍歷1/3N個位置。因此，如果直接對插入作實質(zhì)性的改進，就需要一種新原理，它是這些記錄作

24、長距離的跳躍，而不是一些短促的小步移動。</p><p>　　這樣一個方法是由Donald.L.Shell于1959年提出的，我們稱它為Shell排序，表3說明該法的一般想法：首先把這16個記錄分成8組即（R1，R9），（R2，R10），...，（R8，R16）。分別對每組記錄進行排序。使我們進到表3的第二行，這稱為“第一次掃描”。</p><p><b>　　表3 增量遞減排序

25、</b></p><p>　　Shell排序也叫做“減少增量的排序”，因為每一遍通過增量h來確定，使得我們對相距h個單位進行排序。任何序列h1，hi-1，..，hn都可以使用此方法，只要最后的增量h0=1就行。</p><p><b>　　小結(jié)</b></p><p>　　既然我們已經(jīng)接近著極為冗長的一章結(jié)尾，我們最好“整理出”已研

26、究過的最為重要的事實。</p><p>　　用于排序的一個算法，是一個這樣的過程，它重新安排一個文件的所有記錄，使得其碼處于遞增的次序，這有序的排列是有用的，因為它把相同的記錄放到一起，允許有效的處理按同一個鍵碼排好的多個文件，這導(dǎo)致了有效的檢索方法，而且是計算機的刪除看上去不那么的混亂。如果無論是對那一種應(yīng)用，或無論正在使用什么樣的計算機，僅僅有一兩種排序方法，它比所有的排序方法都好，那么，事情倒好結(jié)局，事實上

27、，每種方法都有各自的優(yōu)點。因此所有的方法都要去記，因為在特地的環(huán)境中，它們是最好的。</p><p><b>　　參考文獻</b></p><p>　　[1] Bell，D．The principles of sorting．The Computer Journal 1 (1958)：71–77．</p><p>　　[2] Bose，R. C

28、，and Nelson，R.J．A sorting problem．Journal of the ACM (JACM) 9，2 (1962)：28–296．</p><p>　　[3] Halstead，M. H．Elements of Software Science．Operating．a(chǎn)nd Programming Systems Series，vol．7．Elsevier, 1977：71–77．<

29、/p><p><b>　　Sorting</b></p><p>　　1 Internal Sorting</p><p>　　Many different sorting algorithms have been invented,and we will be discussing about 25 of them in this book. T

30、his rather alarming number if methods is actually only a fraction the algorithms that have been devised so far;many methods which are now obsolete will be omitted from our discussiong,ir mentioned only briefly why are th

31、ere so many sorting methods ? For computer programming this is a special case of question,”why are there so many x methods?”, where x ranges over the set of problems; an</p><p>　　It is a good idea to learn t

32、he characteristics of each sorting method, so that an inerlligent choice can be made for particular applications Fortunately,it is not a formidable task to learn these algorithms,since they are inerrelated in intersting

33、ways.</p><p>　　At the beginning of this chaper we define the basic terminnology and notation to be used in our study of sorting: the records</p><p><b>　　(1-1)</b></p><p>

34、;　　Are sorting into nondereasing order of their keysesentially by discovering a permutation p(1) p(2)...p(N) such that </p><p><b>　?。?-2）</b></p><p>　　In the present section we are c

35、oncerned with inernal sorling ,when the number of records to be sorting is small enough that the entire process can be performed in a computers high-speed memory.</p><p>　　In some cases will want records to

36、be physiscally rearranged in memory so that their keys are in order ,while in orher cases in may be sufficient merely to have an auxiliary table of some sort which specifies the permutation. If the records and/or the key

37、s each take up quite a few table words of computer memoty , it is often better to make up a new table of link addresses whic point to the records, and to manipulate these link addresses instead of moving the bulky record

38、s around. This method is </p><p>　　All of sorting methods which we shall examine “in depth” will be illustrate in four ways,by means of</p><p>　　a) an English-language description of the algotit

39、hm,</p><p>　　b) flow diagram,</p><p>　　c) a MIX program,</p><p>　　d) an example of the sorting method applied to a given set of number.</p><p>　　An analysis of the runn

40、ing time of each sorting will be give with the MIX programs.</p><p>　　1.1 Sorting by counting</p><p>　　As a simple example of the way in which we shall study inernal sorting methods,lect us cons

41、ider the “ounting” idea mentioned near the beginning of this secion. This simple method is based on the idea that the jth key in the final sorted sequence is greater than exactly (j--1) of the other keys.Putting this ano

42、ther way.if we know that a certain key exceeds exactly 27 others,the corresponding record should go into position 28 after sorting.So the idea is to compare each pair of keys,counting how </p><p>　　The obbi

43、ous way to do the comparisons is to</p><p><b>　　. For </b></p><p><b>　　For </b></p><p>　　But it is easy to see that over half of these comparison are redund

44、at,since it is unnessary to compare a key with itself, and it is unnessary to compare Ka with Kb and later to compare ..with....we need merely to</p><p><b>　　For </b></p><p><b>

45、;　　For </b></p><p>　　Algorithm c(comparison counting) </p><p>　　This algorithm sorts COUNT[1],...,COUNT[N] on the keys by maintaining less than a given key . After the conclusion of the a

46、lgorithm,count[j]+1 specifies the final position of record</p><p>　　C1[clear Counts] Set Count[1] through COUNT[N] to zero.</p><p>　　C2[Loop on i.] Perform step C3,for i = N,N-1,...,2;then termi

47、nate the algorithm.</p><p>　　C3.[Loop on j.] Perform step C4,for j = i - 1,i - 2,...,1.</p><p>　　C4.[Compare Ki,Kj.] If Ki<Kj,increase COUNT[j] by 1;otherwise,increase COUNT[i] by 1.</p>

48、;<p>　　Note that this algorithm involves no movement of records.It is similar to an address table sort,since the COUNT table specifies the final arrangement of records;but it is somewhat differrent because COUNT[j

49、] tells us where to move Rj,instead of indicating which record should be moved into the place of Rj.(Thus the “inverse” of the permutation p(1)...p(n) is specified in the COUNT table;see Section 1.1.1).</p><p&

50、gt;　　In our discussion preceding this algorithm we failed to consider the posibility of equal keys.This is a potentially serious omission,for if equal keys complicated to equal COUNTs the final rearrangement of records w

51、ould be rather complicated.Fortunately,as exercise 2 shows,Algorithm C gives the correct result no matter how many equal keys are present.</p><p>　　Program C(Comparison counting).</p><p>　　The f

52、ollowing MTX implementation of Algorithm C assumes that Rj is stored in location INPUT+j,and COUNT[j] in location COUNT + j,for 1≤j≤N;rI1=i;rI2=j;rA=Ki=Ri;rX=COUNT[i].</p><p>　　The running time of this progr

53、am is 13N+6A+5B-4 units,where N is the number of records;A is the number of choices of two things from a set of N objects,namely ()=(N2-N)/2。</p><p>　　1.2 Sorting by Insertion </p><p>　　One of i

54、mportant families of sorting techniques is based on the “bridge player” method mentioned near the beginning of Section 1.2: Before examing record Rj,we assume that the preceding recordshave aready been sorted; then we in

55、sert Ri into its proper place among the previously sorted records. Several interesting variations on basic theme are possible.</p><p>　　1.2.1 Straight insertion</p><p>　　The simplest insertion s

56、ort is most obvious one.Assume that 1<j≤N and that record have been rearranged so that </p><p>　　We compare the way key Kj with Kj-1,...,k3,k2..,in turn,until discovering that Ri should be inserted betwee

57、n records Ri and Ri+1;then we move records. </p><p>　　Algorithm S(Straight insertion sort). Records are rearranged in place; after sorting is complete,their keys will be in order,.</p><p>　　S1.[

58、Loop on j] Perform steps S2 through S5 for j=2,3,..,N; then terminate the algorithem.</p><p>　　S2.[Set up i,K,R] Set i←j-1，K←Kj，R←Rj</p><p>　　S3.[Compare K,Ki] If K≥Ki go to S5.</p><p

59、>　　S4.[Move Ri,decrease j] Set Ri+1←Ri,then i←i-1.If i>0，go back S3.</p><p>　　S5.[R into Ri+1] Set Ri+1←R.</p><p>　　1.2.2 Binary insertion and two-way insertion.</p><p>　　Whil

60、e the jth record is being pracessed during a straight insertion sort,we compare its key with about 1/2j of the previously sorted keys,on the average;therefore the total number of comparisons performed comes to about 1/2(

61、1+2+...+N)≈1/2N2,and this gets very large when N is only moderately large. In Section 6.2.1 we shall study “Binary search” techniques ,which show where to insert the jth item after only about log2j well-chosen comparison

62、s have been made.For example ,when inserting the 64th re</p><p>　　The unfortunate difficulty with binary insertion is that it sovles only half of the problem; after we we have found where record Rj is to be

63、inserted, we still need to move about 1/2*j of the previously sort records in order to make room for Rj，so the total running time is still essentially proportional to N2。</p><p>　　Of course, a clever program

64、mer can think of various ways to reduce the amount of moving that is necessary; the first such trick, propose early in the 1950’s, is illustrated in table.Here the first item is placed in the center of an output area, an

65、d space is made for subsequent items by moving to the right or to the left, whichever is most convenient. This saves about half the running time of ordinary binary insertion, at the expense of a somewhat more complicated

66、 program, It is possible to use t</p><p>　　1.2.3 Shell’s method</p><p>　　If we have a sorting algorithm which moves items only one position at a time, its average running time will be,at best,pr

67、oportional to N2, since each record must travel an average of about 1/3*N positions during the sorting process. Therefore,if we want to make substantial improvements over straight insertion, we need some mechanise by whi

68、ch the records can take long leaps instead of short steps.</p><p>　　Such a method was proposed in 1950 by Donald L.Shell,we shall call it the diminishing increment sort.Table 3 illustrates the general idea b

69、ehind his method; Fist we divide the 16 records into 8 groups of two each,（R1，R9），（R2，R10），...，（R8，R16）.Sorting each group of records separetely takes us to the second line of Table 3; this is called the “first pass”.<

70、;/p><p><b>　　Table3</b></p><p>　　DIMINSHING INCREMENTSORT</p><p>　　The sequence of increments 8，4，2，1 is not sacred;any sequence h1，hi-1，..,hn can be used, so long as last

71、incement h1 equals 1. Some squences are much better than others; we will discuss the choice of increments later.</p><p>　　Conclusion</p><p>　　Now that we are close to the end of a very long chap

72、ter, we best "sort out" has been studied the most important facts. </p><p>　　An algorithm for sorting, is one such process, which rearrange all the records of a file, so that in the ascending order

73、 of their number, which is an ordered arrangement is useful because it is put together with the recording of the same, allowing effective treatment at the same keycode good discharge more than one file, which leads to an

74、 efficient search method is to remove the computer and look less confusion. If an application either for it, or whatever is what computers use, just having one </p><p>　　Therefore, all the methods have to re

75、member, because in an environment specifically, they are the best.</p><p><b>　　Reference</b></p><p>　　[1] Bell，D．The principles of sorting．The Computer Journal 1 (1958)：71–77．</p&

76、gt;<p>　　[2] Bose，R. C，and Nelson，R.J．A sorting problem．Journal of the ACM (JACM) 9，2 (1962)：28–296．</p><p>　　[3] Halstead，M. H．Elements of Software Science．Operating．a(chǎn)nd Programming Systems Series，vo