【算法】不基于比较的排序(图解)

1.比较器

2.桶排序

2.1.计数排序

2.2.基数排序

3.排序算法的稳定性及其汇总

1.比较器

返回负数的时候，第一个参数排在前面

返回正数的时候，第二个参数排在前面

返回0的时候，谁在前面都无所谓

@Override
public static void compare(Student o1, Student o2) {return o1.id - o2.id;
}

2.桶排序

2.1.计数排序

时间复杂度O(N)

假设我们要以年龄为基准对员工进行排序，首先初始化一个长度200的数组，索引为0的值表示0岁的员工有多少个，索引为1的值表示1岁的员工有多少个...把索引当作年龄，值当作人数，最后将辅助数组还原为原数组

桶排序是分配式排序，它利用数据的分布特征，将数据划分到不同桶中

2.2.基数排序

首先看最大的数字有几位，假设x位，那么把其他数字都补成x位，前面补0。

然后准备10个容器（桶），容器可以是数组队列等数据结构，我们以数组为例，把数据放入桶中

首先按照个位数字存入桶中

然后将数据返回原数组

接着按照十位数字存入桶中

然后将数据返回原数组

接着按照百位数字存入桶中

最后将数据返回原数组

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;
}

//所有元素入桶出桶多少次取决于最大元素的位数digit
public static void radixSort(int[] arr, int l, int r, int dight) {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]当前位是0的数字有几个//count[1]当前位是1的数字有几个//...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);
}