【java排序算法】堆排序，桶排序，计数排序

桶排序

* 在额外空间充足的情况下，尽量增大桶的数量，极限情况下每个桶只有一个数据时，或者是每只桶只装一个值时，
* 完全避开了桶内排序的操作，桶排序的最好时间复杂度就能够达到 O(n)。

//桶排序
/*


比如高考总分 750 分，全国几百万人，我们只需要创建 751 个桶，循环一遍挨个扔进去，排序速度是毫秒级。

但是如果数据经过桶的划分之后，桶与桶的数据分布极不均匀，有些数据非常多，
有些数据非常少，比如[ 8，2，9，10，1，23，53，22，12，9000 ]这十个数据，我们分成十个桶装，
结果发现第一个桶装了 9 个数据，这是非常影响效率的情况，会使时间复杂度下降到 O(nlogn)，
解决办法是我们每次桶内排序时判断一下数据量，如果桶里的数据量过大，那么应该在桶里面回调自身再进行一次桶排序。
*
* */

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {
    public static void sort(int[] arr){
        //最大最小值
        int max = arr[0];
        int min = arr[0];
        int length = arr.length;
        for(int i=1; i<length; i++) {
            if(arr[i] > max) {
                max = arr[i];
            } else if(arr[i] < min) {
                min = arr[i];
            }
        }
        //最大值和最小值的差
        int diff = max - min;
        //桶列表
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for(int i = 0; i < length; i++){
            bucketList.add(new ArrayList<>());
        }
        //每个桶的存数区间
        float section = (float) diff / (float) (length - 1);
        //数据入桶
        for(int i = 0; i < length; i++){
            //当前数除以区间得出存放桶的位置 减1后得出桶的下标
            int num = (int) (arr[i] / section) - 1;
            if(num < 0){
                num = 0;
            }
            bucketList.get(num).add(arr[i]);
        }
        //桶内排序
        for(int i = 0; i < bucketList.size(); i++){
            //jdk的排序速度当然信得过
            Collections.sort(bucketList.get(i));
        }
        //写入原数组
        int index = 0;
        for(ArrayList<Integer> arrayList : bucketList){
            for(int value : arrayList){
                arr[index] = value;
                index++;
            }
        }
    }
}

 

计数排序

m 指的是数据量，说的简单点，计数排序算法的时间复杂度约等于 O(n)，
计数局限性

如果我要排的数据里有 0 呢？ int[] 初始化内容全是 0 ，排毛线。

如果我要排的数据范围比较大呢？比如[ 1，9999 ]，我排两个数你要创建一个 int[10000] 的数组来计数？

对于第一个 bug ，我们可以使用偏移量来解决，比如我要排[ -1，0，-3 ]这组数字，这个简单，
我全给你们加 10 来计数，变成[ 9，10，7 ]计完数后写回原数组时再减 10
。不过有可能也会踩到坑，万一你数组里恰好有一个 -10，你加上 10 后又变 0 了，排毛线。

对于第二个 bug ，确实解决不了，如果是[ 9998，9999 ]这种虽然值大但是相差范围不大的数据我们也可以使用偏移量解决，
比如这两个数据，我减掉 9997 后只需要申请一个 int[3] 的数组就可以进行计数。
由此可见，计数排序只适用于正整数并且取值范围相差不大的数组排序使用，它的排序的速度是非常可观的。
* */

/计数排序

public class CountSort {
    public static void sort(int[] arr) {
        //找出数组中的最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //初始化计数数组
        int[] countArr = new int[max + 1];
        //计数
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
            arr[i] = 0;
        }
        //排序
        int index = 0;
        for (int i = 0; i < countArr.length; i++) {
            if (countArr[i] > 0) {
                arr[index++] = i;
            }
        }
    }
}

堆排序：

//O(nlogn)。

//O(nlogn)。
public class HeapSort {
    public static void main(String[] args) {
        int[] array = new int[] { 2, 1, 4, 3, 6, 5, 8, 7 };
        // 接下来就是排序的主体逻辑
        sort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void sort(int[] array) {
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, array.length);
        }
        // 上述逻辑，建堆结束
        // 下面，开始排序逻辑
        for (int j = array.length - 1; j > 0; j--) {
            // 交换确定元素
            swap(array, 0, j);
            // 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
            // 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
            // 而这里，实质上是自上而下，自左向右进行调整的
            adjustHeap(array, 0, j);
        }
    }
    public static void adjustHeap(int[] array, int i, int length) {
        // 先把当前元素取出来，因为当前元素可能要一直移动
        int temp = array[i];
        // 可以参照sort中的调用逻辑，在堆建成，且完成第一次交换之后，实质上i=0；也就是说，是从根所在的最小子树开始调整的
        // 接下来的讲解，都是按照i的初始值为0来讲述的
        // 这一段很好理解，如果i=0；则k=1；k+1=2
        // 实质上，就是根节点和其左右子节点记性比较，让k指向这个不超过三个节点的子树中最大的值
        // 这里，必须要说下为什么k值是跳跃性的。
        // 首先，举个例子，如果a[0] > a[1]&&a[0]>a[2],说明0,1,2这棵树不需要调整，那么，下一步该到哪个节点了呢？肯定是a[1]所在的子树了，
        // 也就是说，是以本节点的左子节点为根的那棵小的子树
        // 而如果a[0}<a[2]呢，那就调整a[0]和a[2]的位置，然后继续调整以a[2]为根节点的那棵子树，而且肯定是从左子树开始调整的
        // 所以，这里面的用意就在于，自上而下，自左向右一点点调整整棵树的部分，直到每一颗小子树都满足大根堆的规律为止
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            // 让k先指向子节点中最大的节点
            if (k + 1 < length && array[k] < array[k + 1]) {
                k++;
            }
            // 如果发现子节点更大，则进行值的交换
            if (array[k] > temp) {
                swap(array, i, k);
                // 下面就是非常关键的一步了
                // 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？
                // 所以，循环对子节点所在的树继续进行判断
                i = k;
                // 如果不用交换，那么，就直接终止循环了
            } else {
                break;
            }
        }
    }
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}