【Java -- 算法】十大排序算法之计数排序

简介

计算排序假设 n 个输入元素都是 0 到 k 区间内的一个整数，其中 k 为某个整数。

基本原理：

创建一个长度为 k+1 的数组 count[]，它的 count[i] 的值对应输入数组中 i 出现的次数。通过遍历一次输入数组并统计每个元素出现次数，最后遍历 count[] 输出。

实例

1. Java 代码

import java.util.*;
public class Main
{
public static void main(String[] args) {
int[] a = {5, 4, 6, 7, 5, 1, 0, 9, 8, 1};
System.out.println("初始值:");
printArray(a);
countSort(a);
System.out.println("\n排序后:");
printArray(a);
}

public static void countSort(int[] arr) {
int[] count = new int[10];
for (int i = 0; i < arr.length; i++) {
count[arr[i]]++; // 计数每个元素出现次数
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}

private static void printArray(int[] a) {
for (int i = 0;i < a.length;i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}

2. 输出结果