Java 常用排序算法

概述：

• 排序：把一个无序序列，通过某种方式，变成一个有序列。数组常用操作

经常用到的十大排序，如图所示：

按照比较类，和非比较类，又可以分为：

排序算法还可以分为：内部排序和外部排序。

• 内部排序：是数据记录在内存中进行排序。（冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序）
• 外部排序：是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

一、冒泡排序（Bubble Sort）

• 概述：相邻的元素，两两比较，较大的数下沉，较小的数冒起来，经过一轮比较，最大（小）值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。
• 适用场景：数据量很小的排序场景，因为冒泡的实现方式较为简单。

排序步骤：

1. 比较相邻的两个元素（从索引 0 开始）。如果第一个 arr[i] 比第二个 arr[i+1] 大，就进行交换；
2. 对每一对相邻元素，做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素，重复以上的步骤，除了最后一个；
4. 重复步骤 1~3，直到排序完成。

冒泡排序

• 冒泡排序实例：

package com.xxx.sort;

import java.util.Arrays;

/**
 * Description:冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
    // 冒泡排序
    private static void bubbleSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int length = array.length;
        // 外层循环，判断要走多少次;
        for (int j = 0; j < length - 1; j++) {
            // 通过flag 标识位，减少没有意义的比较
            boolean flag = false;
            // 内层循环：每次比较的次数（每次循环时，去掉未尾最大值，数组长度-j)
            // (array.length - 1) 防止索引越界，(array.length - 1 - i) 减少比较次数
            for (int i = 0; i < length - 1 - j; i++) {
                // 内层循环一次，获取一个最大值
                // 内层循环，升序（如果前一个值比后一个值大，则交换）
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    flag = true;
                }
            }

            // 如果没有交换过元素，则已经有序，不再进行接下来的比较
            if (flag = false) {
                break;
            }
        }
    }

    // 自定义方法：交换元素位置
    private static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

二、选择排序（Selection Sort）

• 概述：是一种简单直观的排序算法。它的工作原理是：第一次，从待排序的数据元素中，选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余的未排序元素中，寻找到最小（大）元素，继续放在起始位置，直到未排序元素个数为 0。
• 适用场景：元素个数较少时。

排序步骤：

1. 首先，在未排序序列中，找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中，继续寻找最小（大）元素，然后放到未排序序列的起始位置。
3. 重复第二步，直到所有元素均排序完毕。

• 说明：每次遍历的时候，将前面找出的最小值，看成一个有序的列表，后面的看成无序的列表，然后每次遍历无序的列表，找出最小值。

选择排序

• 选择排序实例：

package com.xxx.sort;

import java.util.Arrays;

/**
 * Description: 选择排序
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78, 1, 12, 0, -5};
        selectionSort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void selectionSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int length = array.length;
        // 外层循环：从 0 索引开始
        for (int i = 0; i < length - 1; i++) {
            // 保存最小数的索引（从索引 0 开始）
            int minIndex = i;
            // 内层循环：从 0 + 1 索引开始（自身不用比较）
            for (int j = i + 1; j < length; j++) {
                // 查找最小数位置，并标记为最小数的索引
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            // 内循环查找的最小值，与本次循环的开始值 array[i]，交换元素位置
            // （如果 minIndex 未改变，说明此数为最小值，不执行交换）
            if (i != minIndex) {
                swap(array, minIndex, i);
            }
            //说明：将i前面的数据看成一个排好的队列，i后面的看成一个无序队列。
            // 每次只需要找无序的最小值，做替换
        }
    }

    private static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

三、插入排序（Insertion Sort）

• 概述：也称为直接插入排序，是一种简单直观的排序算法，将初始数据，分为有序部分和无序部分，每一步将一个无序部分的数据，插入到前面已经排好序的有序部分中，直到插完所有元素为止。

排序步骤：

• 每次从无序部分中取出一个元素，与有序部分中的元素，从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。
  1. 默认从第二个数据开始比较。
  2. 如果第二个数据比第一个小，则交换。然后在用第三个数据比较，如果比前面小，则插入（交换）。否则，退出循环
• 说明：默认将第一个数据看成有序列表，后面为无序，循环后面无序列表的每一个数据，如果比前面的数据小则插入（交换）。否则退出。

插入排序

• 插入排序实例：

package com.xxx.sort;

import java.util.Arrays;

/**
 * Description: 插入排序
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78, 1, 12, 0, -5};
        insertionSort(array);
        System.out.println(Arrays.toString(array));
    }

    // 插入排序
    private static void insertionSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        // 直接插入排序：从 1 索引处开始，将后面的元素，
        // 插入之前的有序列表中，使之保持有序
        // 外层循环：定义轮次（从第二个元素开始）
        for (int i = 1; i < array.length; i++) {
            // 内层循环：进行比较插入
            // j--：将交换后的值，可以与前面的值进行再次比较，直到找到合适位置
            for (int j = i; j > 0; j--) {
                // 如果后边小，前边大，则交换位置
                if (array[j] < array[j - 1]) {
                    swap(array, j, j - 1);
                }
            }
        }
        // 另一种：
        /*for (int i = 1; i < array.length; i++) {
            int j = i;
            while (j > 0 && array[j] < array[j - 1]) {
                swap(array, j, j - 1);
                j--;
            }
        }*/

    }

    private static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

