计数排序（Counting Sort）

之前学习的冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序

平均时间复杂度目前最低是O(nlogn)

计数排序、桶排序、基数排序，都不是基于比较的排序它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比O(nlogn)更低

计数排序于1954年由Harold H.Seward提出，适合对一定范围内的整数进行排序

计数排序的核心思想

统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引

计数排序 - 最简单的实现

// 找出最大值int max = array[0];for (int i = 1; i < array.length; i++) {	if (array[i] > max) {		max = array[i];	}} // O(n)// 开辟内存空间，存储每个整数出现的次数int[] counts = new int[1 + max];// 统计每个整数出现的次数for (int i = 0; i < array.length; i++) {	counts[array[i]]++;} // O(n)// 根据整数的出现次数，对整数进行排序int index = 0;for (int i = 0; i < counts.length; i++) {	while (counts[i]-- > 0) {		array[index++] = i;	}} // O(n)

这个版本的实现存在以下问题

无法对负整数进行排序

极其浪费内存空间

是个不稳定的排序

计数排序 - 改进思路

逆序遍历可以保持稳定性

依次类推

改进版代码实现

// 找出最值int max = array[0];int min = array[0];for (int i = 1; i < array.length; i++) {	if (array[i] > max) {		max = array[i];	}	if (array[i] < min) {		min = array[i];	}}// 开辟内存空间，存储次数int[] counts = new int[max - min + 1];// 统计每个整数出现的次数for (int i = 0; i < array.length; i++) {	counts[array[i] - min]++;}// 累加次数for (int i = 1; i < counts.length; i++) {	counts[i] += counts[i - 1];}// 从后往前遍历元素，将它放到有序数组中的合适位置int[] newArray = new int[array.length];for (int i = array.length - 1; i >= 0; i--) {	newArray[--counts[array[i] - min]] = array[i];}// 将有序数组赋值到arrayfor (int i = 0; i < newArray.length; i++) {	array[i] = newArray[i];}

最好、最坏、平均时间复杂度：O(n+k)

空间复杂度：O(n+k)

k是整数的取值范围

属于稳定排序

计数排序 - 对自定义对象排序

Person[] persons = new Person[] {		new Person(20, "A"),		new Person(-13, "B"),		new Person(17, "C"),		new Person(12, "D"),		new Person(-13, "E"),		new Person(20, "F")};// 找出最值int max = persons[0].age;int min = persons[0].age;for (int i = 1; i < persons.length; i++) {	if (persons[i].age > max) {		max = persons[i].age;	}	if (persons[i].age < min) {		min = persons[i].age;	}}// 开辟内存空间，存储次数int[] counts = new int[max - min + 1];// 统计每个整数出现的次数for (int i = 0; i < persons.length; i++) {	counts[persons[i].age - min]++;}// 累加次数for (int i = 1; i < counts.length; i++) {	counts[i] += counts[i - 1];}// 从后往前遍历元素，将它放到有序数组中的合适位置Person[] newArray = new Person[persons.length];for (int i = persons.length - 1; i >= 0; i--) {	newArray[--counts[persons[i].age - min]] = persons[i];}// 将有序数组赋值到arrayfor (int i = 0; i < newArray.length; i++) {	persons[i] = newArray[i];}for (int i = 0; i < persons.length; i++) {	System.out.println(persons[i]);}

基数排序（Radix Sort）

基数排序非常适合用于整数排序（尤其是非负整数），这里只介绍对非负整数进行基数排序。

执行流程：依次对个位数、十位数、百位数、千位数、万位数…进行排序（从低位到高位）

个位数、十位数、百位数的取值范围都是固定的0~9，可以使用计数排序对它们进行排序。

基数排序代码实现

public class RadixSort extends Sort
    
      {	@Override	protected void sort() {		// 找出最大值		int max = array[0];		for (int i = 1; i < array.length; i++) {			if (array[i] > max) {				max = array[i];			}		}				// 个位数: array[i] / 1 % 10 = 3		// 十位数：array[i] / 10 % 10 = 9		// 百位数：array[i] / 100 % 10 = 5		// 千位数：array[i] / 1000 % 10 = ...		for (int divider = 1; divider <= max; divider *= 10) {			countingSort(divider);		}	}		protected void countingSort(int divider) {		// 开辟内存空间，存储次数		int[] counts = new int[10];		// 统计每个整数出现的次数		for (int i = 0; i < array.length; i++) {			counts[array[i] / divider % 10]++;		}		// 累加次数		for (int i = 1; i < counts.length; i++) {			counts[i] += counts[i - 1];		}				// 从后往前遍历元素，将它放到有序数组中的合适位置		int[] newArray = new int[array.length];		for (int i = array.length - 1; i >= 0; i--) {			newArray[--counts[array[i] / divider % 10]] = array[i];		}				// 将有序数组赋值到array		for (int i = 0; i < newArray.length; i++) {			array[i] = newArray[i];		}	}}

最好、最坏、平均时间复杂度：O(d ∗ (n + k)) ，d 是最大值的位数，k 是进制

空间复杂度：O(n + k)，k 是进制

基数排序属于稳定排序

基数排序-另一种思路

复杂度与稳定性

空间复杂度是 O(kn + k) ，时间复杂度是 O(dn)

d 是最大值的位数，k 是进制

桶排序（Bucket Sort）

执行流程：

① 创建一定数量的桶（比如用数组、链表作为桶）

② 按照一定的规则（不同类型的数据，规则不同），将序列中的元素均匀分配到对应的桶

③ 分别对每个桶进行单独排序

④ 将所有非空桶的元素合并成有序序列

元素在桶中的索引：元素值 * 元素数量

实现

复杂度与稳定性

空间复杂度：O(n + m)，m 是桶的数量

时间复杂度：

桶排序属于稳定排序