【DS】9.常用排序算法大总结【下】！！

本是古典何须时尚 2024-04-01 09:44 103阅读 0赞

> 由于我很少见非比较类排序算法桶排序和基数排序的考察，所以我这里重点分析计数排序，另外两种以分析思想为主，参考中有代码，了解即可。
> 
> 如若后序使用的多了，再进行补充.

#### 文章目录 ####

*   *  一、计数排序（CountSort）
     *   *   *  思路分析
             *  动图演示
             *  代码实现
             *  算法效率分析
             *  使用前提及应用场景
     *  二、桶排序（BucketSort）
     *   *   *  示例分析（含详细步骤拆分图）
             *  算法效率分析
     *  三、基数排序（RadixSort）
     *   *   *  示例分析（含详细步骤拆分图及动图演示）
             *  补充：元素是负数时的处理思路
     *  四、三种非比较类排序算法的异同及内部联系
     *  五、再次总结
     *   *  算法优劣对比【优化后】
     *  参考

### 一、计数排序（CountSort） ###

##### 思路分析 #####

①找出待排序数组中的最大和最小的元素②开辟max-min+1大小的计数数组③统计原数组中每个值为i的元素出现的次数，存入计数数组countArr的第i项④遍历计数数组，反向填充原数组。【具体填充方法：例如计数数组countArr\[99\]=5，放进原数组里一次，countArr\[99\]就减减】

##### 动图演示 #####

![在这里插入图片描述][609507c367d7470795a33d9b5d92e224.gif_pic_center]

##### 代码实现 #####

public static void countSort(int[]array){
        
        //1.遍历数组，找到数组的最大值和最小值——确定计数数组的大小
        int maxVal=array[0];
        int minVal=array[0];
        for (int i = 0; i < array.length; i++) {
        
            if(array[i]>maxVal){
        
                maxVal=array[i];
            }
            if(array[i]<minVal){
        
                minVal=array[i];
            }
        }
        //2.确定计数数组大小
        int[]countArr=new int[maxVal-minVal+1];
        //3.遍历元素，开始计数
        for (int i = 0; i < array.length; i++) {
        
            countArr[array[i]-minVal]++;
        }
        //4.遍历计数数组,将值再次赋给原来的数组
        int k=0;
        for (int i = 0; i < countArr.length; i++) {
        
            while(countArr[i]>0){
        
                array[k++]=i+minVal;
                countArr[i]--;
            }
        }
    }

##### 算法效率分析 #####

> 时间复杂度：O(n+范围)【主要体现在最后一个循环上边】
> 
> 空间复杂度：O(范围)
> 
> 稳定性：不稳定

##### 使用前提及应用场景 #####

> 使用前提：输入的数据必须是有确定范围的整数
> 
> 应用场景：一般是集中分布一定范围内的整形数据的统计

### 二、桶排序（BucketSort） ###

##### 示例分析（含详细步骤拆分图） #####

其实桶排序没有确切的定义，思想也不好描述，如果非要说核心思想，那就是“划分多个范围相同的区间，每个子区间自排序，最后合并”。

但是只放这一句话可能不好理解，下边我们举个例子。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y6DX3B4t-1666494072982)(F:\\typora插图\\image-20221023092807300.png)\]][img-y6DX3B4t-1666494072982_F_typora_image-20221023092807300.png]

##### 算法效率分析 #####

> 时间复杂度：O(n+C)
> 
> 空间复杂度：O(n（临时数组）+桶的个数)【常数个】
> 
> 稳定性：不确定，取决于桶内部排序使用的算法

### 三、基数排序（RadixSort） ###

##### 示例分析（含详细步骤拆分图及动图演示） #####

基本原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

还是和上边一样，我们来举个例子。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NuASv07F-1666494072983)(F:\\typora插图\\image-20221023095745476.png)\]][img-NuASv07F-1666494072983_F_typora_image-20221023095745476.png]

![在这里插入图片描述][1e0ec64b919943feaa4e756f3a559027.gif_pic_center]

> ①个位数是什么放到对应的桶②按顺序拿出来，再次按照十位数拿③按顺序拿出来，按照百位放④如果最大值只有3位数，就结束了
> 
> 个十百位的优先级的应用

##### 补充：元素是负数时的处理思路 #####

有负数时处理思路：先判断有无负数 有则找到最小值 数组所有数据都减去该值 也就是数组最小值会变为0 接下来按正整数排序 最后数组所有数据加上原最小数 变为原有数据值】

### 四、三种非比较类排序算法的异同及内部联系 ###

1.  桶排序和计数排序都需要找最大最小值，基数排序只需要找最大值
2.  计数排序的数学原理是鸽巢原理，因此也叫作鸽巢排序。
3.  基数排序是桶排序的扩展，也就是说基数排序也是桶排序。
4.  基数排序使用的是序列的元素的位数，桶排序和计数排序使用的是序列元素的范围。
5.  三者一般用于整数的排序。

### 五、再次总结 ###

#### 算法优劣对比【优化后】 ####

<table> 
 <thead> 
  <tr> 
   <th>排序算法</th> 
   <th>最坏时间复杂度</th> 
   <th>最好时间复杂度</th> 
   <th>平均时间复杂度</th> 
   <th>空间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(n^2)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(n * logn)</td> 
   <td>O(n * logn)</td> 
   <td>O(n * logn)</td> 
   <td>O(logn)</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(n * log(n))</td> 
   <td>O(n * log(n))</td> 
   <td>O(n * log(n))</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>-----</td> 
   <td>-----</td> 
   <td>O(n^1.3)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>计数排序</td> 
   <td>O(n+范围)</td> 
   <td>-----</td> 
   <td>-----</td> 
   <td>O(范围)</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>-----</td> 
   <td>-----</td> 
   <td>O(n)</td> 
   <td>O(n+范围)</td> 
  </tr> 
  <tr> 
   <td>桶排序</td> 
   <td>-----</td> 
   <td>-----</td> 
   <td>O(n)</td> 
   <td>O（n+范围）</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][352dd5f4142d4d66867b775c72d36b63.png_pic_center]

### 参考 ###

> [基数排序 java代码][java]
> 
> [桶排序参考][Link 1]
> 
> [参考][Link 2]

[609507c367d7470795a33d9b5d92e224.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c59fa544fa144524be9fdac848fcef06.gif
[img-y6DX3B4t-1666494072982_F_typora_image-20221023092807300.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/273588f4ee9e494c869a2467db31cb58.png
[img-NuASv07F-1666494072983_F_typora_image-20221023095745476.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5f1eee72141941ddacbd383bef874e27.png
[1e0ec64b919943feaa4e756f3a559027.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/726ae36a2b1c4330b5e69af03a888097.gif
[352dd5f4142d4d66867b775c72d36b63.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4be8bb4a86ce4b09a2734dca8701cfe2.png
[java]: https://www.runoob.com/w3cnote/radix-sort.html
[Link 1]: http://t.csdn.cn/ihZOS
[Link 2]: https://www.csdn.net/tags/MtTagg2sMjU5OTQtYmxvZwO0O0OO0O0O.html