折半插入排序

• 直接插入排序确定位置，是通过将待排序的元素，与前面有序的序列一个个比较过去，从而得到最终的插入位置。那么，因为是顺序存储，利用数组实现排序，可以对前面的有序序列，使用折半查找来确定最终插入位置。
• 折半插入排序实例：

package com.xxx.sort;

import java.util.Arrays;

/**
 * 折半插入排序
 */
public class BinaryInsertSort {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78, 1, 12, 0, -5};
        binaryInsertSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void binaryInsertSort(int[] array) {
        int len = array.length;
        if (len == 0 || len == 1) return;
        // low high mid用于折半查找
        int low, high, mid;
        for (int i = 1; i < array.length; i++) {
            low = 0;
            high = i - 1;
            while (low <= high) {
                // (high+low)/2 这样的写法可能会超出int的表示范围
                mid = low + ((high - low) >> 1);
                if (array[mid] < array[i])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            // high + 1就是插入的位置
            int temp = array[i];
            // 找到插入位置后,对元素进行挪动
            for (int j = i - 1; j > high; j--)
                array[j + 1] = array[j];
            // 将待排序的元素插入找到的位置
            array[high + 1] = temp;
        }
    }
}

四、希尔排序（Shell Sort）

• 概述：希尔排序，又叫 缩小增量排序。是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种 插入排序，是直接插入排序，经过改进之后的一个更高效的版本，同时该算法是冲破 O(n2） 的第一批算法之一。它与插入排序的不同之处在于，它会 优先比较距离较远的元素。

• 基本思想：设待排序元素序列有 n 个元素，首先取一个整数 increment（小于序列元素总数）作为间隔，所有距离为 increment 的元素，放在同一个逻辑数组中，在每一个逻辑数组中，分别实行直接插入排序。然后缩小间隔 increment，重复上述逻辑数组划分和排序工作。直到最后取 increment = 1，将所有元素放在同一个数组中排序为止。

实现步骤：

1. 选 increment（增量），划分逻辑分组，组内进行直接插入排序。
2. 不断缩小 increment（增量），继续组内进行插入排序。
3. 直到 increment（增量）=1，在包含所有元素的序列内进行直接插入排序。

• 核心：合理选取增量
  • 克努特序列：h = 1; h = h * 3 + 1;

希尔排序

• 希尔排序实例：

package com.xxx.sort;

import java.util.Arrays;

/**
 * Description: 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78, 1, 12, 0, -5};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void shellSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        // 设置增量值
        int increment = 1;
        while (increment <= array.length / 3) {
            // （克努特序列）选取第一次增量：h=h*3+1，设置序列间隔
            increment = increment * 3 + 1;
        }
        // 遍历增量值：按（克努特序列）值递减，直到增量值为1
        for (int h = increment; h > 0; h = (h - 1) / 3) {
            // 插入排序：第一个索引为增量值
            for (int i = h; i < array.length; i++) {
                // 内循环：按增量值，比较插入
                for (int j = i; j > h - 1; j -= h) {
                    if (array[j] < array[j - h]) {
                        swap(array, j, j - h);
                    }
                }
            }
        }
    }

    private static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

五、快速排序（Quick Sort）

• 概述：快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
• 基本思想：挖坑填数+分治法。

算法描述：

• 快速排序使用分治法，来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
  • 从数列中挑出一个元素，称为 “基准”（pivot）；
  • 重新排序数列，所有元素比基准值小的，摆放在基准前面，所有元素比基准值大，的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归地（recursive）把小于基准值元素的子数列，和大于基准值元素的子数列排序。

快速排序

代码描述：

1. i = L; j = R; 将基准数挖出，形成第一个坑 a[i]。
2. j--，由后向前，找比它小的数，找到后，挖出此数填到前一个坑 a[i] 中。
3. i++，由前向后，找比它大的数，找到后，也挖出此数填到前一个坑 a[j] 中。
4. 再重复执行 2，3 二步，直到 i==j，将基准数填入 a[i]中。

• 快速排序实例（挖坑法）：

package com.xxx.sort;

import java.util.Arrays;

/**
 * Description: 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78, 1, 12, 0, -5};
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    private static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // 获取基准数据的索引位置
            int index = getIndex(array, low, high);
            // 递归：对基准数左边排序
            quickSort(array, low, index - 1);
            // 递归：对基准数右边排序
            quickSort(array, index + 1, high);
        }
    }

    // 获取基准数据的索引位置，并将大于基准数的值移动到右侧，小于基准值的移动到左侧
    private static int getIndex(int[] array, int low, int high) {
        // 左边索引值
        int i = low;
        // 右边索引值
        int j = high;
        // 1.取第一个元素为基准值（挖坑）
        int temp = array[i];
        while (i < j) {
            // 2.从右向左（后往前）查找比基准值小的数，挖出此数，填到前一个坑中
            while (i < j && array[j] > temp) {
                // 索引向左移（前），直到找到比基准值小的数
                j--;
            }
            if (i < j) {
                // 将找到的比基准值小的数，添加到基准值位置
                array[i] = array[j];
                // 将左索引+1：从左向右查找时的索引
                i++;
            }
            // 3.从左向右（前往后）查找比基准值大的数，挖出此数，填到前一个坑中
            while (i < j && array[i] < temp) {
                // 索引向右移（后），直到找到比基准值大的数
                i++;
            }
            if (i < j) {
                // 将找到的比基准值小的数，添加到基准值位置
                array[j] = array[i];
                // 将右索引-1：从右向左查找时的索引
                j--;
            }
        }
        // 3.跳出循环时 i 和 j 相等，为第一个基准值的位置，将其存入
        array[i] = temp;
        // 4.返回索引值（i,j 都可以）
        return i;
    }

    private static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

六、归并排序（Merge Sort）

• 概述：归并，字面上的意思是 合并，归并算法的核心思想是 分治法，就是将一个数组一刀切两半，递归切，直到切成单个元素，然后重新组装合并，单个元素合并成小数组，两个小数组合并成大数组，直到最终合并完成，排序完毕。

基本思路：(递归方式)

• 将数组分成 A，B 两组（如果这二组内的数据，都是有序的，那么就可以很方便的，将这二组数据进行排序）。
• 然后，将 A，B 组各自再分成二组。依次类推，当分出来的小组只有 一个数据 时，可以认为这个小组，组内已经达到了有序，然后，再合并相邻的二个小组就可以了。
• 这样，通过 先递归的分解 序列，再合并 序列，就完成了归并排序。

归并排序

算法思路

• 第一个步骤：拆分数组
  采用 2 路归并，(start+end)/2 处为临界点，将初始无序数组，拆分成两个无序序列，然后依次循环拆分，最后，再归并为一个新的有序序列；
  
• 拆分过程：
  判断条件，当 start=end 时，此时序列 只有一个元素，所以这是 临界点； 然后就是分组，拆分，采用递归的方式。最后再把所有拆分好的元素进行归并！
• 第二个步骤：归并序列
  拆完以后，需要将这些单独的元素，放入一个 额外空间储存，再进行排序。因此，归并排序是需要占用额外空间的。

• 注：每个序列，在比较元素大小最后的时候，有可能会多出来元素。默认把它放在，额外空间的最末尾处。

• 第三个步骤：额外空间覆盖原始空间

代码实现

• 归并排序其实要做两件事：
• 分解：将序列每次折半拆分；
• 合并：将划分后的序列段两两排序合并；
• 因此，归并排序实际上就是两个操作，拆分+合并。
• 归并排序实例：

package com.xxx.sort;

import java.util.Arrays;

/**
 * Description: 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78, 1, 12, 0, -5};
        mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    /**
     * @param array 初始数组
     * @param start 开始分组
     * @param end   结束分组
     * @return
     */
    // 拆分
    private static int[] mergeSort(int[] array, int start, int end) {
        // 当 start==end 时，此时分组里只有一个元素，所以这是临界点
        if (start < end) {
            // 分成左右两个分组，再进行递归
            int mid = (start + end) / 2;
            // 左侧分组
            mergeSort(array, start, mid);
            // 右侧分组
            mergeSort(array, mid + 1, end);
            // 递归之后，再归并一个大组
            merge(array, start, mid, end);
        }
        return array;
    }

    // 归并方法
    private static void merge(int[] array, int start, int mid, int end) {
        // 定义临时数组，长度为（end-start+1）
        int[] temp = new int[end - start + 1];
        // 左边起始数组索引
        int i = start;
        // 右边起始数组索引
        int j = mid + 1;
        // 临时数组索引
        int index = 0;
        // 合并序列：比较两个数组元素的大小，存入临时数组
        // 每次存入后，对应的索引值 +1
        while (i <= mid && j <= end) {
            // 将较小元素放入临时数组
            if (array[i] <= array[j]) {
                temp[index] = array[i];
                i++;
            } else {
                temp[index] = array[j];
                j++;
            }
            index++;
        }
        // 处理剩余元素
        // 左边剩余元素
        while (i <= mid) {
            temp[index] = array[i];
            i++;
            index++;
        }
        // 右边剩余元素
        while (j <= end) {
            temp[index] = array[j];
            j++;
            index++;
        }
        // 将临时数组中的元素，覆盖到原数组中
        for (int k = 0; k < temp.length; k++) {
            array[start + k] = temp[k];
        }
    }
}

