Data Structure
  • 資料結構自學筆記
  • 1 - Stack & Queue
    • 1.1 - Stack
    • 1.2 - Queue
    • 1.3 - Stack and Queue
  • 2 - Tree & Binary Tree
    • 2.1 - Tree
    • 2.2 - Binary Tree
    • 2.3 - Binary Tree Traversal
    • 2.4 - Binary Search Tree
    • 2.5 - Heap
    • 2.6 - Thread Binary Tree
    • 2.7 - Tree and Binary Tree Conversion
    • 2.8 Advanced Trees
      • 2.8.1 - Min-Max Heap
      • 2.8.2 - Deap
      • 2.8.3 - Symmetric Min-Max Heap
      • 2.8.4 - Extended Binary Tree
      • 2.8.5 - AVL Tree
      • 2.8.6 - M-Way Search Tree
      • 2.8.7 - B Tree
      • 2.8.8 - Red-Black Tree
      • 2.8.9 - Optimal Binary Search Tree
      • 2.8.10 - Splay Tree
      • 2.8.11 - Leftest Heap
      • 2.8.12 - Binomial Heap
  • 3 - Search & Sort
    • 3.1 - Searching
    • 3.2 - Elementary Sorting
      • 3.2.1 - Insertion Sort
      • 3.2.2 - Selection Sort
      • 3.2.3 - Bubble Sort
      • 3.2.4 - Shell Sort
    • 3.3 - Sophisticated Sorting
      • 3.3.1 - Quick Sort
      • 3.3.2 - Merge Sort
      • 3.3.3 - Heap Sort
      • 3.3.4 - Radix Sort
      • 3.3.5 - Bucket Sort
      • 3.3.6 - Counting Sort
    • 3.4 - Summary
  • 4 - Graph
    • 4.1 - Intro
    • 4.2 - Graph Traversal
    • 4.3 - Spanning Tree
      • 4.3.1 - Kruskal's algorithm
      • 4.3.2 - Prim's algorithm
      • 4.3.3 - Sollin's algorithm
    • 4.4 - Shortest Path Length
      • 4.4.1 - Dijkstra's algorithm
      • 4.4.2 - Bellman-Ford algorithm
      • 4.4.3 - Floyd-Warshall algorithm
    • 4.5 - AOV Network
    • 4.6 - AOE Network
    • 4.7 - Others
Powered by GitBook
On this page
  • 1. 演算法
  • 2. 性質
  1. 3 - Search & Sort
  2. 3.3 - Sophisticated Sorting

3.3.4 - Radix Sort

(LSD) Radix Sort

Previous3.3.3 - Heap SortNext3.3.5 - Bucket Sort

Last updated 6 years ago

1. 演算法

準備r-1個buckets(r進制)，假設資料中最大值的為數個數為d，則需要執行d回合。每回合執行下面兩個步驟

  1. Distribution: 依照資料的位數值分派到對應的buckets

  2. Merge: 依照buckets的編號合併資料

從個位數開始到d，共執行d回合。

e.g. {179,208,306,93,859,984,55,9,271,33}10\{179, 208, 306, 93, 859, 984, 55, 9, 271, 33\} _{10}{179,208,306,93,859,984,55,9,271,33}10​

  1. Distribution: 個位數

  1. Merge: {271, 93, 33, 984, 55, 306, 208, 179, 859, 9}

2. Distribution: 十位數

2. Merge: {306, 208, 9, 33, 55, 859, 271, 179, 984, 93}

3. Distribution: 百位數

3. Merge: {9, 33, 55, 93, 179, 208, 271, 306, 859, 984}

2. 性質

  • 共需r個buckers，每個buckets的大小為n。

Radix sorting is a unstable sorting method.

Time Complexity: O(n)O(n)O(n)

n筆資料為r進制，其最大值有d位數，總共花 O(d∗(n+r))O(d*(n+r))O(d∗(n+r))，d、r可視為常數。

Space Complexity: O(r∗n)O(r*n)O(r∗n)