青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 297,  comments - 15,  trackbacks - 0

Radix sort is the algorithm used by the card-sorting machines you now find only in computer museums. The cards are organized into 80 columns, and in each column a hole can be punched in one of 12 places. The sorter can be mechanically "programmed" to examine a given column of each card in a deck and distribute the card into one of 12 bins depending on which place has been punched. An operator can then gather the cards bin by bin, so that cards with the first place punched are on top of cards with the second place punched, and so on.

For decimal digits, only 10 places are used in each column. (The other two places are used for encoding nonnumeric characters.) A d-digit number would then occupy a field of d columns. Since the card sorter can look at only one column at a time, the problem of sorting n cards on a d-digit number requires a sorting algorithm.

Intuitively, one might want to sort numbers on their most significant digit, sort each of the resulting bins recursively, and then combine the decks in order. Unfortunately, since the cards in 9 of the 10 bins must be put aside to sort each of the bins, this procedure generates many intermediate piles of cards that must be kept track of. (See Exercise 8.3-5.)

Radix sort solves the problem of card sorting counterintuitively by sorting on the least significant digit first. The cards are then combined into a single deck, with the cards in the 0 bin preceding the cards in the 1 bin preceding the cards in the 2 bin, and so on. Then the entire deck is sorted again on the second-least significant digit and recombined in a like manner. The process continues until the cards have been sorted on all d digits. Remarkably, at that point the cards are fully sorted on the d-digit number. Thus, only d passes through the deck are required to sort. Figure 8.3 shows how radix sort operates on a "deck" of seven 3-digit numbers.

 

Figure 8.3:
The operation of radix sort on a list of seven 3-digit numbers. The leftmost column is the input. The remaining columns show the list after successive sorts on increasingly significant digit positions. Shading indicates the digit position sorted on to produce each list from the previous one.

It is essential that the digit sorts in this algorithm be stable. The sort performed by a card sorter is stable, but the operator has to be wary about not changing the order of the cards as they come out of a bin, even though all the cards in a bin have the same digit in the chosen column.

In a typical computer, which is a sequential random-access machine, radix sort is sometimes used to sort records of information that are keyed by multiple fields. For example, we might wish to sort dates by three keys: year, month, and day. We could run a sorting algorithm with a comparison function that, given two dates, compares years, and if there is a tie, compares months, and if another tie occurs, compares days. Alternatively, we could sort the information three times with a stable sort: first on day, next on month, and finally on year.

The code for radix sort is straightforward. The following procedure assumes that each element in the n-element array A has d digits, where digit 1 is the lowest-order digit and digit d is the highest-order digit.

RADIX-SORT(A, d)
1  for i  1 to d
2     do use a stable sort to sort array A on digit i
Lemma 8.3
Start example

Given n d-digit numbers in which each digit can take on up to k possible values, RADIX-SORT correctly sorts these numbers in Θ(d(n + k)) time.

Proof The correctness of radix sort follows by induction on the column being sorted (see Exercise 8.3-3). The analysis of the running time depends on the stable sort used as the intermediate sorting algorithm. When each digit is in the range 0 to k-1 (so that it can take on k possible values), and k is not too large, counting sort is the obvious choice. Each pass over n d-digit numbers then takes time Θ(n + k). There are d passes, so the total time for radix sort is Θ(d(n + k)).

End example

When d is constant and k = O(n), radix sort runs in linear time. More generally, we have some flexibility in how to break each key into digits.

Lemma 8.4
Start example

Given n b-bit numbers and any positive integer r b, RADIX-SORT correctly sorts these numbers in Θ((b/r)(n + 2r)) time.

Proof For a value r b, we view each key as having d = b/r digits of r bits each. Each digit is an integer in the range 0 to 2r - 1, so that we can use counting sort with k = 2r - 1. (For example, we can view a 32-bit word as having 4 8-bit digits, so that b = 32, r = 8, k = 2r - 1 = 255, and d = b/r = 4.) Each pass of counting sort takes time Θ(n + k) = Θ(n + 2r) and there are d passes, for a total running time of Θ(d(n + 2r )) = Θ((b/r)(n + 2r)).

End example

 

