🎉🎉🎉写在前面：
博主主页：🌹🌹🌹戳一戳，欢迎大佬指点！
博主秋秋：QQ：1477649017 欢迎志同道合的朋友一起加油喔💪
目标梦想：进大厂，立志成为一个牛掰的Java程序猿，虽然现在还是一个小菜鸟嘿嘿
-----------------------------谢谢你这么帅气美丽还给我点赞！比个心-----------------------------
排序
一，排序的概念和引入
1，概念
排序：顾名思义，就是把一串数据按照升序或者降序的方式进行排列。
稳定性：当一组数组中有多个相同的元素的时候，如果你排序之后，这些相同的元素之间的前后顺序如果保持没变的话，那就是稳定的，否则就是不稳定的。
内部排序：所有的数据都是在内存上进行排序。
外部排序：数据元素太多，不能在内存上进行数据的移动，只能在磁盘上进行操作。
二，常见排序算法总览
三，算法实现
3.1，插入排序
基本思想：将待排序的数据按照大小逐个插入到一个已经有序的序列中，直至插入完成，使得整个序列依然有序。
3.1.1，直接插入排序
对于直接插入排序而言，就像是一个摸牌的过程，刚开始手中的第一张牌是有序的，然后后面每模一张牌，都要和前面的所有牌进行比较，然后找到一个合适的位置将其插入。这个过程其实就是直接插入排序，只不过现在考虑的是数组中的数据。
【代码实现：】
publicvoidinserSort(int[] array){for(int i =1;i < array.length;i++){int tmp = array[i];//相当于把每次摸到的牌进行保存int j =0;for(j = i -1;j >=0;j--){if(array[j]> tmp){//这个地方如果给到等号了，那就是不稳定的
array[j+1]= array[j];}else{break;}}//跳出循环说明已经不需要再移动元素了
array[j +1]= tmp;}}
【图解：】
【特性总结：】
1，时间复杂度：O(n^2)
对于插入排序而言，最坏的情况就是这个数组是一个倒序的数组，这样每一次的比较都要把tmp中保存的拿到最前面来。当i =1时，内层循环需要执行1次，i = 2内层循环需要执行2次…，当i = n-1时内层循环需要执行n - 1次，这样 1 + 2 + 3 … + n-1 = n(n-1)/2。所以时间复杂度就是O(n^2)。最好的情况就是这个数组本身就是有序的，就只需要遍历一遍数组，时间复杂度就是O(n)。
2，空间复杂度：O(1)
3，稳定性：稳定
在排序过程中，即使遇到与tmp相等的元素，但是不会执行[j+1] = [j]，所以不会改变前后的顺序，所以是稳定的。但这里提醒一个点，就是你把判断的条件改成 array[j] >=tmp后，他就是不稳定的。但是对于直接插入排序，它是一个稳定的排序。一个稳定的排序你可以人为的代码实现为不稳定的，但是不稳定的不可能实现为稳定的。
4，直接插入排序适用于那些基本有序的数据，数据越有序，算法的效率越高。
3.1.2，希尔排序
希尔排序又称为缩小增量算法。它的基本思想就是先将一组数据进行分组，然后组内进行排序，这样的操作会重复进行，每次的分组树，也即是所谓的增量会每次减小，直至最后为1，进行整个的一次排序。
其实希尔排序你可以看成是优化了的直接插入排序，它的每次分组，每一次组内排序，都会使得全部的数据越来越趋于有序。当分组数等于1时，那就是一次完整的直接插入排序，但是因为趋于有序，所以效率会很高。
【代码实现：】
publicvoidshellSort(int[] array,int gap){for(int i = gap;i < array.length;i++){int tmp = array[i];//相当于把每次摸到的牌进行保存int j =0;for(j = i -gap;j >=0;j -= gap){if(array[j]> tmp){//这个地方如果给到等号了，那就是不稳定的
array[j+gap]= array[j];}else{break;}}//跳出循环说明已经不需要再移动元素了
array[j + gap]= tmp;}}classTestSort{publicstaticvoidmain(String[] args){int[] array1 =newint[]{9,7,4,3,8,2,1,6,10,5};int gap =5;while(gap >1){Sort.shellSort(array1,gap);
gap /=2;//也就是5组 2组 1组}Sort.shellSort(array1,1);//gap = 1单独再排序一次System.out.println(Arrays.toString(array1));}}
对于gap = 2的时候，这个时候不是把一组遍历调整完了再跳到下一组，而是两个组交替着来，所以i还是++，只不过要注意j -= gap。
【图示：】
可能看到上面的分组方式，大家可能会奇怪为什么要跳着分组，其实这是为了让数据与数据之间的跨度更大，这样就可以让较大的数据尽可能的往后面交换了，当gap > 1的时候都是预排序，一切的操作都是为了让数据更加的趋于有序，为了那最后一次的直接插入排序打好根基，这样最后效率就会大大提高。
【特性总结：】
1，时间复杂度：因为gap的取值方式有很多种，所以对于希尔排序来说，它的时间复杂度是不确定的。但是根据科学家大量的实验证明，我们可以认为其时间复杂度在O(n^1.3) ~ O(n^1.5)。
2，空间复杂度：O(1)。
3，稳定性：不稳定。因为是跳着分组，调整过程中肯定会出现交换后次序与之前不一致的情况。
3.2，选择排序
3.2.1，直接选择排序
直接选择排序就是从[i] ~ [n-1] （n是数组长度）中选择出一个最大或者最小的数据放到i下标位置来，然后一次交换完i++，直至把整个数组遍历完成。
【代码实现：】
publicstaticvoidselectSort(int[] array){for(int i =0;i < array.length;i++){int minIndex = i;for(int j = i+1;j < array.length;j++){if(array[j]< array[minIndex]){
minIndex = j;}}//进行值的交换swap(array,i,minIndex);}}privatestaticvoidswap(int[] array,int index1,int index2){int tmp = array[index1];
array[index1]= array[index2];
array[index2]= tmp;}
【特性总结：】
1，时间复杂度：O(n^2)
对于直接选择排序来说，当i = 0的时候内层循环要比较 n - 1次，当 i = array.length - 2的时候要比较1次，当i = array.length - 1的时候比较0次，之后循环结束，所以总执行次数 1 + 2+ 3 + 4
… + n-1 = n(n-1)/2，所以时间复杂度就是O(n^2)。
2，空间复杂度：O(1)
3，稳定性：不稳定。交换可能会改变原有次序。
4，对于直接选择排序而言，他对于数据不敏感，无论原数据是否已经有序，它都会去比较完，所以时间复杂度都是O(n^2)。
【直接选择排序优化：】
对于上面的直接选择排序，时间复杂度比较高，既然我们可以每次选择一个最小的放到前面来，那我们是不是同时选一个最大的放到后面，这样就可以提高效率。
publicstaticvoidselectSort2(int[] array){int left =0;int right = array.length -1;while(left < right){int minIndex = left;int maxIndex = left;//初始都在left处for(int i = left +1;i <= right;i++){if(array[i]> array[maxIndex]){
maxIndex = i;}if(array[i]< array[minIndex]){
minIndex = i;}}//每一轮都会找到一个最大值，最小值swap(array,left,minIndex);if(maxIndex == left){//防止最大值在left处，前面交换了直接把最大值移走了
maxIndex = minIndex;}swap(array,right,maxIndex);
left++;
right--;}}privatestaticvoidswap(int[] array,int index1,int index2){int tmp = array[index1];
array[index1]= array[index2];
array[index2]= tmp;}
3.2.2，堆排序
堆排序是利用堆这种数据结构构建的一种排序算法。如果是升序排序，则需要构建一个大根堆，这样堆顶元素总是最大的，然后将其与最后一个元素交换，然后进行向下调整，调整不包括这个换下去的堆顶元素，这样重复操作，直至整个数组元素都被调整完了，最后形成的就是一个升序的序列。同理，如果是降序，那么构造的就是一个小根堆。
【代码实现：】
publicstaticvoidcreateBigHeap(int[] array){//创建一个大根堆for(int parent =(array.length-1-1)/2;parent >=0;parent--){shiftDown(array,parent, array.length);}}publicstaticvoidshiftDown(int[] array,int parent,int len){//向下调整算法int child = parent*2+1;while(child < len){//起码有左孩子if(child +1< len && array[child]< array[child +1]){
child++;//找到较大的孩子的下标}if(array[child]> array[parent]){swap(array,child,parent);//进行交换
parent = child;
child =2*parent +1;}else{break;}}}publicstaticvoidheapSort(int[] array){//这是堆排序主体，上面是所需的准备操作
array =Arrays.copyOf(array,array.length);//拷贝一份createBigHeap(array);//创建大根堆int end = array.length -1;while(end >0){swap(array,0,end);shiftDown(array,0,end);
end--;}
【特性总结：】
1，时间复杂度：O(n*logn)
创建大根堆是O(n)，while()循环也是O(n)，只不过内部还套了一个shiftDown()是logn，所以时间复杂度就是O(n*logn)。
2，空间复杂度：O(1)
3，稳定性：不稳定
在数据量逐渐增大的时候，希尔排序的效率会略高于我们的堆排序。
3.3，交换排序
基本思想：交换排序，顾名思义，就是将元素进行比较，然后按照一定的规则交换，达到的效果就是较大的元素往序列的尾部移动，小的元素往头部移动。(当然也可以实现为降序的效果)
3.3.1，冒泡排序
冒泡排序相信大家是熟悉的不能再熟悉了，这里主要说一下它的两个循环的边界，对于外层循环，控制排序的趟数，N个数据需要排序N-1次，内部循环控制每一趟的比较次数，第一趟需要比较N-1次，第二趟需要比较N-2次，因为每一趟都会找出一个最大的放到后面，后面是有序的，所以比较次数肯定是越来越少的。
【代码实现：】
publicstaticvoidbubbleSort(int[] array){for(int i =0;i < array.length -1;i++){boolean flg =true;//假设有序了for(int j =0;j < array.length -1-i;j++){//-i是因为后面已经放过去的元素就无需比较了if(array[j]> array[j+1]){swap(array,j,j+1);
flg =false;}}if(flg ==true){return;}}}
【特性总结：】
1，时间复杂度：O(n^2)
比较次数也是一个等差数列，1 + 2 + 3 + 4 + … + n-1 = n(n-1)/2。当然经过优化之后，数据有序的情况时间复杂度可以降低到O(n)。
2，空间复杂度：O(1)
3，稳定性：稳定的，当然你可以实现为不稳定，多加一个等号的事。
3.3.2，快速排序
快速排序是由Hoare于1962提出的一种二叉树结构的交换排序算法。它的基本思想就是找到一个基准值，大于基准值的元素往后交换，小于基准值的元素往前交换，最终达到的效果就是基准值的左边全是小于它的元素，右边原始大于它的元素。然后左右两边，又按照相同的方法进行重复操作，最后将整个序列有序化。
看到上面图示的这个过程，可以发现，我们每次分割的过程就形似一棵二叉树，所以快速排顺序的实现也需要依靠递归去操作。
那么，常见的按照基准值进行划分的方法有以下几种：
【1，Hoare版】
privatestaticintpartion(int[] array,int start,int end){//在[start,right]去寻找下一个分割点int keyIndex = start;//记录下最初start的位置int key = array[start];//每次的基准值等于左边1第一个元素//并进行元素的交换while(start < end){//先走右边while(start < end && array[end]>= key){//这是一个单独的循环，如果是有序的，那么end就会一直减减到-1，所以start<end
end--;}//走左边while(start < end && array[start]<= key){
start++;}swap(array,start,end);}swap(array,keyIndex,start);//把最后相遇点的元素与基准值交换return start;//返回我们的相遇点，也就是下一次的分割点下标}privatestaticvoidquick(int[] array,int left,int right){//在[left,right]去进行分割if(left >= right){return;}int divIndex =partion(array,left,right);quick(array,left,divIndex -1);//递归对左半部分，右半部分进行分割quick(array,divIndex +1,right);}publicstaticvoidquickSort(int[] array){quick(array,0, array.length-1);}
【细节分析：】
1，为什么先走右边而不是左边？
2，为什么比较大小的时候都是 array[end] >= key ，array[start] <= key ，需要加上等号？
因为如果第一个元素和最后一个元素相等，你会发现end减减不了，start也加加不了，最终循环会陷入死循环。
3，为什么递归的结束条件是left >= right?
【Hoare法特性总结：】
1，时间复杂度：理想情况下O(n*logn)，最坏是O(n^2)。
假设是理想情况，每次分割都是二分，所以对于每一层递归来说，我们可以看成是一个整体，，第一层要对比n次找到分割点，第二层左半边是n/2，右半边是n/2，整体也是n，继续往下面的递归也可以这么看，所以每层递归执行次数是n，递归的深度是树的高度logn，所以时间复杂度就是n*logn。
但是实际上不会有这么理想的情况，每次都是二分，最坏的情况就是数据刚好有序或者是逆序，这样我们的分割就只有了右子树或者左子树，每层分割都是一样，所以第一层就是n-1，第二层就是n-2，整体算出来就是一个等差数列，就是O(n^2)。
2，空间复杂度：最好情况是O(logn)，最坏情况是O(n)
对于递归的函数来说，每次一递归都要为函数开辟栈帧，所以在最好的情况下都是二分，我们递归的次数就是树的高度，左边递归完了销毁后再去递归右边。但是在最坏情况下，数据有序或者逆序，这个时候树就只有右子树或者左子树，数的高度就是n，空间复杂度就是O(n)，当我们的n越大，递归的深度就越深，栈溢出的风险就越大。
3，使用场景：快速排序适用于排序无序的数据，排序有序的数据，如果数据量很大，递归的深度机会很深，容易造成栈溢出。并且如果是有序的数据，采用直接插入排序或者希尔排序才是第一选择。但是这确实快速排序存在的问题，当然后面也会有优化的办法。
【挖坑法：】
privatestaticintpartion1(int[] array,int start,int end){//在[start,right]去寻找下一个分割点int key = array[start];//拿出左边元素形成一个坑位//并进行元素的交换while(start < end){//先走右边while(start < end && array[end]>= key){
end--;}
array[start]= array[end];//后面找到了小于基准值的元素就换到前面来把坑填上，并且后面end处形成新的坑位//走左边while(start < end && array[start]<= key){
start++;}
array[end]= array[start];}
array[start]= key;//最后相遇了把key放到这个坑位return start;//返回我们的相遇点，也就是下一次的分割点下标}privatestaticvoidquick(int[] array,int left,int right){//在[left,right]去进行分割if(left >= right){return;}int divIndex =partion1(array,left,right);quick(array,left,divIndex -1);//递归对左半部分，右半部分进行分割quick(array,divIndex +1,right);}publicstaticvoidquickSort(int[] array){
array =Arrays.copyOf(array,array.length);//拷贝一份quick(array,0, array.length-1);}
我们每用一个元素去填坑后，这个元素的位置就会形成一个新的坑位。最终left,right相遇处也是一个坑位，这个地方是用来放我们的key值的。
【前后指针法：】
privatestaticintpartion2(int[] array,int start,int end){//在[start,right]去寻找下一个分割点int key = array[start];int prev = start;int cur = start+1;while(cur <= end){if(array[cur]< array[start]&& array[++prev]!= array[cur]){swap(array,prev,cur);}
cur++;}swap(array,start,prev);return prev;}privatestaticvoidquick(int[] array,int left,int right){//在[left,right]去进行分割if(left >= right){return;}int divIndex =partion2(array,left,right);quick(array,left,divIndex -1);//递归对左半部分，右半部分进行分割quick(array,divIndex +1,right);}publicstaticvoidquickSort(int[] array){
array =Arrays.copyOf(array,array.length);//拷贝一份quick(array,0, array.length-1);}
【快速排序优化：】
上面介绍了三种找基准进行分割的方式，但是实际上他们有一个共同的通病，因为都是以左边left下标的元素作为基准值，所以一旦整个序列元素是有序或者逆序的时候，就会出现时间复杂度是O(n^2)，如果递归过深会出现栈溢出，所以为了解决这一问题，我们进行了以下优化。
【1，三数取中】
三数取中的方法就是在我们的[left,right]中计算出一个中间下标，然后比较三个数的值，将中间大小的那个元素作为新的基准值，换到left处。
privatestaticintgetMidNum(int[] array,int left,int right){int mid =(left + right)>>1;if(array[left]< array[right]){if(array[mid]< array[left]){return left;}elseif(array[mid]> array[right]){return right;}else{return mid;}}else{if(array[mid]> array[left]){return left;}elseif(array[mid]< array[right]){return right;}else{return mid;}}}privatestaticvoidquick(int[] array,int left,int right){//在[left,right]去进行分割if(left >= right){return;}int midIndex =getMidNum(array,left,right);//找寻到中间大小元素的下标swap(array,left,midIndex);//把这个元素与left下标处的元素交换int divIndex =partion2(array,left,right);quick(array,left,divIndex -1);//递归对左半部分，右半部分进行分割quick(array,divIndex +1,right);}publicstaticvoidquickSort(int[] array){
array =Arrays.copyOf(array,array.length);//拷贝一份quick(array,0, array.length-1);}
【2，递归到小区间，使用直接插入排序：】
在为我们的递归的过程中，整个序列肯定是越来越趋于有序的，所以等到了一定的小区间之内后，选用直接插入排序的效率会高一些，并且也减少了我们递归的深度与次数。
privatestaticintgetMidNum(int[] array,int left,int right){int mid =(left + right)>>1;if(array[left]< array[right]){if(array[mid]< array[left]){return left;}elseif(array[mid]> array[right]){return right;}else{return mid;}}else{if(array[mid]> array[left]){return left;}elseif(array[mid]< array[right]){return right;}else{return mid;}}}publicstaticvoidinserSort2(int[] array,int left,int right){//区间版的直接插入排序for(int i = left +1;i <= right;i++){//right是要取到的int tmp = array[i];int j =0;for(j = i -1;j >= left;j--){if(array[j]> tmp){
array[j+1]= array[j];}else{break;}}
array[j +1]= tmp;}}privatestaticvoidquick(int[] array,int left,int right){//在[left,right]去进行分割if(left >= right){return;}if(right - left +1<=7){//区间内结点数小于规定值后选取直接插入排序inserSort2(array,left,right);return;}int midIndex =getMidNum(array,left,right);//找寻到中间大小元素的下标swap(array,left,midIndex);//把这个元素与left下标处的元素交换int divIndex =partion2(array,left,right);quick(array,left,divIndex -1);//递归对左半部分，右半部分进行分割quick(array,divIndex +1,right);}publicstaticvoidquickSort(int[] array){
array =Arrays.copyOf(array,array.length);//拷贝一份quick(array,0, array.length-1);}
【非递归实现快速排序：】
publicstaticvoidquickSort2(int[] array){Stack<Integer> stack =newStack<>();//利用栈来实现非递归int left =0;int right = array.length -1;int divIndex =partion1(array,left,right);//分割第一次，找到第一个分割点if(divIndex > left +1){//分割点左边至少有两个元素才把两个边界入栈
stack.push(left);
stack.push(divIndex-1);}if(divIndex < right -1){//分割点右边至少有两个元素才把两个边界入栈
stack.push(divIndex +1);
stack.push(right);}//现在栈中存放的就是分割点两边的两个区间的边界while(!stack.empty()){
right = stack.pop();//先弹出右边界值
left = stack.pop();
divIndex =partion1(array,left,right);//在这个新区间再去分割if(divIndex > left +1){//分割点左边至少有两个元素才把两个边界入栈
stack.push(left);
stack.push(divIndex-1);}if(divIndex < right -1){//分割点右边至少有两个元素才把两个边界入栈
stack.push(divIndex +1);
stack.push(right);}}}
对于非递归，那我们肯定是要借助栈，队列类似的数结构，利用循环的思想来处理整个数据。这里的栈主要是用来存储我们的边界值。
【快速排序总结：】
对于快速排序来说，它的特性主要就是快，但这个特性一般是基于我们的数无序的情况下，这也是它的使用场景，这个时候它的时间复杂度是O(n*logn)。但是当我们的数据有序或者逆序时，这个时候我们的第一选择肯定是直接插入排序或者希尔排序，而不应该是快速排序。这种时候对于快速排序而言，其时间复杂度达到了O(n^2)，并且如果n很大，很容易递归深度过深而造成栈溢出。所以为了解决这一点，就有了三数取中，小区间使用直接插入排序等的解决办法，其针对点就是递归深度过深以及次数过多的问题。另外，快速排序的空间复杂度最好情况是O(logn)，最坏是O(n)。
3.4，归并排序
privatestaticvoidmergeFunc(int[] array,int left,int right){if(left >= right){return;//大于是因为可能分不出子树的情况}int mid =(left + right)/2;//1,分解左边mergeFunc(array,left,mid);//2,分解右边mergeFunc(array,mid+1,right);//3,进行合并merge(array,left,right,mid);}privatestaticvoidmerge(int[] array,int start,int end,int midIndex){//首先得有一个临时的数组int[] tmp =newint[end-start+1];int k =0;//记录这个数组的下标int s1 = start;int s2 = midIndex +1;while(s1 <= midIndex && s2 <= end){//合并的前提是两个段都有数据if(array[s1]> array[s2]){
tmp[k++]= array[s2++];}else{
tmp[k++]= array[s1++];}}//有可能两个段中有一个先拿完，那么剩下的就是全部另一个段中的元素了while(s1 <= midIndex){
tmp[k++]= array[s1++];}while(s2 <= end){
tmp[k++]= array[s2++];}//现在tmp中是排序合并好了的数组，要拷贝到原来的array中for(int i =0;i < k;i++){
array[i + start]= tmp[i];}}publicstaticvoidmergeSort(int[] array){
array =Arrays.copyOf(array,array.length);//拷贝一份mergeFunc(array,0,array.length-1);}
对于归并排序而言，我们先需要把数据先均分到一个个点上，然后再进行合并，合并的时候进行排序，每合并完成一部分，都会把它拷贝到array中去。这里需要提醒一点的是我们的array[i + start] = tmp[i] 语句前面加上了一个start，因为我们是我们每次拷贝不可能都是从0下标开始放的，对于每一个整段它都有自己的start下标，这个下标在array中对应有一个位置，所以我们需要是加上一个start。
【特性总结：】
1，时间复杂度：O(n*logn)
对于归并排序而言，它是严格的均分，所以不会有像快排那样的情况，都只在一边。对于每一层的归并，我们需要比较排序的数据都是n个，树的高度可以是logn,所以时间复杂度严格的是O(n*logn)。
2，空间复杂度：O(n)
因为我们在归并的过程中，每次都是需要一个中间数组的，所以是O(n）。
3，稳定性：稳定的排序。
【归并排序非递归实现：】
publicstaticvoidmergeSort2(int[] array){int gap =1;//每组数据个数while(gap < array.length){for(int i =0;i < array.length-1;i +=2*gap){// i += 2*gap，两两一合并，跳到下一合并处int s1 = i;//能进循环i就不越界，s1不会越界int e1 = s1 + gap -1;if(e1 >= array.length -1){
e1 = array.length -1;}int s2 = e1 +1;if(s2 >= array.length -1){
s2 = array.length -1;}int e2 = s2 + gap -1;if(e2 >= array.length -1){
e2 = array.length -1;}merge(array,s1,e2,e1);}
gap *=2;}}privatestaticvoidmerge(int[] array,int start,int end,int midIndex){//首先得有一个临时的数组int[] tmp =newint[end-start+1];int k =0;//记录这个数组的下标int s1 = start;int s2 = midIndex +1;while(s1 <= midIndex && s2 <= end){//合并的前提是两个段都有数据if(array[s1]> array[s2]){
tmp[k++]= array[s2++];}else{
tmp[k++]= array[s1++];}}//有可能两个段中有一个先拿完，那么剩下的就是全部另一个段中的元素了while(s1 <= midIndex){
tmp[k++]= array[s1++];}while(s2 <= end){
tmp[k++]= array[s2++];}//现在tmp中是排序合并好了的数组，要拷贝到原来的array中for(int i =0;i < k;i++){
array[i + start]= tmp[i];}}
对于非递归的过程，分组之后，都是每两组一和并，变成有序的。其中需要注意的e1,s2,e2都是有可能越界的，所以当其值大于array.length-1的时候，我们都要将其修改为array,.length-1。e1越界说明最后单独剩一个元素，s2,e2越界说明后面没有第二组了，当然随着gap增大，最终绝对会把所有的元素涵盖进去进行一次排序，所以不用担心单独出来的元素或者组无序。
3.5，计数排序(了解思想)
计数排序的基本思想就是统计一个序列里面各个元素的出现次数，然后根据发聩到我们的原数组上。
publicstaticvoidcountSort(int[] array){//先找到数组里面的最大值与最小值int min = array[0];int max = array[0];//假设0下标是最大值最小值for(int i =0;i < array.length;i++){if(array[i]> max){
max = array[i];}if(array[i]< min){
min = array[i];}}//new一个count数组int[] count =newint[max - min +1];for(int i =0;i < array.length;i++){//开始给每一个元素计数int val = array[i];
count[val - min]++;//因为每组数据最小值不一定是0，所以得把最小值减掉，好和数组下标对应}//开始排序int index =0;for(int i =0;i < count.length;i++){while(count[i]!=0){//元素出现几次，就在array数组里面放几次
array[index]= i + min;//恢复到元素值是下标+min
index++;
count[i]--;}}}
对于计数排序而言，其实就是把我们原数组的元素值首先和count数组的下标对应起来，然后count数组的值就是array数组中这个值出现的次数。至于为什么会变得有序，那是因为count数组它的下标是有序的，就相当于把你array数组的元素值也有序化了，然后每也都有自己的出现次数，你去遍历count数组，知道了每个元素出现了几次，再在array里面放几次就行了。
四，特性总结
最后，今天的文章分享比较简单，就到这了，如果大家觉得还不错的话，还请帮忙点点赞咯，十分感谢！🥰🥰🥰
版权归原作者 影子，你陪着我累吗？ 所有， 如有侵权，请联系我们删除。