前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
使用堆排序和基数排序对整数数组进行排序计算

解决方案

堆排序（从小到大）：
1、将数组看成堆，那么当前元素i的左子树为2i+1， 右子树2i+2
2、最后一个非叶子节点的位置为数组中点位置
3、根据以上两点，首先 从最后一个非叶子节点开始进行下沉操作，结束后堆顶就是最值
之后将堆顶元素和堆底元素进行置换操作，仅对堆顶进行下沉操作即可
时间：O(nlog) 空间 ：O（1）
是否稳定排序：非 (感悟中有解释)
是否原地排序：是
基数排序：
1、将数组根据个位放入桶中进行一波计数排序，再根据十位、百位、直到最大值的最高位计数排序完成后，整体就是有序的了
具体可以查看代码
时间：O(nk), k应该是最大值的位数 空间 ：O（n+k）
是否稳定排序：是
是否原地排序：否

代码编写

java语言版本

堆排序：

    /**
     * 堆排序（二轮）
     * @param arr
     * @return
     */
    public static int[] headSortCP(int[] arr){
        if (arr == null || arr.length <= 1){
            return arr;
        }
        int len = arr.length;
        // 先做一个整体的堆调整
        for (int i = len/2-1; i >= 0; i--){
            // 从倒数第一个非叶子节点开始下沉
            headSinkASC(arr, i, len);
        }
        // 开始弹出数据,其实这里如果只需要top5就只弹出5个值即可
        for (int i = arr.length-1; i >= 0; i--){
            // 交换顶元素和尾巴元素
            CommonUtils.swap(arr, 0, i);
            // 只对顶元素进行一次堆调整,注意长度需要减1，相当于去掉了一个尾巴
            headSinkASC(arr, 0, --len);
        }
        return arr;
    }

    /**
     * 堆下沉操作，从parentIndex开始
     * 从大到小的引擎
     * @param arr
     * @param parentIndex
     * @param len 指定数组长度边界,超出的部分不做比较
     */
    private static void headSinkDESC(int[] arr, int parentIndex, int len) {
        int parent = parentIndex;
        int leftIndex = parent*2+1;
        while (leftIndex < len){
            int rightIndex = parent*2+2;
            // 找到parent和left中较小的那个
            int minIndex = arr[parent] < arr[leftIndex] ? parent : leftIndex;
            if (rightIndex < len && arr[rightIndex] < arr[minIndex]) {
                // 判断右边是否是三者中最小的
                minIndex = rightIndex;
            }
            if (minIndex == parent){
                // 小丑竟是我自己
                break;
            }
            // 说明需要交换
            CommonUtils.swap(arr, minIndex, parent);
            // 滑动角标
            parent = minIndex;
            leftIndex = parent*2+1;
        }
    }

    /**
     * 堆下沉操作，从parentIndex开始
     * 从小到大的引擎
     * @param arr
     * @param parentIndex
     * @param len 指定数组长度边界,超出的部分不做比较
     */
    private static void headSinkASC(int[] arr, int parentIndex, int len) {
        int parent = parentIndex;
        int leftIndex = parent*2+1;
        while (leftIndex < len){
            int rightIndex = parent*2+2;
            // 找到parent和left中较大的那个
            int maxIndex = arr[parent] > arr[leftIndex] ? parent : leftIndex;
            if (rightIndex < len && arr[rightIndex] > arr[maxIndex]) {
                // 判断右边是否是三者中最大的
                maxIndex = rightIndex;
            }
            if (maxIndex == parent){
                // 小丑竟是我自己
                break;
            }
            // 说明需要交换
            CommonUtils.swap(arr, maxIndex, parent);
            // 滑动角标
            parent = maxIndex;
            leftIndex = parent*2+1;
        }
    }

基数排序:

    /**
     * 基数排序
     * @param arr
     * @return
     */
    public static int[] radioSortCP(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int len = arr.length;
        // 10个桶代表着10进制，0->9
        List<LinkedList<Integer>> buckets = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
             buckets.add(new LinkedList<>());
        }
        // 找到最大值的位数
        int max = Integer.MIN_VALUE;
        // 最少也有一位
        int maxVNum = 1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        while ((max = max/10) != 0){
            maxVNum++;
        }
        for (int i = 0; i < maxVNum; i++) {
            // i代表要按照第几位进行装桶
            for (int j = 0; j < arr.length; j++) {
                // 取第i位
                int num = (int) (arr[j]/(Math.pow(10, i)))%10;
                buckets.get(num).offer(arr[j]);
            }
            // 按照个位进行重新排序
            int index = 0;
            for (int k = 0; k < 10; k++) {
                LinkedList<Integer> bucket = buckets.get(k);
                while (bucket != null && !bucket.isEmpty()) {
                    arr[index++] = bucket.poll();
                }
            }
        }
        return arr;
    }



    public static void main(String[] args) {
        int[] arr = {3, 4, 1, 5, 2, 8, 6, 9};
        //int[] arr = {1000000000,10000000};

        int[] ints = radioSortCP(arr);
        CommonUtils.printArr(ints);
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

1、堆排序不稳定是因为顶和底会调换位置，导致相同元素靠后的可能因为调换位置调换到前面
2、堆排序为什么中点是最后一个叶子节点？
因为二叉树的特性，叶子节点永远比非叶子节点相等或者多1（数据结构中有说过，每一个叶子节点变成非叶子节点时，就会增加1个或两个叶子，因此总数一定是叶子和非叶子对半或非叶子多叶子一个）
3、为什么后面只需要进行一次自顶向下的下沉操作？
因为刚开始进行了一次所有非叶子节点的下沉操作，其目的就是保证每一个节点都比自己的孩子节点大，但是整个数组不能保证顺序，当堆顶和堆底更换位置以后，除了堆顶以外的其他元素都是符合条件的，因此只需要下沉堆底即可，并且堆底可能是最值，也可能不是最值
堆排序可以用来计算大数据的topn，这个非常重要，因此堆排序是必须要熟练掌握的排序算法
4、基数排序没有交换的过程，但是最后仍然排序成功了，每一位都是计数排序，为什么稳定呢？是因为堆排序的低位排序能够保证在高位进行计数排序的时候，每一个桶内的顺序是有序且稳定的！

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！