值得收藏的＜计数排序＞讲解

偏执的太偏执、 2022-09-12 09:49 157阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

## **计数排序（Counting Sort）** ##

> 计数排序于1954年由Harold H. Seward提出，适合**对一定范围内**的**整数进行**排序

1.  冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序，平均时间复杂度目前最低是 `O(nlogn)`
2.  计数排序、桶排序、基数排序，都不是**基于比较的排序**，它们是典型的用**空间换时间**，在某些时候，平均时间复杂度可以比 `O nlogn` 更低
3.  **计数排序的核心思想**：统计每个整数在序列中**出现的次数**，进而推导出每个整数在**有序序列**中的索引

![计数排序][75e4847babb43192ee372156b62f43b8.gif]

#### **计数排序 – 最简单的实现** ####

1.  统计数组数据次数

![image-20210906162700929][]

1.  最后输出到原来数组中覆盖就可以了

![image-20210906162858072][]

1.  代码实现：找到最大值，开辟空间，统计次数，根据次数进行排序

package com.chengyunzhi;
    
    
    public class 计数排序 { 
    	static int[] array= { 7,3,5,8,6,7,4,5};
    	public static void main(String args[]) { 
    		sort();
    	}
    	public static void sort() { 
    // 找出最大值
    		int max=0;
    		for(int arr:array) { 
    			max=Math.max(max, arr);
    		}//O(n)
    // 开辟内存空间,存每个整数出现的次数
    		int[] counts=new int[max+1];
    // 统计出现次数
    		for(int arr:array) { 
    			counts[arr]++;
    		}//O(n)
    // 根据次数进行排序
    		int index=0;
    		for(int i=0;i<counts.length;i++) { 
    			while(counts[i]-->0) { 
    				array[index++]=i;
    			}
    		}//O(n)
    		for(int i=0;i<array.length;i++) { 
    			System.out.print(array[i]+"_");
    		}
    	}
    }

输出: 3\_4\_5\_5\_6\_7\_7\_8\_

> 时间复杂度O(n)这个版本的实现存在以下问题，无法对负整数进行排序，极其浪费内存空间，是个不稳定的排序

#### **计数排序 – 改进思路** ####

1.  在\{7,3,5,8,6,7,4,5\}找到最大最小值,依次存入次数,就可以节省空间，并且可以对负整数进行排序

![image-20210906190347274][]

1.  每个次数累加上其前面的**所有次数**得到的就是**元素**在**有序序列**中的**位置信息**，比如元素8的次数是8=7+1，说明他前面还有七个，八的索引就是7.
    
    ![image-20210906190526661][]
    
    > 通过上面的方法知道下标就可以依次排序了
2.  每个元素累加上其前面的所有元素得到的就是元素在有序序列中的位置信息

![image-20210906190840627][]

1.  每个元素累加上其前面的所有元素得到的就是元素在有序序列中的位置信息

![image-20210906190948382][]

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[75e4847babb43192ee372156b62f43b8.gif]: /images/20220828/81f8cec31dec428badfc19173b8d8104.png
[image-20210906162700929]: /images/20220828/2e4bb949ca5b48cda430de7e85e7c3d8.png
[image-20210906162858072]: /images/20220828/16b6e46a8039414691f2f2e3e21d2fa9.png
[image-20210906190347274]: /images/20220828/32ddbf47d6e8471aaf4605a19a2ab3e2.png
[image-20210906190526661]: /images/20220828/533896278e1d4616b11730066a3bb6a2.png
[image-20210906190840627]: /images/20220828/98d829b4748f43448bc79843b4aedb56.png
[image-20210906190948382]: /images/20220828/49f4a34ee5e54ba1a61484be9a44a980.png