For given values of n and b, we wish to choose the value of r, with r b, that minimizes the expression (b/r)(n + 2r). If b < lg n, then for any value of r b, we have that (n + 2r) = Θ(n). Thus, choosing r = b yields a running time of (b/b)(n + 2b) = Θ(n), which is asymptotically optimal. If b lg n, then choosing r = lg n gives the best time to within a constant factor, which we can see as follows. Choosing r = lg n yields a running time of Θ(bn/ lg n). As we increase r above lg n, the 2r term in the numerator increases faster than the r term in the denominator, and so increasing r above lg n yields a running time of Θ(bn/ lg n). If instead we were to decrease r below lg n, then the b/r term increases and the n + 2r term remains at Θ(n).

Is radix sort preferable to a comparison-based sorting algorithm, such as quick-sort? If b = O(lg n), as is often the case, and we choose r lg n, then radix sort's running time is Θ(n), which appears to be better than quicksort's average-case time of Θ(n lg n). The constant factors hidden in the Θ-notation differ, however. Although radix sort may make fewer passes than quicksort over the n keys, each pass of radix sort may take significantly longer. Which sorting algorithm is preferable depends on the characteristics of the implementations, of the underlying machine (e.g., quicksort often uses hardware caches more effectively than radix sort), and of the input data. Moreover, the version of radix sort that uses counting sort as the intermediate stable sort does not sort in place, which many of the Θ(n lg n)-time comparison sorts do. Thus, when primary memory storage is at a premium, an in-place algorithm such as quicksort may be preferable

 

 

 

posted on 2010-08-03 21:43 chatler 閱讀(928) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用鏈接

留言簿(10)

隨筆分類(307)

隨筆檔案(297)

algorithm

Books_Free_Online

C++

database

Linux

Linux shell

linux socket

misce

  • cloudward
  • 感覺這個博客還是不錯,雖然做的東西和我不大相關,覺得看看還是有好處的

network

OSS

  • Google Android
  • Android is a software stack for mobile devices that includes an operating system, middleware and key applications. This early look at the Android SDK provides the tools and APIs necessary to begin developing applications on the Android platform using the Java programming language.
  • os161 file list

