桶排序和计数排序

桶排序和计数排序都是一种排序效率比较高的排序算法，桶排序当桶的个数与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);
    }
}