小编点评

**基于桶的排序之计数排序** **作者：Grey** **原文地址：博客园：**基于桶的排序之计数排序CSDN：基于桶的排序之计数排序说明 **基于桶的排序有两种，分别是：** * 计数排序 * 基数排序 **但这两种排序应用范围有限，需要样本的数据状况满足桶的划分计数排序这个排序适用于非负数数组，如果包含负数，需要先将负数转换成正数，处理逻辑如下： * 如果数组最小值是负数，假设最小值为 min，则把数组中所有的数加上(-min)，就转换成了非负数组，最后排序结束后，再统一减去(-min)即可。 **整个排序流程如下：** 1. 获取到整个数组的最大值，假设是 max。 2. 创建长度为 max + 1 的数组 `helper`。 3. 遍历原始数组 `arr`，将 `helper[arr[i]]++` 表示原始数组中 i 这个值出现的的次数。 4. 从 0 到 max 依次取出 `helper` 数组中的非 0 值，就是排序后的结果。 5. 最后从 `helper` 中提取所有不为 0 的值，并按顺序依次写入 `arr` 中去。

正文

基于桶的排序之计数排序

作者：Grey

原文地址：

博客园：基于桶的排序之计数排序

CSDN：基于桶的排序之计数排序

说明

基于桶的排序有两种，分别是计数排序和基数排序。

但是这两种排序应用范围有限，需要样本的数据状况满足桶的划分

计数排序

这个排序适用于非负数数组，如果包含负数，需要先将负数转换成正数，处理逻辑如下

如果数组最小值是负数，假设最小值为 min，则把数组中所有的数加上(-min)，就转换成了非负数组，最后排序结束后，再统一减去(-min)即可。

整个排序流程如下，首先获取到整个数组的最大值，假设是 max，则可以确定，数组中的所有数都不超过 max，所以，只需要开辟一个长度为 max + 1 的数组���假设为 helper，然后遍历原始数组 arr, 将

helper[arr[i]]++

helper[i] 表示原始数组中 i 这个值出现的的次数

最后从 0 到 max 依次取出 helper 数组中的非 0 值，就是排序后的结果。

例如: arr 数组是如下数据

int[] arr = {1,4,3,3,6,4,5}

arr 中的最大值是 6，得到的 helper 数组长度是 7，每个数出现的次数记录在 helper 中以后，helper 数组如下：

int[] helper = {0,1,0,2,2,1,1}

然后找 helper 中不等于 0 的值，

helper[1] = 1; // 1 这个值出现了1次
helper[3] = 2; // 3 这个值出现了2次
helper[4] = 2; // 4 这个值出现了2次
helper[5] = 1; // 5 这个值出现了1次
helper[6] = 1; // 6 这个值出现了1次

然后按顺序依次写回 arr 中去

int[] arr = {1, 3, 3, 4, 4, 5, 6}

完整代码如下

public class Code_CountSort {
  // 非负数
  public static void countSort(int[] arr) {
    if (null == arr || arr.length <= 1) {
      return;
    }
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
      max = Math.max(arr[i], max);
    }
    int[] help = new int[max + 1];
    for (int j : arr) {
      help[j]++;
    }
    int t = 0;
    for (int i = 0; i < help.length; i++) {
      while (help[i] != 0) {
        arr[t++] = i;
        help[i]--;
      }
    }
  }
}

时间复杂度为O(N)，额外空间复杂度为O(M)，其中 M 是数组的最大值。

更多

算法和数据结构笔记