Part-G4 Bucket-Sort and Radix-Sort
0
1
2
3
4
5
6
7
8
9
B
1, c
7, d
7, g
3, b
3, a
7, e
程序设计网络课件教学设计多媒体课件 PPT文档
Bucket-Sort (§ )
Let S be a sequence of n (key, element) entries with keys in the range [0, N - 1]
Bucket-sort uses the keys as indices into an auxiliary array B of sequences (buckets)
Phase 1: Empty sequence S by moving each entry (k, o) into its bucket B[k]
Phase 2: For i = 0, …, N - 1, move the entries of bucket B[i] to the end of sequence S
Analysis:
Phase 1 takes O(n) time
Phase 2 takes O(n + N) time
Bucket-sort takes O(n + N) time
Algorithm bucketSort(S, N)
Input sequence S of (key, element) items with keys in the range [0, N - 1] Output sequence S sorted by increasing keys
B array of N empty sequences
while ()
f ()
(k, o) (f)
B[k].insertLast((k, o))
for i 0 to N - 1
while B[i].isEmpty()
f B[i].first()
(k, o) B[i].remove(f)
((k, o))
程序设计网络课件教学设计多媒体课件 PPT文档
Example
Key range [0, 9]
7, d
1, c
3, a
7, g
3, b
7, e
1, c
3, a
3, b
7, d
7, g
7, e
Phase 1
Phase 2
0
1
2
3
4
5
6
7
8
9
B
1, c
7, d
7, g
3, b
3, a
7, e
程序设计网络课件教学设计多媒体课件 PPT文档
Properties and Extensions
Key-type Property
The keys are used as indices into an array and cannot be arbitrary objects
No parator
Stable Sort Property
The relative order
b[k]insertlast((k 来自淘豆网m.daumloan.com转载请标明出处.
