[数据结构与算法]动画详解十大经典排序算法【Java版实现】(下)

上篇博客介绍了五种排序算法，分别为：冒泡排序，选择排序，插入排序，希尔排序，归并排序，博客地址如下：

动画详解十大经典排序算法【Java版实现】(上)

本篇博客针对剩下的五种排序算法展开介绍：快速排序，堆排序，计数排序，桶排序，基数排序。

1. 快速排序

算法介绍

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录均比另一部分记录小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的效果。

动画演示

?

步骤描述

• 从数列中挑出一个元素，称为 “基准”；

• 重新排序数列，比基准值小的元素放在前面，比基准值大的元素放在后面；

• 递归地把小于基准值元素的子数列和大于基准值元素的子数列进行排序，直到不能递归；

代码实现

    public void quickSort(int[] a, int start, int end) {
        if (start < end) {
            //选基准值
            int baseNum = a[start];
            //记录中间值
            int midNum;
            int i = start;
            int j = end;
            do {
                while ((a[i] < baseNum) && i < end) {
                    i++;
                }
                while ((a[j] > baseNum) && j > start) {
                    j--;
                }
                if (i <= j) {
                    midNum = a[i];
                    a[i] = a[j];
                    a[j] = midNum;
                    i++;
                    j--;
                }
            } while (i <= j);
            if (start < j) {
                quickSort(a, start, j);
            }
            if (i < end) {
                quickSort(a, i, end);
            }
        }
    }

2. 堆排序

算法介绍

堆排序是利用堆的数据结构进行排序的方法，可以将堆看做是一个完全二叉树。

堆排序中有两个概念需要明确：

大顶堆：每个结点的值都大于等于其左右孩子结点的值，称为大顶堆；

小顶堆：每个结点的值都小于等于其左右孩子结点的值，称为小顶堆；

动画演示

步骤描述

• 将待排序列构造成一个大顶堆(或小顶堆)；

• 整个序列的最大值(或最小值)就是堆顶的根结点，将根节点的值和堆数组的末尾元素交换；

• 将剩余的 n-1 个序列重新构造成一个堆；

• 反复执行，最终得到一个有序序列；

代码实现

    /**
     * 调整堆
     *
     * @param array
     * @param index
     * @param length
     */
    public static void heapAdjust(int[] array, int index, int length) {
        //保存当前结点的下标
        int max = index;
        //当前节点左子节点的下标
        int lchild = 2 * index;
        //当前节点右子节点的下标
        int rchild = 2 * index + 1;
        if (length > lchild && array[max] < array[lchild]) {
            max = lchild;
        }
        if (length > rchild && array[max] < array[rchild]) {
            max = rchild;
        }
        //若此节点比其左右孩子的值小，就将其和最大值交换，并调整堆
        if (max != index) {
            int temp = array[index];
            array[index] = array[max];
            array[max] = temp;
            heapAdjust(array, max, length);
        }
    }

    /**
     * 堆排序
     *
     * @param array
     * @return
     */
    public static int[] heapSort(int[] array) {
        int len = array.length;
        //初始化堆，构造一个最大堆
        for (int i = (len / 2 - 1); i >= 0; i--) {
            heapAdjust(array, i, len);
        }
        //将堆顶的元素和最后一个元素交换，并重新调整堆
        for (int i = len - 1; i > 0; i--) {
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            heapAdjust(array, 0, i);
        }
        return array;
    }

3. 计数排序

算法介绍

计数排序是一种稳定的排序算法，只能对整数进行排序。

它使用一个额外的数组，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。

动画演示

步骤描述

• 扫描整个序列 A，获取最小值 min 和最大值 max；

• 开辟一块新的空间创建新数组 B，长度为 (max - min + 1)；

• 数组 B 中 i 的元素记录的值是 A 中某元素出现的次数；

• 遍历数组 B，输出相应元素以及对应的个数；

代码实现

    /**
     * 计数排序
     *
     * @param array
     * @return
     */
    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;
    }

4. 桶排序

算法介绍

桶排序是计数排序的升级版，它利用函数的映射关系，假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别进行排序，最后拼接为完整的排序数据。

动画演示

步骤描述

• 设置固定数量的空桶；

• 把数据放到对应的桶中；

• 对每个不为空的桶中数据进行排序；

• 拼接不为空的桶中数据，得到结果；

代码实现

    /**
     * 桶排序
     *
     * @param array
     * @param bucketSize 桶中可以放多少种元素
     * @return
     */
    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;
    }

5. 基数排序

算法介绍

基数排序是非比较的排序算法，对每一位进行排序，从最低位开始。

首先对低位排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

动画演示

?

步骤描述

• 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零；

• 从最低位开始，依次进行排序；

• 一直到最高位排序完成，即可得到一个有序序列；

代码实现

    /**
     * 基数排序
     *
     * @param array
     * @return
     */
    public static int[] RadixSort(int[] array) {
        if (array == null || array.length < 2)
            return array;
        // 1.先算出最大数的位数；
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max, array[i]);
        }
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        int mod = 10, div = 1;
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10; i++) {
            bucketList.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int j = 0; j < array.length; j++) {
                int num = (array[j] % mod) / div;
                bucketList.get(num).add(array[j]);
            }
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int k = 0; k < bucketList.get(j).size(); k++) {
                    array[index++] = bucketList.get(j).get(k);
                }
                bucketList.get(j).clear();
            }
        }
        return array;
    }

介绍完十种排序算法，最后来总结下它们的特点：

?本篇博客参考了以下内容，深表感谢：

十大经典排序算法动画与解析，看我就够了！（配代码完全版） - 五分钟学算法 - 博客园

Java常用的八种排序算法与代码实现 - 我心自在 - 博客园

十大经典排序算法总结（Java实现+动画）_meibenxiang的博客-CSDN博客