桶排序思想下的排序：计数排序 & 基数排序
1)桶排序思想下的排序都是不基于比较的排序
2)时间复杂度为O(N)，额外空间负载度O(M)
3)应用范围有限，需要样本的数据状况满足桶的划分
1）一般来讲，计数排序要求，样本是整数，且范围比较窄(员工年龄)
2）一般来讲，基数排序要求，样本是10进制的正整数
一旦要求稍有升级，改写代价增加是显而易见的
计数排序
public class CountSort {
//对员工年龄进行排序
public static void sort(int[] ages){
if(ages ==null || ages.length < 2){
return;
}
//1.找出最大年龄
int maxAge = Integer.MIN_VALUE;
for (int age : ages) {
maxAge = Math.max(maxAge,age);
}
//辅助数组
int[] help = new int[maxAge + 1];
for (int i = 0; i < ages.length; i++) {
help[ages[i]]++;
}
//遍历辅助数组，把数组放到ages中
int i = 0;
for (int j = 0; j < help.length; j++) {
while (help[i]-- >0){
ages[i++] = j;
}
}
}
}
基数排序
package com.lzf2.class07;
import java.util.Arrays;
public class 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 : arr) {
max = Math.max(max,i);
}
int res = 0;
while (max != 0){
res++;
max /= 10;
}
return res;
}
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
// arr[L..R]排序 , 最大值的十进制位数digit
public static void radixSort(int[] arr, int L, int R, int digit) {
int radix = 10;//基数
int[] help = new int[R - L + 1];
for (int d = 1; d <= digit; d++) {//有多少位就进出多少次
int[] count = new int[radix];//统计该位上每个数字的个数
for (int i = L; i <= R; i++) {
int num = getDigit(arr[i],d);
count[num]++;
}
//把count改成累加和
for (int i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
//从由往左遍历原数组，调整好位置
for (int i = R; i >= L; i--) {
int num = getDigit(arr[i],d);
help[count[num] - 1] = arr[i];
count[num]--;
}
//辅助数组拷贝回原数组
for (int i = L,j = 0; i <= R; i++,j++) {
arr[i] = help[j];
}
}
}
// 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);
}
}
排序的稳定性
稳定性是指同样大小的样本再排序之后不会改变相对次序
对基础类型来说，稳定性毫无意义
对非基础类型来说，稳定性有重要意义
有些序算法可以实现成稳定的， 而有些排序算法无论如何都实现不成稳定的
排序总结1）不基于比较的排序，对样本数据有严格要求，不易改写
2）基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
3）基于比较的排序，时间复杂度的极限是O(NlogN)
4）时间复杂度O(NlogN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的。
5）为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并
常见的坑
1）归并排序的额外空间复杂度可以变成O(1)，“归并排序 内部缓存法”，但是将变得不再稳定。
2）“原地归并排序" 是垃圾贴，会让时间复杂度变成O(N^2)
3）快速排序稳定性改进，“01 stable sort”，但是会对样本数据要求更多。
在整型数组中，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的相对次序不变，所有偶数之间原始相对次序不变。时间复杂度做到O(N)，额外空间复杂度做到O(1)。
做不到
1）归并排序的额外空间复杂度可以变成O(1)，“归并排序 内部缓存法”，但是将变得不再稳定。
2）“原地归并排序" 是垃圾贴，会让时间复杂度变成O(N^2)
3）快速排序稳定性改进，“01 stable sort”，但是会对样本数据要求更多。
在整型数组中，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的相对次序不变，所有偶数之间原始相对次序不变。时间复杂度做到O(N)，额外空间复杂度做到O(1)。
做不到
