桶排序和计数排序都是一种排序效率比较高的排序算法，桶排序当桶的个数与n接近时的时间复杂度是O(n)，计数排序的时间复杂度是O(n+k)。
package com.program;
import java.util.ArrayList;
import java.util.List;
public class Sort {
private int findMin(int[] data) {
int min = data[0];
int minIndex = 0;
for (int i = 1; i < data.length; i++) {
if (data[i] < min) {
min = data[i];
minIndex = i;
}
}
return data[minIndex];
}
private int findMax(int[] data) {
int max = data[0];
int maxIndex = 0;
for (int i = 1; i < data.length; i++) {
if (data[i] > max) {
max = data[i];
maxIndex = i;
}
}
return data[maxIndex];
}
/**
* 桶排序
* 用途：一般用作外部排序，比如有10G的订单数据，但是内存只有100M大小内存，这个时候就用到桶排序，
* 步骤：1.扫描一遍整个文件，看整个订单数据的订单金额所处的范围大小
* 2.按照订单金额分成m个桶,然后将所有的订单存放到这m个桶里(这样每个桶里存放的都是同一区间的数据了)
* 3.对这m个桶进行内部排序(时间复杂度O(nlogn)
* 4.将m个桶里的数据按照顺序拿出来，over了。
* 时间复杂度：当整体数据n与桶的个数接近时，时间复杂度能达到O(n)
* 空间复杂度：未知，和数据是否均匀分布有关
*/
public void bucketSort(int[] data) {
if (data == null || data.length == 0) {
return;
}
int n = data.length;
int min = findMin(data);
//这里假设数据量不是很多的情况，桶的个数m与n相同
//我这里为了简单直接用List来表示了，实际上也可以用链表来表示桶，或者数组扩容也行。
ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(n);
for (int j = 0; j < n; j++) {
bucket.add(new ArrayList<Integer>());
}
for (int i = 0; i < data.length; i++) {
//找到这个数所在的桶的位置(这里因为桶的个数与n相同，所以每个桶只存一个数，那么计算就很简单了)
int k = (data[i] - min) % data.length;
bucket.get(k).add(data[i]);
}
//遍历所有的桶，拿出数据，over了
for (int l = 0; l < bucket.size(); l++) {
ArrayList<Integer> list = bucket.get(l);
if (list.size() > 0) {
for (int m = 0; m < list.size(); m++) {
System.out.print(list.get(m) + " ");
}
}
}
}
/**
* 计数排序
* 计数排序其实是桶排序的特定情况，就是每个桶里存放的都是一样的数据，就避免了桶内排序
* 用途：比如查找高考排名，因为分数在一个正常的范围内，并且是正整数。或者对公司内员工年龄排序，这些都是在一个正常范围内
* 思路：
* 1.找出n个数A[n]中最大的一个数k,
* 2.创建一个空的数组B[k+1],其中数组下标表示n中的值,遍历A[n],得到每个数的个数,(这个就是计数数组了)
* 3.对计数数组进行按顺序求和，就能得到<=某个数的个数了
* 4.创建一个空的数组C[n]用来存放排序后的数，
* 5.根据计数数组来将对应的数存放到C[n]中，具体怎么存放，请看代码
* 时间复杂度&空间复杂度都是O(n)+O(k),其中k是计数数组个数
*/
public void countingSort(int[] data) {
if (data == null || data.length == 0) {
return;
}
System.out.println("原始数组为：");
printArray(data);
int max = findMax(data);
//创建一个计数数组
int[] countArray = new int[max + 1];
for (int i = 0; i < data.length; i++) {
int value = data[i];
countArray[value] += 1;
}
System.out.println("计数数组为：");
printArray(countArray);
//对计数数组按顺序求和，得到小于某个数的个数
//这种时间复杂度要稍微高一点
/*for (int j = countArray.length - 1; j >= 0; j--) {
for (int k = j - 1; k >= 0; k--) {
countArray[j] += countArray[k];
}
}*/
//换下面这种方式
for (int j = 1; j < countArray.length; j++) {
countArray[j] += countArray[j - 1];
}
//经过这一步之后就能知道自己的分数排名了
System.out.println("计数数组按顺序求和之后：");
printArray(countArray);
//从后往前(从前往后也行，只不过不是稳定的排序了)挨个儿从原始数组中取出数x,
//然后在计数数组中查找x前面有y个数，
//然后将x存放到resultArray[y]的位置
//其实计数排序的核心思想就在这里，就是找到某个数前面到底有多少个数，然后插入到对应位置即可。
int[] resultArray = new int[data.length];
for (int m = data.length - 1; m >= 0; m--) {
int value = data[m];
int position = countArray[value];
resultArray[position - 1] = value;
countArray[value] -= 1;
}
System.out.println("排序之后的数组：");
printArray(resultArray);
}
private void printArray(int[] data) {
if (data == null || data.length == 0) {
return;
}
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
//int[] data = new int[]{10, 11, 12, 13, 14, 3, 5, 6, 7, 8};
//int[] data = new int[]{11, 24, 25, 10, 9, 11, 24, 25, 10, 9, 11, 67, 11, 67, 11, 24, 25, 11, 24, 25, 10, 9, 11, 67, 10, 9, 11, 67, 11, 24, 25, 10, 9, 11, 67, 33, 89, 11, 45, 22, 35, 56, 22, 23};
Sort sort = new Sort();
//sort.bubbleSort(data);
//sort.insertionSort(data);
//sort.selectionSort(data);
//int[] data = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
//sort.merge(data, 0, 4, 5, data.length - 1);
//sort.mergeSort(data, 0, data.length - 1);
int[] data = new int[]{2, 5, 3, 0, 2, 3, 0, 3};
//sort.quickSort(data, 0, data.length - 1);
//for (int i = 0; i < data.length; i++) {
// System.out.print(data[i] + " ");
//}
sort.countingSort(data);
}
}
