觀看麻省理工學院開放式課件5時。線性排序，教授談到了直接訪問數組排序：
def direct_access_sort(A):
"Sort A assuming items have distinct non-negative keys"
u = 1 + max([x.key for x in A]) # O(n) find maximum key
D = [None] * u # O(u) direct access array
for x in A: # O(n) insert items
D[x.key] = x
i = 0
for key in range(u): # O(u) read out items in order
D[key] is not None:
A[i] = D[key]
i += 1
假設所有鍵都是唯一的non-negative整數，范圍為{0，…，u?1}，因此n≤u，這里描述的算法基本上是：
- 將每個項目插入一個直接訪問數組，大小u為Θ（n）
- 按項目在直接訪問數組中的出現順序返回Θ（u）中的項目
我想知道這怎么能被描述為“排序”，因為在我看來，這里唯一排序的是鍵而不是值。
數組
D將存儲A中項目的完整對象（鍵和值），因此當插入回A時，它是完整對象：A[i] = D[key]示例：假設我們正在按身高對一組人進行排序，每個人都有一個與他們身高相等的鍵。輸入如下所示（為了簡單起見，不包括其他屬性）：
這條線在A中找到最大高度：
在我們的例子中，是200。
這一行創建了一個新的
u大小的數組，因此即使我們在A中只有4個元素，也可以創建一個200大小的數組：這個循環將整個對象（包括鍵）插入到新數組中，位于鍵的索引處。
因此，它是一個大小為200的數組，但只有4個索引具有值（這些索引是高度150160188200）。其余的是
None。當向數組中插入元素時，我們需要一個計數器——這就是
i的作用，所以它從0開始。現在我們從0迭代到最大密鑰（200）。
由于我們只有4個位置有值，我們需要檢查我們正在測試的當前高度是否為這4個位置之一：
如果鍵在數組中，我們用具有該高度的對象覆蓋
A中的當前索引（i）。這將首先發生在i=0和key=150時（因為150將是從0-200開始的第一個匹配）
最后，
i是遞增的，所以我們不會多次在同一位置插入。因此，插入時的值如下：
考慮啟動一個調試器，看看運行時對象是什么樣子的。它實現了很多線性，但要求輸入是不同的non-negative。此外，想象一下用百萬/數十億的鍵對10個元素進行排序——arrays和迭代會變得非常大。