算法入门篇四 桶排序
程序员文章站
2022-06-07 14:42:55
...
桶排序
计数排序(基于统计)
- 要求数据是有限的,和数据状况有关,比如对于200个人统计他们的年龄分布,这个时候需要申请200个桶,因此对于输入数据的规模有限制,如果输入规模是不定的,空间申请就会很麻烦。
基数排序
思想
- 要求排序的数字都是十进制的数字,找到最高位的数字,对于其中不满足位数的数字前面补0,例如【100,23,34】就需要改写成【100,023,034】的形式。
- 准备和数字相同数目的桶(类比于先进先出的队列),所有数字按照个位数字进桶,然后按照从左往右的次序依次往出倒数字,如果一个桶内有多个数字按照次序(队列)倒数,再按照十位数字进桶,原理和先前类似,倒出;再按照百位数字进桶,出桶。最后的次序是从小到大的。
落地
- 初始数组为【23,13,3,24,23,14】,申请两个栈,一个为count,一个是help。count按照次序分别是【0,1,2,3,4,5,6,7,8,9】这个用于统计对应的数字的个数,比如上面这个例子的话,个位是3的个数有4个,个位是4的个数有3个。而help指定的是数组中元素的个数。此时一个6个元素,所以将help的大小设置为6。
- 统计完对应的数字数字之后,得到的count为【0,0,0,4,2,0,0,0,0,0】,对其进行加工,对应元素的位置等于自身的值+前面的元素值。如果是0号位置就是本身,1号就是0+0,2号是0+0;3号是4+0;4号是4+0;5号是6+0;依次类推剩余元素的值都是6。经过加工后的count数组含义就是小于等于相应位置上元素的个数。比如小于等于3的有三个元素;小于等于5,6,7,8,9的有6个元素。
操作过程
- 从右往左遍历,第一个元素是14,个位数小于等于6的有6个,所以将14填写在help的5位置上,并且将count数组中的4对应的6减1,变成5。
- 下一个元素是23,个位元素对应的是3,查询count数组,小于等于3的元素有四个,因此将23填写在help数组的3号位置,count中3号位置的4减1;
- 下一个元素是24, 个位元素对应的是4,查询count数组,小于等于4的元素有5个,因此将24填写在help数组的4号位置,count中4号位置的5减1;
- 下一个元素是3, 个位元素对应的是3,查询count数组,小于等于3的元素有3个,因此将3填写在help数组的2号位置,count中3号位置的3减1;
- 下一个元素是13, 个位元素对应的是3,查询count数组,小于等于3的元素有2个,因此将3填写在help数组的1号位置,count中3号位置的2减1;
- 下一个元素是23, 个位元素对应的是3,查询count数组,小于等于3的元素有1个,因此将3填写在help数组的0号位置,count中3号位置的1减1;
完整代码
package class03;
import java.util.Arrays;
public class Code02_RadixSort {
// only for no-negative value
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
// arr[begin..end]排序
public static void radixSort(int[] arr, int L, int R, int digit) {
final int radix = 10;
int i = 0, j = 0;
// 有多少个数准备多少个辅助空间
int[] bucket = new int[R - L + 1];
for (int d = 1; d <= digit; d++) { // 有多少位就进出几次
// 10个空间
// count[0] 当前位(d位)是0的数字有多少个
// count[1] 当前位(d位)是(0和1)的数字有多少个
// count[2] 当前位(d位)是(0、1和2)的数字有多少个
// count[i] 当前位(d位)是(0~i)的数字有多少个
int[] count = new int[radix]; // count[0..9]
for (i = L; i <= R; i++) {
j = getDigit(arr[i], d);
count[j]++;
}
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
for (i = R; i >= L; i--) {
j = getDigit(arr[i], d);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
for (i = L, j = 0; i <= R; i++, j++) {
arr[i] = bucket[j];
}
}
}
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
// for test
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100000;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
radixSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
radixSort(arr);
printArray(arr);
}
}
稳定性
- 相同元素排序保证先后顺序
分析:
- 桶排序思想下的排序都是不基于比较的排序
- 时间复杂度为O(N),额外空间负载度O(M)
- 应用范围有限,需要样本的数据状况满足桶的划分
汇总
- 快速排序不是基于比较的排序
对于排序的改进优化
- 充分利用O(N*logN)和O(N^2)的排序的各自优势
数据规模很大的时候使用快速排序,当数据规模减少,数据项在60以内的时候,该换成插入排序,同时使用快速和插入两种方法,能进一步提高效率,减少时间复杂度。
- 稳定性考虑
如果输入的数据是基础类型,使用快速排序;如果输入的类型是自定义的类型,使用插入、归并这些可以保证稳定性的排序方法
问题
- 将一个数组中,所有的奇数移到数组的左边,所有的偶数移到数组的右边。保持相对次序不变的同时,要是时间复杂度为O(N),空间复杂度为O(1)。这个没法做????????????????
上一篇: BST树基本操作
下一篇: 二分图最大权值完美匹配 hdu2255