JavaDS —— 排序

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

就例如上图所示：排序前，红色的5 在黑色的 5 之后，如果在排序后 红色的 5 在黑色的 5 之后就是稳定的，否则就是不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

插入排序

直接插入排序

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。

直接插入排序会让前面的元素有序，然后不断向后遍历将待排序的元素往前插入即可，直到所有的元素排序完成。

算法思想，首先使用一个大循环，从第二个元素开始遍历数组，因为我们设定第一个元素只用一个本身有序，所以从第二个元素开始排列。
然后接着一个小循环，就是从 i - 1 开始向前遍历，也就是从待排序的元素的前一个已排好的元素开始向前遍历，arr[j+1] = arr[j] ，直到找到恰当的位置将待排序的元素放好（arr[j+1] = tmp）

我们要提前将待排列的元素保存起来。

    public static void insertsort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                } else {
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

在 j 循环结束后还需要 array[j+1] = tmp; 是因为可能数组首元素的位置就是待排列的元素的位置，因此我们需要加上这一行代码。

还有 j 的结束条件应该为 j >= 0

---

时间复杂度分析：
i 从 下标 1 开始循环遍历，j 循环执行 1 次
i 从 下标 2 开始循环遍历，j 循环执行 2 次
i 从 下标 3 开始循环遍历，j 循环执行 3 次
… …
i 从 下标 n-1 开始循环遍历，j 循环执行 n-1 次

这是一个等差数列，使用求和公式可得 （1+（n-1））* （n - 1 ) / 2 ，即时间复杂度为 o(n^2)

由于只是使用了一个临时变量的空间，所以空间复杂度为 o(1)

稳定性： 这是一个稳定的排序算法

希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

---

我们以 gap 为增量对数组进行划分，对不同的小组进行直接插入排序，最后增量 一定会为 1 ，直接进行直接插入排序，得到的一定是有序的数据。

    public static void shellsort(int[] array){
        int gap = array.length;
        while(gap > 1) {
            gap /= 2;
            shell(array,gap);
        }
    }

    private static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j-=gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                } else {
                    array[j+gap] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

这里讲解一下这个算法：for (int i = gap; i < array.length; i++) 这个大家应该很好理解，第一个元素当作是有序的，从 gap 开始遍历数组，即使是不同的组别， i ++ 也能进行排序，只是每次对不同组别进行直接插入排序

这里要注意 j + gap ，因为希尔排序是对不同组别进行直接插入排序的，所以我们要找到对应的组别的成员

---

希尔排序的特性总结：
1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很
快。这样整体而言，可以达到优化的效果。
3.希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排
序的时间复杂度都不固定：

《数据结构(c语言版)》— 严蔚敏：

《数据结构-用面向对象方法与c++描述》— 殷人昆：

---

这里我们将希尔排序的时间复杂度记为 n^1.3 到 n^1.5 之间
空间复杂度为 o(1)
希尔排序是不稳定的排序算法

选择排序

直接选择排序

如果是升序排序，首先从第一个元素开始排列，那么就会先从后面的待排序元素中找到最小的，和第一个元素进行交换；降序也是同理。

以升序为例，我们可以先定义一个临时变量，来保存最小数据的下标，直到遍历完成，下标交换即可。

    public static void selectsort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int mixindex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[mixindex]) {
                    mixindex = j;
                }
            }
            swap(array,mixindex,i);
        }
    }
    
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

很明显可以看出这是一个等差数列，所以时间复杂度为 o(n^2)
并且无论数据原本是有序的还是无序的，时间复杂度依旧还是 o(n^2)，所以直接选择排序算法的效率很低，应用面很小，一般我们不使用该算法进行排序
空间复杂度为 o(1)
是不稳定的算法，如下图所示：

---

优化的直接选择排序算法：

我们使用双指针法，在遍历的过程中同时找到最大值和最小值，然后放在数据的两端，这样的算法效率就提高了一半。

