『壹』 如何確定Kafka的分區數，key和consumer線程數
一、客戶端/伺服器端需要使用的內存就越多
先說說客戶端的情況。Kafka 0.8.2之後推出了java版的全新的procer，這個procer有個參數batch.size，默認是16KB。它會為每個分區緩存消息，一旦滿了就打包將消息批量發出。看上去這是個能夠提升性能的設計。不過很顯然，因為這個參數是分區級別的，如果分區數越多，這部分緩存所需的內存佔用也會更多。假設你有10000個分區，按照默認設置，這部分緩存需要佔用約157MB的內存。而consumer端呢？我們拋開獲取數據所需的內存不說，只說線程的開銷。如果還是假設有10000個分區，同時consumer線程數要匹配分區數(大部分情況下是最佳的消費吞吐量配置)的話，那麼在consumer client就要創建10000個線程，也需要創建大約10000個Socket去獲取分區數據。這裡面的線程切換的開銷本身已經不容小覷了。
伺服器端的開銷也不小，如果閱讀Kafka源碼的話可以發現，伺服器端的很多組件都在內存中維護了分區級別的緩存，比如controller，FetcherManager等，因此分區數越多，這種緩存的成本越久越大。
二、文件句柄的開銷
每個分區在底層文件系統都有屬於自己的一個目錄。該目錄下通常會有兩個文件： base_offset.log和base_offset.index。Kafak的controller和ReplicaManager會為每個broker都保存這兩個文件句柄(file handler)。很明顯，如果分區數越多，所需要保持打開狀態的文件句柄數也就越多，最終可能會突破你的ulimit -n的限制。
三、降低高可用性
Kafka通過副本(replica)機制來保證高可用。具體做法就是為每個分區保存若干個副本(replica_factor指定副本數)。每個副本保存在不同的broker上。期中的一個副本充當leader 副本，負責處理procer和consumer請求。其他副本充當follower角色，由Kafka controller負責保證與leader的同步。如果leader所在的broker掛掉了，contorller會檢測到然後在zookeeper的幫助下重選出新的leader——這中間會有短暫的不可用時間窗口，雖然大部分情況下可能只是幾毫秒級別。但如果你有10000個分區，10個broker，也就是說平均每個broker上有1000個分區。此時這個broker掛掉了，那麼zookeeper和controller需要立即對這1000個分區進行leader選舉。比起很少的分區leader選舉而言，這必然要花更長的時間，並且通常不是線性累加的。如果這個broker還同時是controller情況就更糟了。
說了這么多「廢話」，很多人肯定已經不耐煩了。那你說到底要怎麼確定分區數呢？答案就是：視情況而定。基本上你還是需要通過一系列實驗和測試來確定。當然測試的依據應該是吞吐量。雖然LinkedIn這篇文章做了Kafka的基準測試，但它的結果其實對你意義不大，因為不同的硬體、軟體、負載情況測試出來的結果必然不一樣。我經常碰到的問題類似於，官網說每秒能到10MB，為什麼我的procer每秒才1MB？ —— 且不說硬體條件，最後發現他使用的消息體有1KB，而官網的基準測試是用100B測出來的，因此根本沒有可比性。不過你依然可以遵循一定的步驟來嘗試確定分區數：創建一個只有1個分區的topic，然後測試這個topic的procer吞吐量和consumer吞吐量。假設它們的值分別是Tp和Tc，單位可以是MB/s。然後假設總的目標吞吐量是Tt，那麼分區數 = Tt / max(Tp, Tc)
Tp表示procer的吞吐量。測試procer通常是很容易的，因為它的邏輯非常簡單，就是直接發送消息到Kafka就好了。Tc表示consumer的吞吐量。測試Tc通常與應用的關系更大， 因為Tc的值取決於你拿到消息之後執行什麼操作，因此Tc的測試通常也要麻煩一些。
另外，Kafka並不能真正地做到線性擴展(其實任何系統都不能)，所以你在規劃你的分區數的時候最好多規劃一下，這樣未來擴展時候也更加方便。
消息-分區的分配
默認情況下，Kafka根據傳遞消息的key來進行分區的分配，即hash(key) % numPartitions，如下圖所示:
def partition(key: Any, numPartitions: Int): Int = {
Utils.abs(key.hashCode) % numPartitions
}
這就保證了相同key的消息一定會被路由到相同的分區。如果你沒有指定key，那麼Kafka是如何確定這條消息去往哪個分區的呢？
復制代碼
if(key == null) { // 如果沒有指定key
val id = sendPartitionPerTopicCache.get(topic) // 先看看Kafka有沒有緩存的現成的分區Id
id match {
case Some(partitionId) =>
partitionId // 如果有的話直接使用這個分區Id就好了
case None => // 如果沒有的話，
val availablePartitions = topicPartitionList.filter(_.leaderBrokerIdOpt.isDefined) //找出所有可用分區的leader所在的broker
if (availablePartitions.isEmpty)
throw new LeaderNotAvailableException("No leader for any partition in topic " + topic)
val index = Utils.abs(Random.nextInt) % availablePartitions.size // 從中隨機挑一個
val partitionId = availablePartitions(index).partitionId
sendPartitionPerTopicCache.put(topic, partitionId) // 更新緩存以備下一次直接使用
partitionId
}
}
復制代碼
可以看出，Kafka幾乎就是隨機找一個分區發送無key的消息，然後把這個分區號加入到緩存中以備後面直接使用——當然了，Kafka本身也會清空該緩存（默認每10分鍾或每次請求topic元數據時）
如何設定consumer線程數
我個人的觀點，如果你的分區數是N，那麼最好線程數也保持為N，這樣通常能夠達到最大的吞吐量。超過N的配置只是浪費系統資源，因為多出的線程不會被分配到任何分區。讓我們來看看具體Kafka是如何分配的。
topic下的一個分區只能被同一個consumer group下的一個consumer線程來消費，但反之並不成立，即一個consumer線程可以消費多個分區的數據，比如Kafka提供的ConsoleConsumer，默認就只是一個線程來消費所有分區的數據。——其實ConsoleConsumer可以使用通配符的功能實現同時消費多個topic數據，但這和本文無關。
再討論分配策略之前，先說說KafkaStream——它是consumer的關鍵類，提供了遍歷方法用於consumer程序調用實現數據的消費。其底層維護了一個阻塞隊列，所以在沒有新消息到來時，consumer是處於阻塞狀態的，表現出來的狀態就是consumer程序一直在等待新消息的到來。——你當然可以配置成帶超時的consumer，具體參看參數consumer.timeout.ms的用法。
下面說說Kafka提供的兩種分配策略： range和roundrobin，由參數partition.assignment.strategy指定，默認是range策略。本文只討論range策略。所謂的range其實就是按照階段平均分配。舉個例子就明白了，假設你有10個分區，P0 ~ P9，consumer線程數是3， C0 ~ C2，那麼每個線程都分配哪些分區呢？
C0 消費分區 0, 1, 2, 3
C1 消費分區 4, 5, 6
C2 消費分區 7, 8, 9
具體演算法就是：
復制代碼
val nPartsPerConsumer = curPartitions.size / curConsumers.size // 每個consumer至少保證消費的分區數
val nConsumersWithExtraPart = curPartitions.size % curConsumers.size // 還剩下多少個分區需要單獨分配給開頭的線程們
...
for (consumerThreadId <- consumerThreadIdSet) { // 對於每一個consumer線程
val myConsumerPosition = curConsumers.indexOf(consumerThreadId) //算出該線程在所有線程中的位置，介於[0, n-1]
assert(myConsumerPosition >= 0)
// startPart 就是這個線程要消費的起始分區數
val startPart = nPartsPerConsumer * myConsumerPosition + myConsumerPosition.min(nConsumersWithExtraPart)
// nParts 就是這個線程總共要消費多少個分區
val nParts = nPartsPerConsumer + (if (myConsumerPosition + 1 > nConsumersWithExtraPart) 0 else 1)
...
}
復制代碼
針對於這個例子，nPartsPerConsumer就是10/3=3，nConsumersWithExtraPart為10%3=1，說明每個線程至少保證3個分區，還剩下1個分區需要單獨分配給開頭的若干個線程。這就是為什麼C0消費4個分區，後面的2個線程每個消費3個分區，具體過程詳見下面的Debug截圖信息：
ctx.myTopicThreadIds
nPartsPerConsumer = 10 / 3 = 3
nConsumersWithExtraPart = 10 % 3 = 1
第一次：
myConsumerPosition = 1
startPart = 1 * 3 + min(1, 1) = 4 ---也就是從分區4開始讀
nParts = 3 + (if (1 + 1 > 1) 0 else 1) = 3 讀取3個分區， 即4,5,6
第二次：
myConsumerPosition = 0
startPart = 3 * 0 + min(1, 0) =0 --- 從分區0開始讀
nParts = 3 + (if (0 + 1 > 1) 0 else 1) = 4 讀取4個分區，即0,1,2,3
第三次：
myConsumerPosition = 2
startPart = 3 * 2 + min(2, 1) = 7 --- 從分區7開始讀
nParts = 3 + if (2 + 1 > 1) 0 else 1) = 3 讀取3個分區，即7, 8, 9
至此10個分區都已經分配完畢
說到這里，經常有個需求就是我想讓某個consumer線程消費指定的分區而不消費其他的分區。坦率來說，目前Kafka並沒有提供自定義分配策略。做到這點很難，但仔細想一想，也許我們期望Kafka做的事情太多了，畢竟它只是個消息引擎，在Kafka中加入消息消費的邏輯也許並不是Kafka該做的事情。
『貳』 快速排序特點
快速排序（Quicksort）是對冒泡排序的一種改進，由東尼·霍爾在1960年提出。 快速排序是指通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序。整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
分類
排序演算法
數據結構
不定
最壞空間復雜度
根據實現的方式不同而不同
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：
從數列中挑出一個元素，稱為「基準」（pivot），
重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（相同的數可以到任何一邊）。在這個分區結束之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
遞歸地（recursively）把小於基準值元素的子數列和大於基準值元素的子數列排序。
遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個演算法一定會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。
在簡單的偽代碼中，此演算法可以被表示為：
function quicksort(q)
{
var list less, pivotList, greater
if length(q) ≤ 1
return q
else
{
select a pivot value pivot from q
for each x in q except the pivot element
{
if x<pivot then add x to less
if x ≥ pivot then add x to greater
}
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
}
原地（in-place）分區的版本
上面簡單版本的缺點是，它需要的額外存儲空間，也就跟歸並排序一樣不好。額外需要的存儲器空間配置，在實際上的實現，也會極度影響速度和緩存的性能。有一個比較復雜使用原地（in-place）分區演算法的版本，且在好的基準選擇上，平均可以達到空間的使用復雜度。
function partition(a, left, right, pivotIndex)
{
pivotValue = a[pivotIndex]
swap(a[pivotIndex], a[right]) // 把pivot移到結尾
storeIndex = left
for i from left to right-1
{
if a[i]<= pivotValue
{
swap(a[storeIndex], a[i])
storeIndex = storeIndex + 1
}
}
swap(a[right], a[storeIndex]) // 把pivot移到它最後的地方
return storeIndex
}
這是原地分區演算法，它分區了標示為"左邊（left）"和"右邊（right）"的序列部分，藉由移動小於的所有元素到子序列的開頭，留下所有大於或等於的元素接在他們後面。在這個過程它也為基準元素找尋最後擺放的位置，也就是它回傳的值。它暫時地把基準元素移到子序列的結尾，而不會被前述方式影響到。由於演算法只使用交換，因此最後的數列與原先的數列擁有一樣的元素。要注意的是，一個元素在到達它的最後位置前，可能會被交換很多次。
一旦我們有了這個分區演算法，要寫快速排列本身就很容易：
procere quicksort(a, left, right)
if right>left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)
這個版本經常會被使用在命令式語言中，像是C語言。
快速排序
快速排序是二叉查找樹（二叉搜索樹）的一個空間最優化版本。不是循序地把數據項插入到一個明確的樹中，而是由快速排序組織這些數據項到一個由遞歸調用所隱含的樹中。這兩個演算法完全地產生相同的比較次數，但是順序不同。對於排序演算法的穩定性指標，原地分區版本的快速排序演算法是不穩定的。其他變種是可以通過犧牲性能和空間來維護穩定性的。
『叄』 java十大演算法
演算法一：快速排序演算法
快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法（Divide and conquer）策略來把一個串列（list）分為兩個子串列（sub-lists）。
演算法步驟：
1 從數列中挑出一個元素，稱為 "基準"（pivot），
2 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
3 遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。
演算法二：堆排序演算法
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。
堆排序的平均時間復雜度為Ο(nlogn) 。
演算法步驟：
創建一個堆H[0..n-1]
把堆首（最大值）和堆尾互換
3. 把堆的尺寸縮小1，並調用shift_down(0),目的是把新的數組頂端數據調整到相應位置
4. 重復步驟2，直到堆的尺寸為1
演算法三：歸並排序
歸並排序（Merge sort，台灣譯作：合並排序）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
演算法步驟：
1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列
2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置
4. 重復步驟3直到某一指針達到序列尾
5. 將另一序列剩下的所有元素
『肆』 排序演算法概述
十大排序演算法：冒泡排序，選擇排序，插入排序，歸並排序，堆排序，快速排序、希爾排序、計數排序，基數排序，桶排序
穩定 ：如果a原本在b前面，而a=b，排序之後a仍然在b的前面；
不穩定 ：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；
排序演算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，前一個鍵排序的結果可以為後一個鍵排序所用。
演算法的復雜度往往取決於數據的規模大小和數據本身分布性質。
時間復雜度 ： 一個演算法執行所耗費的時間。
空間復雜度 ：對一個演算法在運行過程中臨時佔用存儲空間大小的量度。
常見復雜度由小到大 ：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
在各種不同演算法中，若演算法中語句執行次數(佔用空間)為一個常數，則復雜度為O(1)；
當一個演算法的復雜度與以2為底的n的對數成正比時，可表示為O(log n)；
當一個演算法的復雜度與n成線性比例關系時，可表示為O (n)，依次類推。
冒泡、選擇、插入排序需要兩個for循環，每次只關注一個元素，平均時間復雜度為
（一遍找元素O(n)，一遍找位置O(n)）
快速、歸並、堆基於分治思想，log以2為底，平均時間復雜度往往和O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）相關
而希爾排序依賴於所取增量序列的性質，但是到目前為止還沒有一個最好的增量序列 。例如希爾增量序列時間復雜度為O(n²)，而Hibbard增量序列的希爾排序的時間復雜度為 ， 有人在大量的實驗後得出結論;當n在某個特定的范圍後希爾排序的最小時間復雜度大約為n^1.3。
從平均時間來看，快速排序是效率最高的：
快速排序中平均時間復雜度O(nlog n)，這個公式中隱含的常數因子很小，比歸並排序的O(nlog n)中的要小很多，所以大多數情況下，快速排序總是優於合並排序的。
而堆排序的平均時間復雜度也是O(nlog n)，但是堆排序存在著重建堆的過程，它把根節點移除後，把最後的葉子結點拿上來後需要重建堆，但是，拿上的值是要比它的兩個葉子結點要差很多的，一般要比較很多次，才能回到合適的位置。堆排序就會有很多的時間耗在堆調整上。
雖然快速排序的最壞情況為排序規模（n）的平方關系，但是這種最壞情況取決於每次選擇的基準， 對於這種情況，已經提出了很多優化的方法，比如三取樣劃分和Dual-Pivot快排。
同時，當排序規模較小時，劃分的平衡性容易被打破，而且頻繁的方法調用超過了O(nlog n)為
省出的時間，所以一般排序規模較小時，會改用插入排序或者其他排序演算法。
一種簡單的排序演算法。它反復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。這個工作重復地進行直到沒有元素再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為元素會經由交換慢慢「浮」到數列的頂端。
1.從數組頭開始，比較相鄰的元素。如果第一個比第二個大(小)，就交換它們兩個；
2.對每一對相鄰元素作同樣的工作，從開始第一對到尾部的最後一對，這樣在最後的元素應該會是最大(小)的數；
3.重復步驟1~2，重復次數等於數組的長度，直到排序完成。
首先，找到數組中最大（小）的那個元素；
其次，將它和數組的第一個元素交換位置（如果第一個元素就是最大（小）元素那麼它就和自己交換）；
再次，在剩下的元素中找到最大（小）的元素，將它與數組的第二個元素交換位置。如此往復，直到將整個數組排序。
這種方法叫做選擇排序，因為它在不斷地選擇剩餘元素之中的最大（小）者。
對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。
為了給要插入的元素騰出空間，我們需要將插入位置之後的已排序元素在都向後移動一位。
插入排序所需的時間取決於輸入中元素的初始順序。例如，對一個很大且其中的元素已經有序（或接近有序）的數組進行排序將會比對隨機順序的數組或是逆序數組進行排序要快得多。
總的來說，插入排序對於部分有序的數組十分高效，也很適合小規模數組。
一種基於插入排序的快速的排序演算法。簡單插入排序對於大規模亂序數組很慢，因為元素只能一點一點地從數組的一端移動到另一端。例如，如果主鍵最小的元素正好在數組的盡頭，要將它挪到正確的位置就需要N-1 次移動。
希爾排序為了加快速度簡單地改進了插入排序，也稱為縮小增量排序，同時該演算法是突破O(n^2）的第一批演算法之一。
希爾排序是把待排序數組按一定數量的分組，對每組使用直接插入排序演算法排序；然後縮小數量繼續分組排序，隨著數量逐漸減少，每組包含的元素越來越多，當數量減至 1 時，整個數組恰被分成一組，排序便完成了。這個不斷縮小的數量，就構成了一個增量序列。
在先前較大的增量下每個子序列的規模都不大,用直接插入排序效率都較高，盡管在隨後的增量遞減分組中子序列越來越大,由於整個序列的有序性也越來越明顯,則排序效率依然較高。
從理論上說，只要一個數組是遞減的，並且最後一個值是1，都可以作為增量序列使用。有沒有一個步長序列,使得排序過程中所需的比較和移動次數相對較少,並且無論待排序列記錄數有多少,演算法的時間復雜度都能漸近最佳呢？但是目前從數學上來說，無法證明某個序列是「最好的」。
常用的增量序列
希爾增量序列 ：{N/2, (N / 2)/2, ..., 1}，其中N為原始數組的長度，這是最常用的序列，但卻不是最好的
Hibbard序列：{2^k-1, ..., 3,1}
Sedgewick序列：{... , 109 , 41 , 19 , 5，1} 表達式為
歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法的一個非常典型的應用。
對於給定的一組數據，利用遞歸與分治技術將數據序列劃分成為越來越小的半子表，在對半子表排序後，再用遞歸方法將排好序的半子表合並成為越來越大的有序序列。
為了提升性能，有時我們在半子表的個數小於某個數（比如15）的情況下，對半子表的排序採用其他排序演算法，比如插入排序。
若將兩個有序表合並成一個有序表，稱為2-路歸並，與之對應的還有多路歸並。
快速排序（Quicksort）是對冒泡排序的一種改進，也是採用分治法的一個典型的應用。
首先任意選取一個數據（比如數組的第一個數）作為關鍵數據，我們稱為基準數(Pivot)，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序，也稱為分區（partition）操作。
通過一趟快速排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數組變成有序序列。
為了提升性能，有時我們在分割後獨立的兩部分的個數小於某個數（比如15）的情況下，會採用其他排序演算法，比如插入排序。
基準的選取：最優的情況是基準值剛好取在無序區數值的中位數，這樣能夠最大效率地讓兩邊排序，同時最大地減少遞歸劃分的次數，但是一般很難做到最優。基準的選取一般有三種方式，選取數組的第一個元素，選取數組的最後一個元素，以及選取第一個、最後一個以及中間的元素的中位數（如4 5 6 7, 第一個4, 最後一個7, 中間的為5, 這三個數的中位數為5, 所以選擇5作為基準）。
Dual-Pivot快排：雙基準快速排序演算法，其實就是用兩個基準數, 把整個數組分成三份來進行快速排序，在這種新的演算法下面，比經典快排從實驗來看節省了10%的時間。
許多應用程序都需要處理有序的元素，但不一定要求他們全部有序，或者不一定要一次就將他們排序，很多時候，我們每次只需要操作數據中的最大元素（最小元素），那麼有一種基於二叉堆的數據結構可以提供支持。
所謂二叉堆，是一個完全二叉樹的結構，同時滿足堆的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。在一個二叉堆中，根節點總是最大（或者最小）節點。
堆排序演算法就是抓住了這一特點，每次都取堆頂的元素，然後將剩餘的元素重新調整為最大（最小）堆，依次類推，最終得到排序的序列。
推論1：對於位置為K的結點 左子結點=2 k+1 右子結點=2 (k+1)
驗證：C:2 2 2+1=5 2 (2+1)=6
推論2：最後一個非葉節點的位置為 (N/2)-1，N為數組長度。
驗證：數組長度為6，(6/2)-1=2
計數排序對一定范圍內的整數排序時候的速度非常快，一般快於其他排序演算法。但計數排序局限性比較大，只限於對整數進行排序，而且待排序元素值分布較連續、跨度小的情況。
計數排序是一個排序時不比較元素大小的排序演算法。
如果一個數組里所有元素都是整數，而且都在0-K以內。對於數組里每個元素來說，如果能知道數組里有多少項小於或等於該元素，就能准確地給出該元素在排序後的數組的位置。
桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，利用某種函數的映射關系將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序）。
桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當於快排中劃分，已經把大量數據分割成了基本有序的數據塊(桶)。然後只需要對桶中的少量數據做排序即可。
常見的數據元素一般是由若干位組成的，比如字元串由若干字元組成，整數由若干位0~9數字組成。基數排序按照從右往左的順序，依次將每一位都當做一次關鍵字，然後按照該關鍵字對數組排序，同時每一輪排序都基於上輪排序後的結果；當我們將所有的位排序後，整個數組就達到有序狀態。基數排序不是基於比較的演算法。
基數是什麼意思？對於十進制整數，每一位都只可能是0~9中的某一個，總共10種可能。那10就是它的基，同理二進制數字的基為2；對於字元串，如果它使用的是8位的擴展ASCII字元集，那麼它的基就是256。
基數排序 vs 計數排序 vs 桶排序
基數排序有兩種方法：
MSD 從高位開始進行排序
LSD 從低位開始進行排序
這三種排序演算法都利用了桶的概念，但對桶的使用方法上有明顯差異：
基數排序：根據鍵值的每位數字來分配桶
計數排序：每個桶只存儲單一鍵值
桶排序：每個桶存儲一定范圍的數值
有時，待排序的文件很大，計算機內存不能容納整個文件，這時候對文件就不能使用內部排序了（我們一般的排序都是在內存中做的，所以稱之為內部排序，而外部排序是指待排序的內容不能在內存中一下子完成，它需要做內外存的內容交換），外部排序常採用的排序方法也是歸並排序，這種歸並方法由兩個不同的階段組成：
採用適當的內部排序方法對輸入文件的每個片段進行排序，將排好序的片段（成為歸並段）寫到外部存儲器中（通常由一個可用的磁碟作為臨時緩沖區），這樣臨時緩沖區中的每個歸並段的內容是有序的。
利用歸並演算法，歸並第一階段生成的歸並段，直到只剩下一個歸並段為止。
例如要對外存中4500個記錄進行歸並，而內存大小隻能容納750個記錄，在第一階段，我們可以每次讀取750個記錄進行排序，這樣可以分六次讀取，進行排序，可以得到六個有序的歸並段
每個歸並段的大小是750個記錄，並將這些歸並段全部寫到臨時緩沖區（由一個可用的磁碟充當）內了，這是第一步的排序結果。
完成第二步該怎麼做呢？這時候歸並演算法就有用處了。