分布排序

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

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

事實上,Hoare排序可認為是兩個桶的分布排序。

基本介紹

  • 中文名:分布排序
  • 外文名:distribute sort
  • 套用:計算機程式語言
定義,性質,

定義

在基於關鍵字比較的一些排序算法之外,當預先知道有關待排序關鍵字的一些知識(如其分布範圍)時,就能構造出非基於比較的排序算法,而且能在最壞情況下達到線性時間。
如果把大量的索引卡排列成一個字典序,或許首先將其分成26堆(第一堆以字母a開頭,第二堆以字母b開頭等等),然後再排序各個堆。這種想法引出基於關鍵字的數字性質的分“桶“排序方法,即,分布排序。
分布排序即在對所要排序的數據有一定了解的基礎上,利用數據分布的一些特性進行排序,使降低排序算法的時空複雜性。

性質

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

相關詞條

熱門詞條

聯絡我們