突然發(fā)現(xiàn)自己對這三種排序算法一無所知柴信。
他們是基于不比較類型的算法。
在特殊情況下，時間復(fù)雜度可以達(dá)到 O(n)
看下面三篇文章妈经，講得很好跃脊。
Radix sort:
https://en.wikipedia.org/wiki/Radix_sort
Counting sort:
http://www.geeksforgeeks.org/counting-sort/
Bucket sort:
http://www.geeksforgeeks.org/bucket-sort-2/
我自己寫了下Radix sort, 他是基于counting sort的宇挫。
My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class Solution {
public void radixSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
int max = getMax(nums);
for (int i = 1; i <= max; i = i * 10) {
countingSort(nums, nums.length, i);
}
}
private int getMax(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
}
return max;
}
private void countingSort(int[] nums, int n, int digit) {
int[] counters = new int[10];
int[] temp = new int[n];
for (int i = 0; i < n; i++) {
counters[(nums[i] / digit) % 10]++;
}
for (int i = 1; i < 10; i++) {
counters[i] += counters[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
temp[counters[(nums[i] / digit) % 10] - 1] = nums[i];
counters[(nums[i] / digit) % 10]--;
}
for (int i = 0; i < n; i++) {
nums[i] = temp[i];
}
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = new int[]{170, 45, 75, 90, 802, 24, 2, 66};
test.radixSort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + "_");
}
}
}
這里有個細(xì)節(jié)是，counting sort 只能從右往左掃描酪术。因為我們要維持穩(wěn)定的排序器瘪。即，假設(shè)兩個兩位數(shù)绘雁，在按照第三位排序的時候橡疼，他們原來的順序不能被破壞。
Anyway, Good luck, Richardo! -- 09/01/2016
