🍈 计数排序（Counting Sort）
简介：
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
设计思想：
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
代码实现：
c语言版
void CountingSort(int *A, int *B, int n, int k) { int *C = (int *)malloc(sizeof(int) * (k + 1)); int i; for (i = 0; i <= k; i++) { C[i] = 0; } for (i = 0; i < n; i++) { C[A[i]]++; } for (i = 1; i <= k; i++) { C[i] = C[i] + C[i - 1]; } for (i = n - 1; i >= 0; i--) { B[C[A[i]] - 1] = A[i]; C[A[i]]--; } }
Java版
/** * 计数排序 * @param array * @return * @date 2022/01/20 */ public static int[] countingSort(int[] array){ if(array.length == 0){ return array; } int bias ,min = array[0],max = array[0]; //找出最小值和最大值 for(int i = 0;i < array.length;i++){ if(array[i] < min){ min = array[i]; } if(array[i] > max){ max = array[i]; } } //偏差 bias = 0 - min; //新开辟一个数组 int[] bucket = new int[max - min +1]; //数据初始化为0 Arrays.fill(bucket, 0); for(int i = 0;i < array.length;i++){ bucket[array[i] + bias] += 1; } int index = 0; for(int i = 0;i < bucket.length;i++){ int len = bucket[i]; while(len > 0){ array[index++] = i - bias; len --; } } return array; }
🍍 桶排序（Bucket Sort）
简介：
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
设计思想：
设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。
代码实现：
c语言版
void bucketSort(int *arr, int size, int max) { int i,j; int buckets[max]; memset(buckets, 0, max * sizeof(int)); for (i = 0; i < size; i++) { buckets[arr[i]]++; } for (i = 0, j = 0; i < max; i++) { while((buckets[i]--) >0) arr[j++] = i; } }
Java版
/** * 桶排序 * * @param array * @param bucketSize 桶中可以放多少种元素 * @return * @date 2022/01/20 */ public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) { if (array == null || array.size() < 2) return array; int max = array.get(0), min = array.get(0); // 找到最大值最小值 for (int i = 0; i < array.size(); i++) { if (array.get(i) > max) max = array.get(i); if (array.get(i) < min) min = array.get(i); } int bucketCount = (max - min) / bucketSize + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount); ArrayList<Integer> resultArr = new ArrayList<>(); //构造桶 for (int i = 0; i < bucketCount; i++) { bucketArr.add(new ArrayList<Integer>()); } //往桶里塞元素 for (int i = 0; i < array.size(); i++) { bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i)); } for (int i = 0; i < bucketCount; i++) { if (bucketSize == 1) { for (int j = 0; j < bucketArr.get(i).size(); j++) resultArr.add(bucketArr.get(i).get(j)); } else { if (bucketCount == 1) bucketSize--; ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize); for (int j = 0; j < temp.size(); j++) resultArr.add(temp.get(j)); } } return resultArr; }
