桶排序之基数排序总结

桶排序之基数排序总结

算法实现

public class RadixSort {

	public static void main(String[] args) {
		int[] arr = {422, 240, 115, 532, 305, 124};
		int[] result = sort(arr);
		System.out.println(Arrays.toString(result));

	}

	private static int[] sort(int[] arr) {
		int[] result = new int[arr.length];
		int[] count = new int[10];

		for (int i = 0; i < 3; i++) {
			int division = (int) Math.pow(10, i);
			System.out.println(division);
			for (int j = 0; j < arr.length; j++) {
				int num = arr[j] / division % 10;
				System.out.println(num + " ");
				count[num]++;
			}
			System.out.println();
			System.out.println(Arrays.toString(count));
			for (int m = 0; m < count.length; m++) {
				count[m] = count[m] + count[m - 1];
			}
			System.out.println(Arrays.toString(count));

			for (int n = 0; n < arr.length; n++) {
				int num = arr[n] / division % 10;

			}




		}


		return new int[0];
	}


}

大O分析

时间

• 求最大最小值n
• 便利装桶 n
• 桶内排序 n/k * log(n/k) *k
• 输出结果 n
• 3n + k + n/k * log(n/k) k = 3n + k + nlog(n/k) 与等于 n + k
• 最坏n方 （一个桶）
• 最好为n（n个桶而且值排列均匀）

空间

• n + k
• 但实际上空间做到最好的话，就只能用链表，时间就做不到最好