各个排序算法的总结为：

稳定：如果a=b并且a在排序之前出现在b前，排序之后a仍然会出现在b的前面。

冒泡排序

稳定，平均时间复杂度为：n^2
基本思想：通过对待排序从前往后（从下标小的元素开始），依次比较相邻的元素的值，如是发现逆序则交换，使值较大的元素逐渐从前移向后部，像水底的起跑一样。

总结规则：

1. 一共进行n-1次大循环（数组中有n个元素）
2. 每一次排序的元素在逐渐的减少
3. 如果在某次排序的过程中，没有发生一次交换，说明排序已经完成了

public static int[] bubbleSort(int[] arr) {
        int temp = 0;
        boolean flag = false;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if(!flag){
                break;
            }else {
                flag = false;
            }
        }
        return arr;
    }

插入排序

插入排序属于内部排序法，是对于欲排序的元素以插入的方式寻找该元素的适当位置。

插入排序的思想：把n个待排序的元素看做是一个有序表和无序表，开始时有序表中只含有一个元素，无序表中包含n-1个元素。排序的过程中，每次从无序表中取出第一个元素，把它插入到有序表中的适当位置，使之形成新的有序表。

代码的实现：

/**
     * 插入排序，将列表看做一个有序表和一个无序表
     * @param arr
     * @return
     */
public static int[] insertSort(int[] arr){
    int temp = 0;
    int index = 0;
    for (int i = 1; i < arr.length; i++) {
        temp = arr[i];
        index = i-1;
        // 倒叙判断从i-1到0进行判断，如果出现temp>arr[index]，则说明arr[index+1]则为要插入的部分
        while (index >= 0  && temp < arr[index]){
            arr[index+1] = arr[index];    //依次移动数据
            index --;
        }
        // 在arr[index+1]中插入数据
        arr[index+1] = temp;
    }
    return arr;
}

希尔排序

基本思想： 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

安照一定的步长，将一定数量的数据分为一组。设置每组的数据增量为上一次增量的一半，然后将每组的数据量增加，数组减少，直到只剩下一个数组为止。

希尔排序方法：

