【愚公系列】2023年10月 十一大排序算法(八)-计数排序
🏆 作者简介,愚公搬代码
🏆《头衔》:华为云特约编辑,华为云云享专家,华为开发者专家,华为产品云测专家,CSDN博客专家,阿里云专家博主,腾讯云优秀博主,掘金优秀博主,51CTO博客专家等。
🏆《近期荣誉》:2022年CSDN博客之星TOP2,2022年华为云十佳博主等。
🏆《博客内容》:.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏
🚀前言
排序算法是一种将一组数据按照特定的规则进行排列的方法。排序算法通常用于对数据的处理,使得数据能够更容易地被查找、比较和分析。
下面是常见的11种排序算法:
-
冒泡排序(Bubble Sort):比较相邻的元素,如果前面的元素大于后面的元素,就交换这两个元素的位置。时间复杂度为O(n^2)。
-
选择排序(Selection Sort):在未排序的数据中找到最小(大)的元素,放置在已排序的数据末尾。时间复杂度为O(n^2)。
-
插入排序(Insertion Sort):将未排序的元素插入到已排序的序列中,时间复杂度为O(n^2)。
-
希尔排序(Shell Sort):希尔排序是插入排序的一种改进,它将原序列分割成若干个子序列,对每个子序列进行插入排序,最后对整个序列进行插入排序。时间复杂度为O(nlogn)。
-
二路归并排序(Merge Sort):二路归并排序是指将一个序列分成两个子序列,分别对两个子序列进行归并排序,然后将排序好的两个子序列合并成一个有序序列的过程。这种排序思想采用了分治算法的思想,排序效率较高,时间复杂度为 O(nlogn)。
-
快速排序(Quick Sort):选择一个基准元素,将大于基准元素的数放在一边,小于基准元素的数放在另一边,递归执行该过程,最后得到有序序列。时间复杂度为O(nlogn)。
-
堆排序(Heap Sort):将序列转换为一个大根堆,每次将堆顶元素与堆底元素交换,然后将剩余元素重新构建堆,重复执行该过程,最后得到有序序列。时间复杂度为O(nlogn)。
-
计数排序(Counting Sort):统计小于等于每个元素的个数,再依次计算出每个元素在有序序列中的位置。时间复杂度为O(n+k),其中k为最大元素值。
-
桶排序(Bucket Sort):将元素分到多个桶中,对每个桶进行排序,最后将所有桶中的元素按顺序合并起来。时间复杂度为O(n)。
-
基数排序(Radix Sort):按照低位到高位的顺序对元素进行排序,依次排序后得到有序序列。时间复杂度为O(dn),其中d为元素的位数。
-
多路归并排序:多路归并排序是指将一个序列分成多个子序列,然后对每个子序列进行排序,最后将排好序的子序列合并成一个有序序列的过程。多路归并排序的时间复杂度不仅取决于序列长度,还取决于子序列个数。多路归并排序的优点是可以对比二路归并排序更加高效地利用计算机的多核心处理能力,因此在大规模数据处理中有广泛的应用。
🚀一、计数排序
🔎1.基本思想
计数排序是一种非比较排序算法,它的基本思想是:对于一组待排序的元素,如果知道了每个元素的大小关系,那么就可以利用这个信息对它们进行排序。具体实现时,先统计出待排序元素中每个元素出现的次数,然后根据元素的大小关系,依次把元素放回原来的位置中,最终得到一个有序的序列。
计数排序的基本步骤如下:
- 找出待排序数组中的最大值max和最小值min。
- 创建一个长度为(max-min+1)的计数数组count,并将每个元素都初始化为0。
- 遍历待排序数组,统计待排序数组中每个元素出现的次数,将其存入计数数组中。
- 遍历计数数组count,依次累加前面的元素,得到元素在排序数组中的位置。
- 遍历待排序数组,根据计数数组得到每个元素在排序数组中的位置,依次放回原来的位置,完成排序。
计数排序的时间复杂度为O(n+k),其中n是待排序数组的长度,k是计数数组的大小。当k较小时,计数排序的效率很高,但当k较大时,计数排序的辅助空间会非常大。因此,计数排序适合对于取值范围较小的整数进行排序。
🔎2.复杂度分析
计数排序的时间复杂度为O(n+k),其中n是待排序数列的长度,k是数列中元素的最大值与最小值的差值加上1。空间复杂度也为O(n+k),因为需要借助辅助数组来存储排序结果。
计数排序的核心思想是对每个数进行计数并统计其出现的次数,然后按顺序输出即可。由于不需要比较元素,计数排序的时间复杂度与待排序数列的数据范围有关,而与具体数列中元素的个数无关。
计数排序的优点是速度快,适用于元素数目比较小的情况,但对于数据范围比较大的数列,需要的辅助空间也会很大,而且无法应用于包含负数的数列。
🔎3.应用场景
计数排序适用于数据范围比较小的情况下,例如对于一组正整数的排序。因为计数排序是利用桶的思想实现的,需要开辟一个长度为数据的范围的桶,所以对于数据范围比较大的情况下,计数排序的空间复杂度会非常高,不适合使用。
以下是计数排序的常见应用场景:
-
对一组正整数进行排序,例如考试成绩排序、年龄排序等。
-
统计某一数据集合中某些特定数据的出现次数,例如在一篇文章中统计某些单词的出现次数等。
-
对一组数据进行去重操作,例如将一段文字中重复的单词去除掉,只保留一个。
计数排序主要是用于整数排序,通常能够在O(n)的时间复杂度下实现排序。因此,如果你需要对一组整数进行非常快速地排序,计数排序是一个不错的选择。
🔎4.示例
/// <summary>
/// 计数排序
/// </summary>
public class Program {
public static void Main(string[] args) {
int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };
CountingSort(array);
ShowSord(array);
Console.ReadKey();
}
private static void ShowSord(int[] array) {
foreach (var num in array) {
Console.Write($"{num} ");
}
Console.WriteLine();
}
public static void CountingSort(int[] array) {
if (array.Length == 0) return;
int min = array[0];
int max = min;
foreach (int number in array) {
if (number > max) {
max = number;
}
else if (number < min) {
min = number;
}
}
int[] counting = new int[max - min + 1];
for (int i = 0; i < array.Length; i++) {
counting[array[i] - min] += 1;
}
int index = -1;
for (int i = 0; i < counting.Length; i++) {
for (int j = 0; j < counting[i]; j++) {
index++;
array[index] = i + min;
}
}
}
}
🚀感谢:给读者的一封信
亲爱的读者,
我在这篇文章中投入了大量的心血和时间,希望为您提供有价值的内容。这篇文章包含了深入的研究和个人经验,我相信这些信息对您非常有帮助。
如果您觉得这篇文章对您有所帮助,我诚恳地请求您考虑赞赏1元钱的支持。这个金额不会对您的财务状况造成负担,但它会对我继续创作高质量的内容产生积极的影响。
我之所以写这篇文章,是因为我热爱分享有用的知识和见解。您的支持将帮助我继续这个使命,也鼓励我花更多的时间和精力创作更多有价值的内容。
如果您愿意支持我的创作,请扫描下面二维码,您的支持将不胜感激。同时,如果您有任何反馈或建议,也欢迎与我分享。
再次感谢您的阅读和支持!
最诚挚的问候, “愚公搬代码”
- 点赞
- 收藏
- 关注作者
评论(0)