# 决策树模型

$$n! \le l \le 2^h$$

\begin{aligned} h &\ge \lg(n!) \\ &= \Omega(n\lg n) \end{aligned}

# 计数排序

#!python
"""
The implement of the Counting Sort

The time consume of Counting Sort is O(n), and this algorithm is stable.

The drawbacks of the this algorithm is that it can only sort the numbers from 0 to k. If there is a negative number in the A, this algorithm can not work.

If the given data is very sparse, it will waster a lot space.
"""

def CountingSort(A):
k = max(A)

C = [0] * (k+1)
B = [None] * len(A)

for item in A:
C[item] += 1
# now C[i] contains the number of elements equal to i.

for i in range(1,len(C)):
C[i] = C[i-1] + C[i]
# now C[i] contains the number of elements less than or equal to i.

for i in range(len(A)-1,-1,-1): # why from len(A) to 0 not from 0 to len(A) ? Becuse it must be stable!
# only from len(A) to 0 can guarntee stable.
B[C[A[i]]-1] = A[i]     # not the B[C[A[i]]] = A[i], because A and C starts with 0, not 1.
C[A[i]] -= 1

return B


# 基数排序

#!python
"""
The implement of Radix Sort.

Radix Sort is using the property of the stable sorting algorithm.
"""

def counting_sort(A,index):
k = max([item[index] for item in A])
n = len(A)

B = [0] * (k+1)
C = [None] * n

for item in A:
B[item[index]] += 1

for i in range(1,len(B)):
B[i] += B[i-1]

for i in range(len(A)-1,-1,-1):
C[ B[ A[i][index] ] - 1 ] = A[i]
B[A[i][index]] -= 1

return C

def radix_sort(A):
d = len(A[0])
B = A[:]
for i in range(d-1,-1,-1):
B = counting_sort(B,i)
return B

if __name__ == "__main__":
A = [
[3,2,9],
[4,5,7],
[6,5,7],
[8,3,9],
[4,3,6],
[7,2,0],
[3,5,5],
]
print(A)
B = radix_sort(A)
print(B)


Share on: TwitterFacebookEmail

Flyaway is the owner of this blog.

So what do you think? Did I miss something? Is any part unclear? Leave your comments below

comments powered by Disqus

~2 min read

clrs