日常开发中，会遇到一些特定的排序场景：“待排序的值”范围很明细，比如：基金的星级排名，客服的好评星级排名，一般星级排名也就从1星到5星。这种情况下，有一个经典的“下标计数排序法”，可以用O(n)的时间复杂度完成排序：
代码语言：javascript复制 static void sort0() {
int[] arr = new int[]{5, 4, 4, 1, 2, 3};
int[] indexCountArr = new int[6];
//下标计数排序
for (int i = 0; i < arr.length; i ) {
indexCountArr[arr[i]] = 1;
}
//排完后，indexCountArr的值:[0, 1, 1, 1, 2, 1]
System.out.println("indexCountArr=>" Arrays.toString(indexCountArr));
//排序结果输出
for (int i = 0; i < indexCountArr.length; i ) {
for (int j = 0; j < indexCountArr[i]; j ) {
System.out.print(i "t");
}
}
System.out.println("n");
}输出：
indexCountArr=>[0, 1, 1, 1, 2, 1] 1 2 3 4 4 5
但这是一个不稳定的排序算法，而且输出结果只有值，如果是一个复杂的对象，比如下面这样：
代码语言：javascript复制 static class EmpScore {
public String empNo;
public int score;
public EmpScore(String empNo, int score) {
this.empNo = empNo;
this.score = score;
}
@Override
public String toString() {
return empNo ":" score;
}
}
public static void main(String[] args) {
EmpScore[] arr = new EmpScore[]{
new EmpScore("S01", 5),
new EmpScore("S02", 4),
new EmpScore("S03", 4),
new EmpScore("S04", 1),
new EmpScore("S05", 2),
new EmpScore("S06", 3)
};
//todo 待排序
}按score评分星级排序后，如果希望S02仍然在S03前面，可以参考下面这样：(大致思路是在每个"桶"的位置，引入了一个顺序结构的List)
代码语言：javascript复制 static void sort1(EmpScore[] arr) {
//排序过程(下标计数排序)
Map<Integer, List<EmpScore>> scoreMap = new HashMap<>(arr.length);
int[] indexCountArr = new int[6];
for (int i = 0; i < arr.length; i ) {
indexCountArr[arr[i].score] = 1;
List<EmpScore> list;
if (scoreMap.containsKey(arr[i].score)) {
list = scoreMap.get(arr[i].score);
} else {
list = new ArrayList<>();
}
list.add(arr[i]);
scoreMap.put(arr[i].score, list);
}
//排完后，indexCountArr的值:[0, 1, 1, 1, 2, 1]
System.out.println("indexCountArr=>" Arrays.toString(indexCountArr));
//输出结果
List<EmpScore> sortedList = new ArrayList<>(arr.length);
for (int i = 1; i < indexCountArr.length; i ) {
sortedList.addAll(scoreMap.get(i));
}
System.out.println(sortedList.toString() "n");
}输出：
indexCountArr=>[0, 1, 1, 1, 2, 1] [S04:1, S05:2, S06:3, S02:4, S03:4, S01:5]
如果不想额外引入List，还可以这样做：
代码语言：javascript复制static void sort2(EmpScore[] arr) {
int[] indexCountArr = new int[6];
for (int i = 0; i < arr.length; i ) {
indexCountArr[arr[i].score] = 1;
}
//关键点1
for (int i = 1; i < arr.length; i ) {
indexCountArr[i] = indexCountArr[i - 1];
}
//排完后，indexCountArr的值:[0, 1, 2, 3, 5, 6]
System.out.println("indexCountArr=>" Arrays.toString(indexCountArr));
EmpScore[] sorted = new EmpScore[arr.length];
//关键点2
for (int i = arr.length - 1; i >= 0; i--) {
sorted[indexCountArr[arr[i].score] - 1] = arr[i];
indexCountArr[arr[i].score] -= 1;
}
System.out.println(Arrays.toString(sorted));
}结果不变，具体过程，大家可以拿张纸，自己画一画，还是蛮有技巧的，算是一种比较tricky的解法吧。