我们以 left 为基准，发现 left 自己就是最大值，下标 5 对应的 3 是最小值，开始交换，首先最小值换到 0 下标，然后最大值换到 5 下标，但是要注意了第一次交换的过程中发生了最大值已经换到了 5 下标，所以写代码的时候要注意，如果最大值就是 left 的话，在最小值交换完就要堆此时最大值的下标继续处理。

    public static void selectsort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int minindex = left;
            int maxindex = left;
            for (int i = left + 1; i <= right; i++) {
                if(array[i] < array[minindex]) {
                    minindex = i;
                }
                if(array[i] > array[maxindex]) {
                    maxindex = i;
                }
            }
            swap(array,left,minindex);
            //如果maxindex就是left所对应的数值，那么由于上面left已经和minindex交换了，所以maxindex要发生改变
            if(maxindex == left) {
                maxindex = minindex;
            }
            swap(array,maxindex,right);
            left++;
            right--;
        }
    }

	private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

堆排序

堆排序在上一篇文章中已经提过，如果不了解的，可以阅读javads —— 优先级队列（堆）priorityqueue
这里直接上代码，以升序为例：

    public static void heapsort(int[] array) {
        if(array == null || array.length == 0) {
            return;
        }
        //建立大根堆
        creatheap(array);

        //升序排列
        int end = array.length - 1;
        while(end > 0) {
            swap(array,0,end);
            siftdown(array,0,end);
            end--;
        }
    }

    private static void creatheap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            siftdown(array,parent,array.length);
        }
    }

    private static void siftdown(int[] array, int parent, int size) {
        int child = 2*parent + 1;
        while(child < size) {
            if(child + 1 < size && array[child+1] > array[child]) {
                child++;
            }
            if(array[parent] < array[child]) {
                swap(array,parent,child);
                parent = child;
                child = 2*parent + 1;
            } else {
                break;
            }
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

时间复杂度为 o(n*log2(n))
空间复杂度为 o(1)
不稳定

交换排序

冒泡排序

冒泡排序比较简单，这里就不赘述了，直接上优化过的冒泡排序代码：

    //冒泡排序
    public static void bubblesort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j+1]) {
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
    }

我们讨论冒泡排序的时间复杂度一般从未优化的出发，那么冒泡排序的时间复杂度为 o(n^2)
冒泡排序最好情况下的时间复杂度为o(n)，也就是排列的数据本身就是有序的，但是一般情况下，我们认为冒泡排序的时间复杂度为 o(n^2)

空间复杂度为 o(1)

冒泡排序是稳定的排序算法

快速排序

快速排序是hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

hoare版

首先右指针向前遍历，遇到比 key 大的数值停下，然后左指针开始向后遍历，遇到比 key 小的数值停下，然后开始交换两个指针所对应的数值，直到两个指针相遇，则此轮排序结束，开始递归左边的子序列。

---

重复之前的操作，直到两个下标相遇~~

这里就展示这么多，剩下的序列还是和之前的操作一样，左递归完了就开始右边的递归，直到快速排序完成。

从上面的视频中，我们可以了解为什么快速排序是一种二叉树结构的交换排序算法，将一个数组不断地拆分，就类似一颗二叉树。

---

