分布排序

在基於關鍵字比較的一些排序算法之外，當預先知道有關待排序關鍵字的一些知識（如其分布範圍）時，就能構造出非基於比較的排序算法，而且能在最壞情況下達到線性時間。 如果把大量的索引卡排列成一個字典序，或許首先將其分成26堆（第一堆以字母a開頭，第二堆以字母b開頭等等），然後再排序各個堆。這種想法引出基於關鍵字的數字性質的分“桶“排序方法，即，分布排序。 事實上，Hoare排序可認為是兩個桶的分布排序。

定義

在基於關鍵字比較的一些排序算法之外，當預先知道有關待排序關鍵字的一些知識（如其分布範圍）時，就能構造出非基於比較的排序算法，而且能在最壞情況下達到線性時間。

如果把大量的索引卡排列成一個字典序，或許首先將其分成26堆（第一堆以字母a開頭，第二堆以字母b開頭等等），然後再排序各個堆。這種想法引出基於關鍵字的數字性質的分“桶“排序方法，即，分布排序。

分布排序即在對所要排序的數據有一定了解的基礎上，利用數據分布的一些特性進行排序，使降低排序算法的時空複雜性。

性質

分布排序可以使基於關鍵字比較的排序算法的下界Ω（n㏒2 N)提高到最壞情況下線性階。套用Hoare排序是分散式排序的一種。即快速排序（Quicksort），是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。