迭代法

• 申请空间，使其大小，为两个已经排序序列之和，该空间用来存放合并后的序列；
• 设定两个指针，最初位置分别为，两个已经排序序列的起始位置；
• 比较两个指针所指向的元素，选择相对小的元素，放入到合并空间，并移动指针到下一位置；
• 重复步骤 3 ，直到某一指针到达序列尾；
• 将另一序列剩下的所有元素，直接复制到合并序列尾。
• 归并排序实例：非递归方式

package com.xxx.sort;

import java.util.Arrays;

/**
 * Description: 归并排序（非递归方式）
 */
public class MergeSort02 {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78, 1, 12, 0, -5};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        // mergeSize代表每次合并时，一半（可以理解为左侧）数据量的大小
        int mergeSize = 1;
        while (mergeSize < N) {
            int L = 0;
            while (L < N) {
                // 从L到M位置的数据就是当前合并部分的左侧数据大小，数据量为mergeSize
                int M = L + mergeSize - 1;
                // 表示当前要合并的数据量凑不够本次合并的左侧部分，比如本次要合并的数据量
                // 为8，则左侧数据量为4，但剩余未合并的数只有3个了，则这三个本次不用再
                // 合并，因为这三个数肯定在上次合并时已经有序了
                if (M >= N) {
                    break;
                }
                // 上面的过程是寻找左侧数据的过程，即：L...M，接下来要找右侧数据。此时
                // 就要分情况了。为什么呢？正常情况下右侧数据的边界是从M+1到M + mergeSize，
                // 但有可能右侧没这么多数据了，右边界实际是N-1，所以右边界应该取这两个
                // 数的最小值（其实就代表实际值）
                int R = Math.min(M + mergeSize, N - 1);
                // 分出了左右边界，接下来就是进行合并了
                merge(arr, L, M, R);
                L = R + 1;
            }
            // 此处的if语句算一个优化语句，不影响功能，防止的是：mergeSize在*2的过程
            // 中超过Integer.MAX_VALUE，出现错误
            if (mergeSize > N / 2) {
                break;
            }
            // 每次合并扩大一倍
            mergeSize = mergeSize * 2;
        }
    }

    public static void merge(int[] arr, int L, int M, int R) {
        // 准备辅助数组，存放排序后的数据
        int[] help = new int[R - L + 1];
        int i = 0;
        // 左侧数据起始位置
        int p1 = L;
        // 右侧数据起始位置
        int p2 = M + 1;
        // 左右两侧都没遍历完，即p1、p2都没越界
        while (p1 <= M && p2 <= R) {
            // 将左右部分的数据进行比较，小的数据存放到辅助数组，
            // 然后help和添加到辅助数组的部分指针（p1或p2）进行右移
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 当跳出wile循环，代表左或右某个部分已经遍历完了，然后将未
        // 遍历完的追加到辅助数组尾部，下面的两个while循环只能有一个执行
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        // 将辅助数组中的数据追加到原arr数组中
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }
}