这里以升序为例：

    public static void quicksort(int[] array) {
        quick(array,0,array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        if(left >= right) {
            return;
        }

        int pivot = partition(array,left,right);

        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        int tmpleft = left;
        while(left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }

            while(left < right && array[left] <= tmp) {
                left++;
            }

            swap(array,left,right);
        }

        swap(array,tmpleft,left);

        return left;
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

---

---

快速排序算法分析

时间复杂度：在最坏的情况下，快速排序递归时是一颗只有右子树或左子树的一颗二叉树，也就是说快速排序排列的数据要么是逆序要么是顺序的情况下就会类似下图的两颗二叉树：

那么此时有n个数据，每次递归双指针需要走 n-2，n - 3 , n - 4 … 可知这是一个等差数列，那么最坏情况下的时间复杂度为o(n^2)

在最好的情况下快速排序的递归应该可以类似一颗满二叉树，树的高度为 log2(n)，每一层双指针大概需要遍历 n 步，最好的情况下的时间复杂度为 o(n*log2(n))

空间复杂度，在最好的情况下为log2(n) 【因为在递归中，先左边递归开辟空间，等左边的递归结束，空间会被回收，然后才会开始右边的递归，所以空间复杂度为二叉树的高度也是递归的深度，而不是二叉树的所有结点！！！】
在最坏的情况下为 o(n)

稳定性：不稳定

挖坑法

我们先将基准值挖走，然后左指针对应的就是一个坑，右指针开始运动，直到遇到比基准值小的数据就将数据覆盖到左指针对应的坑，然后右指针下方局形成一个坑，然后就轮到左指针运动，直到左指针遇到比基准值大数据就会停下，然后将数据覆盖到右指针对应的坑，然后轮到右指针运动，以此类推，最后双指针相遇将基准值覆盖到此就完成了此轮的排序。

下面给大家提供第一轮挖坑法的排序视频，剩下的都是一样的操作，使用递归写代码即可。

    public static void quicksort(int[] array) {
        quick(array,0,array.length - 1);
    }

    public static void quick(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }

        int pivot = partition(array,left,right);

        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    private static int partition(int[] array, int left, int right) {
        int key = array[left];
        while(left < right) {
            while(left < right && array[right] >= key) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= key) {
                left++;
            }
            array[right] = array[left];
        }

        array[left] = key;
        return left;
    }

前后指针法