overall

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            狠狠色综合网站久久久久久久| 亚洲人成网站色ww在线| 欧美国产日韩一区二区| 国产精品草莓在线免费观看| 亚洲国产欧美日韩| 国产亚洲欧美日韩精品| 一区二区三区成人精品| 日韩视频永久免费观看| 久热综合在线亚洲精品| 久久躁狠狠躁夜夜爽| 国产一级精品aaaaa看| 亚洲欧美制服中文字幕| 欧美一区午夜视频在线观看| 国产精品你懂得| 中国成人在线视频| 亚洲一区二区成人在线观看| 欧美视频一区| 中日韩美女免费视频网址在线观看 | 亚洲美女91| 日韩午夜av电影| 欧美激情亚洲国产| 亚洲精品久久7777| 亚洲性色视频| 国产精品一卡二| 新片速递亚洲合集欧美合集| 久久动漫亚洲| 在线欧美电影| 欧美激情第五页| 99re6热在线精品视频播放速度| 99国产精品私拍| 国产精品久久国产精品99gif| 亚洲婷婷免费| 久久亚洲精品欧美| 亚洲国产精品久久91精品| 欧美成熟视频| 中文欧美在线视频| 久久久久久久999精品视频| 亚洲高清不卡在线| 欧美啪啪一区| 亚洲免费中文字幕| 免费久久99精品国产| 亚洲精品免费在线播放| 欧美新色视频| 久久精品国产第一区二区三区| 欧美激情影院| 新狼窝色av性久久久久久| 一区二区三区在线视频播放 | 久久精品国产一区二区电影| 欧美国产极速在线| 亚洲在线一区二区| 亚洲成人资源网| 欧美日韩综合在线免费观看| 欧美在线电影| 亚洲肉体裸体xxxx137| 久久国产精品免费一区| 亚洲人成网站999久久久综合| 国产精品高潮视频| 美女精品在线观看| 亚洲自拍高清| 亚洲国产影院| 久久久久久久综合狠狠综合| 99re6这里只有精品| 国产亚洲一区二区三区在线观看 | 欧美日韩视频在线| 久久国产精品久久精品国产| 999在线观看精品免费不卡网站| 久久久久久久综合色一本| 一本色道久久综合亚洲二区三区| 久久理论片午夜琪琪电影网| 亚洲日本视频| 国内自拍视频一区二区三区| 欧美日韩国产区| 久久女同互慰一区二区三区| 中国成人黄色视屏| 91久久精品国产91性色tv| 久久亚洲综合色| 亚洲欧美日韩在线播放| 亚洲免费黄色| 亚洲国产婷婷香蕉久久久久久99| 国产伦精品一区二区三区视频黑人| 欧美成人国产va精品日本一级| 午夜宅男久久久| 中文在线不卡| 一区二区三区国产精华| 亚洲国产裸拍裸体视频在线观看乱了中文 | 亚洲免费视频在线观看| 性欧美video另类hd性玩具| 欧美一区二区三区喷汁尤物| 久久综合一区二区| 亚洲第一在线| 一区二区三区国产在线观看| 午夜亚洲性色视频| 裸体歌舞表演一区二区| 欧美日韩视频不卡| 国产亚洲精品久久飘花| 亚洲国产欧美一区二区三区久久 | 在线午夜精品自拍| 久久精品国产96久久久香蕉| 欧美国产激情| 亚洲一区二区高清| 久久久亚洲影院你懂的| 欧美日韩一区二区在线视频| 国产一区二区三区在线观看免费视频| 在线不卡免费欧美| 亚洲一区二区av电影| 久久综合给合久久狠狠狠97色69| 亚洲国产一区二区三区a毛片| 亚洲午夜免费福利视频| 女主播福利一区| 国产精品免费一区豆花| 亚洲国产天堂久久国产91| 亚洲欧美国内爽妇网| 欧美福利在线| 亚洲欧美视频在线观看| 欧美搞黄网站| 国内精品国产成人| 亚洲视频二区| 欧美激情一区二区三区在线| 亚洲资源av| 欧美日韩国产在线| 激情综合电影网| 亚洲欧美精品在线| 最新国产成人av网站网址麻豆| 欧美影片第一页| 国产精品久久国产精品99gif | 欧美国产精品中文字幕| 国一区二区在线观看| 亚洲欧美日韩精品久久久| 欧美黑人在线观看| 久久se精品一区精品二区| 国产精品久久久久久久电影| 亚洲精品免费一区二区三区| 另类成人小视频在线| 午夜宅男欧美| 国产精品网站在线| 亚洲一区二区三区在线看| 亚洲国产欧美一区| 免费影视亚洲| 亚洲东热激情| 美女任你摸久久| 久久精品91久久久久久再现| 国产欧美一区二区视频| 香蕉久久夜色精品国产| 亚洲视频在线观看三级| 国产精品v日韩精品| 亚洲午夜极品| 中国亚洲黄色| 国产精品久久久久久久久久尿| 99热这里只有精品8| 亚洲韩国精品一区| 欧美mv日韩mv国产网站| 亚洲欧洲一二三| 亚洲国产精品小视频| 欧美成年人视频网站| 亚洲国产日韩一区二区| 欧美黑人在线观看| 欧美国产亚洲另类动漫| 亚洲免费高清| 日韩一二三在线视频播| 欧美特黄a级高清免费大片a级| 亚洲视频在线看| 在线综合亚洲欧美在线视频| 国产精品久久久久久久久久免费 | 国产精品任我爽爆在线播放| 欧美一级一区| 欧美在线免费观看亚洲| 伊人婷婷久久| 欧美国产高清| 欧美日本免费| 亚洲免费在线观看| 午夜精品理论片| 伊人成年综合电影网| 欧美国产精品劲爆| 欧美人与禽猛交乱配视频| 在线视频日韩| 亚洲欧洲av一区二区| 一区视频在线看| 亚洲国产美女久久久久| 欧美系列一区| 久久免费99精品久久久久久| 久久综合999| 中文精品在线| 欧美伊人精品成人久久综合97| 亚洲国产成人精品久久久国产成人一区| 亚洲成色精品| 国产精品久久夜| 玖玖玖国产精品| 欧美连裤袜在线视频| 午夜伦欧美伦电影理论片| 欧美一区二区在线播放| 91久久综合| 亚洲一区二区在线看| 亚洲高清成人| 在线视频欧美精品| 精品成人一区二区三区| 亚洲精品日韩在线| 国产一区二区三区不卡在线观看| 亚洲大片精品永久免费| 国产欧美日韩精品在线| 欧美激情精品久久久久久久变态|