七、基数排序（Radix Sort）

• 概述：基数排序是一种非比较型，整数排序算法，其基本思想是：将整数按位数，切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

实现步骤：

1. 将所有待比较数值，统一为同样的数位长度，数位较短的数，前面补零。
2. 从最低位开始，依次进行一次排序。
3. 依次从最低位排序，一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序

• 基数排序实例 1：数组元素不能包含负整数

package com.xxx.sort;

import java.util.Arrays;

/**
 * Description: 基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
        // 基数排序：通过分配再收集的方式排序（负数暂时有问题）
        int[] array = {18, 381, 983, 5, 147, 5915, 1, 927, 465, 4, 1906, 50, 498};
        radixSort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void radixSort(int[] array) {
        // 定义二维数组，放 10 个桶（0-9），每个桶可能存放元素个数
        // （按最大考虑：数组元素都存在一个桶中 array.length ）
        int[][] tempArray = new int[10][array.length];
        // 定义统计数组，索引值与桶索引相同（统计第个桶中存储元素个数，
        // 初始值为 0，每存储一个元素，值做一次自增）
        int[] counts = new int[10];
        // 获取最大值
        int max = getMax(array);
        // max 转成字符串，并获取长度
        int len = String.valueOf(max).length();
        // 确定循环轮次（数组最大值的位数）
        // 变量 n 从 1 开始，每次递增 10 ，取个、十、百....位数字
        for (int i = 0, n = 1; i < len; i++, n *= 10) {
            // 遍历数组中的元素
            for (int j = 0; j < array.length; j++) {
                // 获取每个位上的数字（% 10 取余数）
                int ys = array[j] / n % 10;
                // counts[ys]++:桶内存储元素个数自增
                tempArray[ys][counts[ys]++] = array[j];
            }
            // 取出桶中元素
            int index = 0;
            for (int k = 0; k < counts.length; k++) {
                if (counts[k] != 0) {
                    for (int h = 0; h < counts[k]; h++) {
                        // 从桶中取出元素，放回原数组
                        array[index] = tempArray[k][h];
                        index++;
                    }
                    // 清除上一次统计的个数
                    counts[k] = 0;
                }
            }
        }
    }

    // 获取最大值
    private static int getMax(int[] array) {
        int max = array[0];
        //  用后一个元素和前一个元素比较，查找最大值，保存到 max
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }
}

• 基数排序实例 2：数组元素可包含负整数

package com.xxx.sort;

import java.util.Arrays;

/**
 * 基数排序
 */