首先 cur 指针一直都是往前走，现在要思考 prev 什么时候才能往前走
我们先考虑结果，当 prev 走到比 key 大的数值，并且 cur 走到 比 key 小的数值，二者进行交换。
开始时，当 cur 对应的数值小于 key 的时候，prev 也要跟着走，这样可以消除 不符合条件的数值，然后如果 cur 对应的数值大于 key 的话，prev 不需要走，那么这时候prev 前面就是比 key大的数值，这时候要等到cur 运动到比 key 小的数值才能发生交换，cur 还要继续运动，如果有一时刻当 cur 对应的数值小于 key 的时候，prev 就要往前走一步，也就是走到比基准值大的位置，然后进行交换。
本质上，prev 所对应的数值要始终小于 key ，cur 负责遍历完整个数组。
所以最后 prev 所在的位置就是 key 要坐的位置。

    public static void quicksort(int[] array) {
        quick(array,0,array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        if(left >= right) {
            return;
        }

        int pivot = partition(array,left,right);

        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    private static int partition(int[] array, int left, int right) {
        int prev = left;
        int cur = left + 1;
        int key = array[left];

        while(cur <= right) {
            if(array[cur] < key && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }

        swap(array,prev,left);
        return prev;
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

优化

快速排序的缺点就是一旦数据量过大，递归的深度就会越大，开辟的空间也就越大，很有可能会发生栈溢出，所以要想优化快速排序算法，那么我们应该要想办法减少递归的深度，这时候就有了 三数取中法 和 后面的序列采用直接插入法。

三数取中法

原因：从快速排序的空间复杂度中，我们得知最坏的空间复杂度为 o(n)，是因为这是一颗只有一颗子树的二叉树，最好的空间复杂度为 o(log2(n))，这是一颗满二叉树，也就是要想减少递归的深度，就尽量让快速排序呈现的是一颗饱满的二叉树，所以我们取中位数，也就是让数组切分地更加均匀一些。

此外，取基准值除了上述的三数取中法，还有随机数法，也就是随机取一个数据作为基准值，但是我们一般使用三数取中法，毕竟我们直到三数取中法可以尽量地切分数据，而随机数法具有很多不可空因素和偶然性，所以我们不使用随机数法。

这里要注意分情况讨论：
if 当left 的数值大于 right 的数值的时候
剩下的直接 else

    public static void quicksort(int[] array) {
        quick(array,0,array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        if(left >= right) {
            return;
        }

        int pivot = partition(array,left,right);

        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    private static int partition(int[] array, int left, int right) {
        //三数取中法
        getmiddleindex(array,left,right);

        int key = array[left];
        while(left < right) {
            while(left < right && array[right] >= key) {
                right--;
            }
            array[left] = array[right];

            while(left < right && array[left] <= key) {
                left++;
            }
            array[right] = array[left];
        }

        array[left] = key;
        return left;
    }

    private static void getmiddleindex(int[] array, int left, int right) {
        int leftvalue = array[left];
        int rightvalue = array[right];
        int middleindex = (left + right) / 2;
        int middlevalue = array[middleindex];

        if(leftvalue < rightvalue) {
            if(middlevalue > rightvalue) {
                swap(array,left,right);
            } else if(middlevalue < leftvalue) {
                return;
            } else {
                swap(array,left,middleindex);
            }
        } else {
            if(middlevalue < rightvalue) {
                swap(array,left,right);
            } else if(middlevalue > leftvalue) {
                return;
            } else {
                swap(array,left,middleindex);
            }
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

后面的序列采用直接插入法

直接插入排序的有点是越有序的数据就会排地越快，而快速排序是越排序越有序，我们可以将二者结合起来，就是在快速排序切分为比较小量的数组的时候，可以不用递归了，直接使用直接插入排序以此来减少递归开辟的空间。

    public static void quicksort(int[] array) {
        quick(array,0,array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        if(right - left <= 20) {
            insertsort(array,left,right);
            return;
        }

        int pivot = partition(array,left,right);

        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    private static void insertsort(int[] array, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(array[j] > key) {
                    array[j+1] = array[j];
                } else {
                    array[j+1] = key;
                    break;
                }
            }
            array[j+1] = key;
        }
    }

    private static int partition(int[] array, int left, int right) {
        //三数取中法
        getmiddleindex(array,left,right);

        int key = array[left];
        while(left < right) {
            while(left < right && array[right] >= key) {
                right--;
            }
            array[left] = array[right];

            while(left < right && array[left] <= key) {
                left++;
            }
            array[right] = array[left];
        }

        array[left] = key;
        return left;
    }

    private static void getmiddleindex(int[] array, int left, int right) {
        int leftvalue = array[left];
        int rightvalue = array[right];
        int middleindex = (left + right) / 2;
        int middlevalue = array[middleindex];

        if(leftvalue < rightvalue) {
            if(middlevalue > rightvalue) {
                swap(array,left,right);
            } else if(middlevalue < leftvalue) {
                return;
            } else {
                swap(array,left,middleindex);
            }
        } else {
            if(middlevalue < rightvalue) {
                swap(array,left,right);
            } else if(middlevalue > leftvalue) {
                return;
            } else {
                swap(array,left,middleindex);
            }
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

非递归

我们可以使用队列或者栈来保存本来要递归的起点与终点，这样就可以通过队列或者栈来模拟递归的过程，做到非递归。

    public static void quicksort(int[] array) {
        quicknor(array,0,array.length - 1);
    }

    private static void quicknor(int[] array, int left, int right) {
        queue<integer> queue = new linkedlist<>();

        int pivot = partition(array,left,right);
        if(left < pivot-1) {
            queue.offer(left);
            queue.offer(pivot-1);
        }

        if(right > pivot+1) {
            queue.offer(pivot + 1);
            queue.offer(right);
        }

        while(!queue.isempty()) {
            int start = queue.poll();
            int end = queue.poll();
            pivot = partition(array,start,end);

            if(start < pivot-1) {
                queue.offer(start);
                queue.offer(pivot-1);
            }

            if(end > pivot+1) {
                queue.offer(pivot + 1);
                queue.offer(end);
            }
        }
    }

    private static int partition(int[] array, int left, int right) {
        int key = array[left];
        while(left < right) {
            while (left < right && array[right] >= key) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= key) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = key;
        return left;
    }

---

归并排序

归并排序（merge-sort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（divide and
conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使
子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

下面是归并排序的视频：

递归

先分解后合并，在合并里面是两个有序数组的合并，我们需要

    public static void mergesort(int[] array) {
        merge(array,0,array.length-1);
    }

    private static void merge(int[] array, int start, int end) {
        if(start == end) {
            return;
        }

        int mid = (start + end) / 2;

        //分解
        merge(array,start,mid);
        merge(array,mid+1,end);

        //合并
        merge_sort(array,start,mid,end);
    }

    private static void merge_sort(int[] array, int start, int mid, int end) {
        int[] tmp = new int[end - start +1];
        int k = 0;
        int s1 = start;
        int s2 = mid+1;
        int e1 = mid;
        int e2 = end;

        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            } else {
                tmp[k++] = array[s2++];
            }
        }

        while(s1 <= e1) {
            tmp[k++] = array[s1++];
        }

        while(s2 <= e2) {
            tmp[k++] = array[s2++];
        }

        //放回原数组
        for (int i = 0; i < k; i++) {
            array[i+start] = tmp[i];
        }
    }

归并排序算法分析

时间复杂度：递归的深度为 log2(n)，二叉树每层需要 遍历一次数组也就是 n ，则 时间复杂度为 o(n*log2(n))

空间复杂度为 o(n)

稳定性：稳定

非递归

归并排序在空间消耗上很大，那我们能不能使用迭代的方法来实现归并排序呢？以此来减少递归产生的空间的消耗。

我们先来看一下递归的函数主体：

我们通过递归将数组划分，然后再调用我们的合并函数，如果要改成非递归的话，就要思考如何通过迭代划分数据，再将 start,mid 与 end 三个下标值传递给合并函数？

分组在第一层，第二层，第三层的递归中，分别是 4个一组，2个一组，1个一组，我们可以在原数组上进行分割，使用 gap 确定间距：

我们的 gap 是 2 倍 2 倍的增长，gap 从 1 开始，也就是两两分组，因为一个一组本身就是有序的，所以从两个两个为一组开始排序，这样才有意义。

    public static void mergesortnor(int[] array) {
        int gap = 1;
        while(gap < array.length) {
            for (int i = 0; i < array.length; i += gap * 2) {
                int start = i;
                int mid = i+gap-1;
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int end = mid+gap;
                if(end >= array.length) {
                    end = array.length-1;
                }
                merge_sort(array,start,mid,end);
            }
            gap *= 2;
        }
    }


    private static void merge_sort(int[] array, int start, int mid, int end) {
        int[] tmp = new int[end - start +1];
        int k = 0;
        int s1 = start;
        int s2 = mid+1;
        int e1 = mid;
        int e2 = end;

        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            } else {
                tmp[k++] = array[s2++];
            }
        }

        while(s1 <= e1) {
            tmp[k++] = array[s1++];
        }

        while(s2 <= e2) {
            tmp[k++] = array[s2++];
        }

        //放回原数组
        for (int i = 0; i < k; i++) {
            array[i+start] = tmp[i];
        }
    }

七大排序的总结

排序算法	时间复杂度	空间复杂度	稳定性
直接插入排序	o(n^2)	o(1)	稳定
希尔排序	o(n^ 1.3 ~ n^1.5)	o(1)	不稳定
直接选择排序	o(n^2)	o(1)	不稳定
堆排序	o(n * log(n))	o(1)	不稳定
冒泡排序	o(n^2)	o(1)	稳定
快速排序	o(n * log(n))	o(log(n))	不稳定
归并排序	o(n * log(n)	o(n)	稳定

计数排序

计数排序是非基于比较的排序，计数排序是利用下标来表示原数组的具体的数据，而下标对应是数值则是这个数据会出现多少次。

然后我们使用计数数组将数据一一放回原数组，这样原数组就是有序的~~

    public static void countsort(int[] array) {
        //找到最大值和最小值然后开辟的数组
        int min = array[0];
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] < min) {
                min = array[i];
            }
            if(array[i] > max) {
                max = array[i];
            }
        }
        int[] count = new int[max - min + 1];

        //遍历原数组，制作计数数组
        for (int i = 0; i < array.length; i++) {
            count[array[i] - min]++;
        }

        int k = 0;
        //利用计数数组给原数组进行计数排序
        for (int i = 0; i < count.length; i++) {
            while(count[i] != 0) {
                array[k++] = i + min;
                count[i]--;
            }
        }
    }

时间复杂度：o(n + k)

空间复杂度：o(k)

稳定性：稳定

---