1. 对有序序列插入时采用交换法
2. 对有序序列插入时采用移动法

 /**
     * 希尔交换法
     * @param arr
     * @return
     */
    public static int[] shellSort(int[] arr){
        int temp = 0;
        int count = 0;
        for(int gap = arr.length/2; gap > 0; gap /= 2){
            for(int i=gap; i< arr.length; i++){
                // 遍历组中的所有数据，gap为步长
                for(int j=i-gap; j >= 0; j -= gap){
                    if(arr[j] > arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
        return arr;
    }
// 移动位置（结合插入排序）
    public static int[] shellMoveSort(int[] arr){
        for(int gap = arr.length/2; gap > 0; gap /= 2){
            for(int i=gap; i < arr.length; i++){
                int j = i;
                int temp = arr[j];
                if(arr[j] < arr[j-gap]){
                    while (j - gap >= 0 && temp < arr[j - gap]){
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分为一些小的问题然后递归求解，而治阶段则将分的阶段得到的各答案“修补”在一起，即分而治之）

基本方法：

1. 首先将数组成分成两个部分，一直拆分直到拆分到每个子数组中只有一个元素
2. 然后进行合并相同相邻的拆分部分，按照顺序进行合并，直到合并成完整的数组
3. 使用递归方法完成最好，时间复杂度为O(nlogn)

 /**
     * 归并排序
     * @param arr
     * @param left
     * @param right
     * @return
     */
public static int[] mergeSort(int[] arr, int left, int right){
    // 如果left大于right，说明数组中只有1个或者没有数据，则将直接返回空
    if(left >= right) return null;
    int mid = (left + right)/2;
    // 分割
    mergeSort(arr, left, mid);
    mergeSort(arr, mid+1, right);
    int i = left;
    int j = mid+1;
    int t = 0;
    int[] temp = new int[(right - left + 1)];
    while (i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            temp[t] = arr[i];
            t ++;
            i ++;
        }else {
            temp[t] = arr[j];
            t ++;
            j ++;
        }
    }
    // 将剩余的内容填充到temp中
    while (i <= mid){
        temp[t] = arr[i];
        t++;
        i++;
    }
    // 将剩余的right内容填充到temp中
    while (j <= right){
        temp[t] = arr[j];
        t++;
        j++;
    }
    // 将temp数据拷贝到arr中
    for(int k=left; k<=right; k++){
        arr[k] = temp[k-left];
    }
    System.out.println("排序后的数据为：" + Arrays.toString(temp));
    return arr;
}

堆排序

堆是一个特殊的二叉树，堆分为大顶堆和小顶堆。

堆排序的最好、最坏、平均时间复杂度都是O(nlogn)，是一种不稳定的排序。
大顶堆：每个节点的值都大于或等于左右孩子节点的值。
小顶堆：每个节点的值都小于或等于左右孩子节点的值。

如果当前节点在数组中的位置为 i，那么左子节点的位置为2*i+1, 右子节点为2*i+2

最后一个非叶子结点：arr.length/2 - 1

堆排序的思想：

1. 将待排序序列构造成一个大顶堆
2. 此时，整个序列的最大值就是堆顶的根节点
3. 将其与末尾元素进行交换，此时末尾为最大值
4. 然后将剩余的n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复，便可以等到一个有序序列。

堆排序的代码实现如下：

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        for(int i=arr.length/2 - 1; i >= 0; i--) {
            bigHeapSort(arr, i, arr.length);
        }
//        bigHeapSort(arr, 1, arr.length);
        // 并不是所有节点的值全部都已经排序好了，还需要进一步的循环
        for(int j=arr.length-1; j > 0; j--){
            swap(arr, 0, j);
            bigHeapSort(arr, 0, j);
        }
        System.out.println("输出排序后的内容为：" + Arrays.toString(arr));
    }
    // 使用堆排序的代码
    public static void bigHeapSort(int[] arr, int i, int len) {
        int temp = arr[i];
        for(int k = 2 * i + 1; k < len; k = k * 2 + 1) {
            // 如果k+1存在，并且k+1位置的值较大，则将k置为k+1
            if(k+1 < len && arr[k] < arr[k + 1]) {
                k = k + 1;
            }
            // 如果arr[i]位置的值要小于arr[k]，也就是说子节点的值要大于父节点，则进行交换
            if(tmp < arr[k]) {
                // k点的值往上移动，然后将子节点设置为下一次判断的父节点
                arr[i] = arr[k];
                i = k;
            }else {
                // 如果k点的值要小于等于i点的值，也就是说子节点的值要小于父节点的值，那就跳出
                break;
            }
        }
        // 将将要替换的值赋值给最后遍历到的节点
        arr[i] = temp;
    }
}

基数排序

基数排序属于“分配式排序”，又称桶子法，它是通过键值的各个位的值，将要排序的元素分配到某些“桶”中，达到排序的作用
2. 基数排序属于稳定性的排序，基数排序法的是效率高的稳定性排序法
3. 基数排序是桶排序的拓展
4. 基数排序的实现方法：将整数位按照位数切割成不同的数字，然后按照每个位分别比较。

实现的方法：

1. 定义一个二维数组，表示10个桶，每一个桶就是一个一维数组
2. 为了防止在放入输的时候数据溢出，则每个一维数组（桶），大小定为arr.length
3. 基数排序就是使用空间换时间的经典算法。

 /**
     * 基数排序
     * @param arr
     * @return
     */
public static int[] radixSort(int[] arr){
    int[][] bubble = new int[10][arr.length];   //设置桶的数量，每个桶最多盛放整个数组
    // 寻找数组中最大的数
    int max = arr[0];
    for(int i=1; i<arr.length; i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }
    int maxLength = (max + "").length();
    // 根据数值中最大数据的位数判定需要多少次循环
    for (int i = 0; i < maxLength; i++) {
        int[] bubbleLength = new int[10];   // 桶的放的数据的量
        // 将数据根据个位、十位、百位依次放入桶中
        for (int j = 0; j < arr.length; j++) {
            int size = arr[j] / (int)Math.pow(10, i) % 10;
            bubble[size][bubbleLength[size]] = arr[j];
            bubbleLength[size] ++;
        }
        //依次将数据取出，并放入到原来的数组中
        int index = 0;
        for(int j=0; j<bubble.length; j++){
            if(bubbleLength[j] > 0){
                for(int k=0; k<bubbleLength[j]; k++){
                    arr[index++] = bubble[j][k];
                }
            }
        }
    }
    return arr;
}

快速排序

基本思想：通过一次排序将要排序的数据分割成独立的两个部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后按照这种方法对这两个部分数据分布进行快速排序，整个排序部分可以使用递归进行，以此达到整个数据变成有序序列。

思路分析：

1. 假设数组为arr，左侧为left，右侧为right，设置选择的初始位置为
2. 从左侧开始查找，找到大于等于mid的值为止，从右侧也开始查找，直到找到小于等于mid的值
3. 直到找到l<r的位置，然后递归进行快速排序。

/**
     * 快速排序
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
public static int[] quickSort(int[] arr, int left, int right) {
    if (left >= right) return null;
    // 如果数组中left与right相等或者left大于right，则跳出程序
    int l = left;
    int r = right;
    int mid = arr[(l + r) / 2];
    int temp = 0;
    while (l < r) {
        while (l < r && arr[l] < mid) {
            l++;
        }
        while (r > l && arr[r] > mid) {
            r--;
        }
        if (l >= r) {
            break;
        }
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        if (arr[l] == mid){
            r--;
        }
        if (arr[r] == mid) {
            l++;
        }
    }
    quickSort(arr, left, l - 1);
    quickSort(arr, r + 1, right);
    return arr;
}

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
1. 计数排序的特征当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。
算法的步骤如下：

• （1）找出待排序的数组中最大和最小的元素
• （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
• （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
• （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

  2. 动图演示

  

public class CountingSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        int maxValue = getMaxValue(arr);
        return countingSort(arr, maxValue);
    }
    private int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];
        for (int value : arr) {
            bucket[value]++;
        }
        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }
    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }
}

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

1. 什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢

当输入的数据被分配到了同一个桶中。

3. 示意图

元素分布在桶中：

然后，元素在每个桶中排序：

public class BucketSort implements IArraySort {
    private static final InsertSort insertSort = new InsertSort();
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        return bucketSort(arr, 5);
    }
    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }
        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }
        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];
        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }
        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }
        return arr;
    }
    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}