public class RadixSort02 {
    public static void main(String[] args) {
        int[] array = {18, -147, 5915, 365, 260, 1, 927, 2, 465, 4, -1906, 0, 498};
        // 获取数组最大元素
        int maxDigit = getMaxDigit(array);
        // 基数排序
        radixSort(array, maxDigit);
        System.out.println(Arrays.toString(array));
    }

    // 获取最高位数
    private static int getMaxDigit(int[] array) {
        // 获取最大值
        int maxValue = getMaxValue(array);
        return getNumLength(maxValue);
    }

    // 获取最大值
    private static int getMaxValue(int[] array) {
        int maxValue = array[0];
        for (int value : array) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    // 获取元素位数长度（个位：1位  千位：4位）
    private static int getNumLength(long num) {
        // 0 返回 1位
        if (num == 0) {
            return 1;
        }
        int length = 0;
        // 元素/10 取位数
        for (long temp = num; temp != 0; temp /= 10) {
            length++;
        }
        return length;
    }

    // 基数排序
    private static int[] radixSort(int[] array, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，
            // [10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < array.length; j++) {
                int bucket = ((array[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], array[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    array[pos++] = value;
                }
            }
        }
        return array;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param array
     * @param value
     */
    private static int[] arrayAppend(int[] array, int value) {
        array = Arrays.copyOf(array, array.length + 1);
        array[array.length - 1] = value;
        return array;
    }
}

八、堆排序（Heap Sort）

• 概述：堆排序，是指利用堆这种数据结构，所设计的一种排序算法。该排序方式主要利用了堆的一些特点：

  1. 结构近似于完全二叉树，这样就可以在每层的节点中，从左到右遍历。
  2. 子结点的值，总是小于（或者大于）它的父节点，即是一个大顶堆或小顶堆。

• 堆又分大根堆和小根堆，倘若要升序，选择大根堆，倘若要降序，选择小根堆。

  • 大根堆：根节点的值，不小于左右子节点的值。
  • 小根堆：根节点的值，不大于左右子节点的值。

排序步骤：

• 堆排序是把一个数组，看做是一颗完全二叉树。
  • 先对乱序的数组建立大根堆，可以得到数组的第一个元素（看做完全二叉树的话，就是根节点）就是最大的。
  • 将其与数组最后面的那个值交换，然后重新调整，变为大根堆，依次类推。

堆排序

• 堆排序实例：

package com.xxx.sort;

import java.util.Arrays;

/**
 * Description:堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78, 1, 12, 0, -5};
        // 调整成大顶堆
        // 定义开始调整的位置
        int startIndex = (array.length - 1) / 2;
        // 循环开始调整
        for (int i = startIndex; i >= 0; i--) {
            toMaxHeap(array, array.length, i);
        }
        // 经过上述操作，已经成为大顶堆，把根元素和最后一个元素调换
        for (int i = array.length - 1; i > 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            // 换完之后，将剩余元素调整成大顶堆
            toMaxHeap(array, i, 0);
        }
        System.out.println(Arrays.toString(array));
    }

    /**
     * Description：调整成大顶堆
     *
     * @param array 要排序的数组
     * @param size  调整的元素个数
     * @param index 开始调整的索引位置
     */
    private static void toMaxHeap(int[] array, int size, int index) {
        // 获取左右子节点的索引
        int leftNodeIndex = index * 2 + 1;
        int rightNodeIndex = index * 2 + 2;
        // 查找最大节点所对应的索引
        int maxIndex = index;
        // leftNodeIndex < size: 防止递归调用后，角标越界
        if (leftNodeIndex < size && array[leftNodeIndex] > array[maxIndex]) {
            maxIndex = leftNodeIndex;
        }
        if (rightNodeIndex < size && array[rightNodeIndex] > array[maxIndex]) {
            maxIndex = rightNodeIndex;
        }
        // 调换位置
        if (maxIndex != index) {
            int temp = array[maxIndex];
            array[maxIndex] = array[index];
            array[index] = temp;
            // 调完之后，可能会影响下面的子树，不再是大顶堆，需要再次调整
            toMaxHeap(array, size, maxIndex);
        }
    }
}

九、计数排序（Counting Sort）

• 概述：计数排序，不是比较排序算法，是一种利用桶，空间换时间的排序算法，在面对在一定范围内，大量重复数字的场景下，很适用。

排序步骤

1. 找出原数组中元素值最大的，记为 max。
2. 创建一个新数组 count，其长度是 max+1，其元素默认值都为 0。
3. 遍历原数组中的元素，以原数组中的元素作为 count 数组的索引，以原数组中的元素出现次数，作为 count 数组的元素值。
4. 创建结果数组 result，起始索引 index。
5. 遍历 count 数组，找出其中元素值大于 0 的元素，将其对应的索引，作为元素值，填充到 result 数组中去，每处理一次，count 中的该元素值减 1，直到该元素值，不大于 0，依次处理 count 中剩下的元素。
6. 返回结果数组 result。

计数排序

• 计数排序实例：

package com.xxx.sort;

import java.util.Arrays;

/**
 * Description:计数排序
 */
public class CountingSort02 {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78, 1, 12, 0, -5};
        int min = getMin(array);
        int max = getMax(array);
        countSort(array, min, max);
        System.out.println(Arrays.toString(array));
    }

    /**
     * @param arr 数组
     * @param min 该数组中的最小值
     * @param max 该数组中的最大值
     * @Title: countSort
     * @Description:计数排序,适用于数字的范围小，排序量大的数组
     * @return: int[]
     */
    public static void countSort(int[] arr, int min, int max) {
        // arr的最小值到最大值之间的数字，即为countArr的下标
        int[] countArr = new int[max - min + 1];
        // 统计arr中每个数字出现的次数
        for (int j = 0; j < arr.length; j++)
            countArr[arr[j] - min]++;
        int[] res = new int[arr.length];
        // 将countArr变为累加数组,这一步主要是实现算法稳定
        for (int m = 1; m < countArr.length; m++)
            countArr[m] += countArr[m - 1];
        // 这一步参见基数排序的过程示意图
        for (int k = arr.length - 1; k >= 0; k--)
            res[--countArr[arr[k] - min]] = arr[k];
        // 将排序好的数组赋值给arr
        for (int i = 0; i < arr.length; i++) {
            arr[i] = res[i];
        }
    }

    // 获取最小值
    private static int getMin(int[] array) {
        int min = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }
        return min;
    }

    // 获取最大值
    private static int getMax(int[] array) {
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }
}

