计数排序

前言：
这是一种不需要比较的排序方式，但极其浪费空间。（写嵌入式的小伙伴会气死吧）
原理：
统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引
image.png
示例：

  1. //这是最简单的实现方式
  3. // 找出最大值
  4.         int max = array[0];
  5.         for (int i = 1; i < array.length; i++) {
  6.             if (array[i] > max) {
  7.                 max = array[i];
  8.             }
  9.         } // O(n)
  11.         // 开辟内存空间，存储每个整数出现的次数
  12.         int[] counts = new int[1 + max];
  13.         // 统计每个整数出现的次数
  14.         for (int i = 0; i < array.length; i++) {
  15.             counts[array[i]]++;
  16.         } // O(n)
  18.         // 根据整数的出现次数，对整数进行排序
  19.         int index = 0;
  20.         for (int i = 0; i < counts.length; i++) {
  21.             while (counts[i]-- > 0) {
  22.                 array[index++] = i;
  23.             }
  24.         } // O(n)

算法分析：
这个版本的实现存在以下问题：无法对负整数进行排序；极其浪费内存空间；是个不稳定的排序 。
（用这个的人就很神奇）

计数排序 – 改进思路

原本我们是把数组的索引作为记录原序列中的数值，但是数组中没有负数，所以我们就没有办法比较序列中的负数。
现在我们将数组中第一个位置就是序列中最小的数，利用这个数和数组索引的差，
image.png
解决的不能负数的问题，现在来解决不稳定
image.png
假设array中的最小值是 min； array中的元素 k 对应的 counts 索引是 k – min； array中的元素 k 在有序序列中的索引； counts[k – min] – p； p 代表着是倒数第几个 k；
image.png
image.png

  1. // 找出最值
  2.         int max = array[0];
  3.         int min = array[0];
  4.         for (int i = 1; i < array.length; i++) {
  5.             if (array[i] > max) {
  6.                 max = array[i];
  7.             }
  8.             if (array[i] < min) {
  9.                 min = array[i];
  10.             }
  11.         }
  13.         // 开辟内存空间，存储次数
  14.         int[] counts = new int[max - min + 1];
  15.         // 统计每个整数出现的次数
  16.         for (int i = 0; i < array.length; i++) {
  17.             counts[array[i] - min]++;
  18.         }
  19.         // 累加次数
  20.         for (int i = 1; i < counts.length; i++) {
  21.             counts[i] += counts[i - 1];
  22.         }
  24.         // 从后往前遍历元素，将它放到有序数组中的合适位置
  25.         int[] newArray = new int[array.length];
  26.         for (int i = array.length - 1; i >= 0; i--) {
  27.             newArray[--counts[array[i] - min]] = array[i];
  28.         }
  30.         // 将有序数组赋值到array
  31.         for (int i = 0; i < newArray.length; i++) {
  32.             array[i] = newArray[i];
  33.         }
  34.     }

基数排序

前言：
基数排序，所谓的基数就是他的个位，十位，百位，通过个十百千的顺序依次排列各位的数字大小，最后得到所有数字的大小。
原理：
基数排序非常适合用于整数排序（尤其是非负整数），因此只演示对非负整数进行基数排序 执行流程：依次对个位数、十位数、百位数、千位数、万位数…进行排序（从低位到高位）
image.png
对位数排序时，我们使用计数排序

示例：

  1. // 找出最大值
  2.         int max = array[0];
  3.         for (int i = 1; i < array.length; i++) {
  4.             if (array[i] > max) {
  5.                 max = array[i];
  6.             }
  7.         }
  9.         // 个位数: array[i] / 1 % 10 = 3
  10.         // 十位数：array[i] / 10 % 10 = 9
  11.         // 百位数：array[i] / 100 % 10 = 5
  12.         // 千位数：array[i] / 1000 % 10 = ...
  14.         for (int divider = 1; divider <= max; divider *= 10) {
  15.             countingSort(divider);
  16.         }
  18. protected void countingSort(int divider) {
  19.         // 开辟内存空间，存储次数
  20.         int[] counts = new int[10];
  21.         // 统计每个整数出现的次数
  22.         for (int i = 0; i < array.length; i++) {
  23.             counts[array[i] / divider % 10]++;
  24.         }
  25.         // 累加次数
  26.         for (int i = 1; i < counts.length; i++) {
  27.             counts[i] += counts[i - 1];
  28.         }
  30.         // 从后往前遍历元素，将它放到有序数组中的合适位置
  31.         int[] newArray = new int[array.length];
  32.         for (int i = array.length - 1; i >= 0; i--) {
  33.             newArray[--counts[array[i] / divider % 10]] = array[i];
  34.         }
  36.         // 将有序数组赋值到array
  37.         for (int i = 0; i < newArray.length; i++) {
  38.             array[i] = newArray[i];
  39.         }
  40.     }

基数排序 – 另一种思路

我们先按照个位数的大小竖着放起来
image.png
然后，我们依次将数穿起来，最后，就会把数列排好
示例：

// 找出最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        //用来记录的二维数组
        int buckets[][]=new int[10][array.length];
        //二维数组每列的数量
        int bucketSizes[]=new int[buckets.length];

        for (int divider = 1; divider <= max; divider *= 10){
            for (int i=0;i<array.length;i++){
                int a=array[i] / divider % 10;
                buckets[a][bucketSizes[a]++]=array[i];
            }
            int index=0;
            for (int i=0;i<buckets.length;i++){
                for (int j=0;j<bucketSizes[i];j++){
                    array[index++]=buckets[i][j];
                }
                bucketSizes[i]=0;
            }
        }