18.6.基数排序

\(18.6.\)Radix Sort

1.Counting Sort

   In the previous text, we have proved that sorting using comparison has a worst case running time of \(\Theta(n\log n)\).However, what if we don't compare at all?

  Suppose we have a couple of characters, saying \(acdsjlfkm\), we can sort them in alphabet order through the following steps:

1. Creat an array with the same size of an alphabet(\(26\)).
2. For each character, put it in the \(ch-'a'\) index.
3. Scan the whole array, and the former character are always less than the latter. Insert the character into a new array in order, then we get a sorted array.

  This kind of sorting method is called counting sort. If the length of data is \(N\), and the size of alphabet is \(R\), then the runtime of counting sort is \(\Theta(N+R)\). It's liner runtime!

  However, the algorithm falls to sort hard-to-count items like String, so we need improvement.

2.LSD Radix Sort

  The LSD(Least Significant Digit) radix sort sort each digit of the item independently form rightmost digit towards left, take the below table as example:

  The runtime of LSD radix sort is \(\Theta(WN+WR)\),where N is Number of items, R is size of alphabet, and W is the maximun length of these items.

  What if the length of each item isn't same? We can treat empty spaces as less than all other characters:

3.MSD Radix Sort

  The MSD(Most Significant Digit) radix sort is similiar to LSD radix sort. However, it sorts from the left digit to the right.

  After first sorting process, we may get items as below:

  The items are not in correct order yet! To solve this, we can treat items with same left digit as a group, and compare the next left character within groups:

  The runtime of MSD radix sort is the same as LSD radix sort.