十、桶排序（Bucket Sort）

• 概述：桶排序，即箱排序（是计数排序的升级版），其原理是将数组分到有限数量的桶子里，每个桶子再个别排序。利用了函数的映射关系，高效与否的关键，就在于这个映射函数的确定。

排序步骤：

1. 先计算装所有元素，所需要的桶的个数。
2. 将待排序元素，按大小装到对应的桶中。
3. 对每个桶内的元素进行排序。
4. 将所有桶中的元素，按顺序放入到原数组中。

• 注意：如果递归使用桶排序，为各个桶排序，则当桶数量为 1 时，要手动减小 BucketSize，增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。

桶排序

• 桶排序实例：

package com.xxx.sort;

import java.util.*;

/**
 * Description:桶排序
 */
public class BucketSort {
    public static void main(String[] args) {
        int[] array = {12, 63, 1, 95, 44, 62, 78, 1, 12, 0, -5};
        bucketSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * Description: 桶排序
     *
     * @param array 要排序的数组
     * @return void
     */
    public static void bucketSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        // 建立桶，个数和待排序数组长度一样
        int length = array.length;
        LinkedList<Integer>[] bucket = (LinkedList<Integer>[]) new LinkedList[length];
        // 待排序数组中的最大值
        int maxValue = Arrays.stream(array).max().getAsInt();
        // 根据每个元素的值，分配到对应范围的桶中
        for (int i = 0; i < array.length; i++) {
            int index = toBucketIndex(array[i], maxValue, length);
            // 没有桶才建立桶(延时)
            if (bucket[index] == null) {
                bucket[index] = new LinkedList<>();
            }
            // 有桶直接使用
            bucket[index].add(array[i]);
        }
        // 对每个非空的桶排序，排序后顺便存入临时的List，则list中已经有序）
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
                temp.addAll(bucket[i]);
            }
        }

        // 将temp中的数据写入原数组
        for (int i = 0; i < length; i++) {
            array[i] = temp.get(i);
        }
    }

    /**
     * Description: 映射函数，将值转换为应存放到的桶数组的索引
     *
     * @param value
     * @param maxValue
     * @param length
     * @return int
     */
    private static int toBucketIndex(int value, int maxValue, int length) {
        return (value * length) / (maxValue + 1);
    }
}

排序算法比较：

• 术语说明：
  • 稳定：如果 a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面；
  • 不稳定：如果 a 原本在 b 的前面，而 a = b ，排序之后 a 可能会出现在 b 的后面；
  • 内排序：所有排序操作都在内存中完成；
  • 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
  • 时间复杂度：一个算法执行所耗费的时间。
  • 空间复杂度：运行完一个程序所需内存的大小。