首页
学习
活动
专区
圈层
工具
发布

数据结构排序——计数排序和排序总结(附上912. 排序数组讲解)

数据结构排序——计数排序和排序总结 现在常见算法排序都已讲解完成,今天就再讲个计数排序。...再总结一下 1.计数排序 计数排序是一种非基于比较的排序算法,它通过统计数组中每个元素出现的次数,然后根据元素的值和出现次数重新构造数组,从而实现排序。...计数排序适用于元素范围比较小且元素非负的情况 步骤: 找出待排序的数组中最大和最小的元素:min和max 统计数组中每个值为 i 的元素出现的次数,存入新建数组 C 的第 i-min 项(c初始化时都是...0),每遇到一次,对应下标上的数就++ 反向填充目标数组:利用新建的数组把数据覆盖回去 时间复杂度:O(n + range) void CountSort(int* a, int n) { //先找最大最小...排序算法 时间复杂度 空间复杂度 稳定性 直接插入排序 O(N^2) O(1) 稳定 希尔排序 O(N^1.3) O(logN) 不稳定 选择排序 O(N^2) O(N) 不稳定 堆排序 O(N*logN

53010

Python 算法基础篇:堆排序和计数排序

Python 算法基础篇:堆排序和计数排序 引言 堆排序和计数排序是两种高效的排序算法,用于将一个无序列表按照特定顺序重新排列。...本篇博客将介绍堆排序和计数排序的基本原理,并通过实例代码演示它们的应用。 ❤️ ❤️ ❤️ 1....计数排序通过统计列表中每个元素的出现次数,然后根据统计结果构建有序列表。通过遍历统计数组,将元素放回原来的位置,实现了计数排序算法。 5....堆排序与计数排序的对比 堆排序和计数排序都是高效的排序算法,它们分别适用于不同类型的排序需求: 堆排序适用于处理大规模数据的排序,它的时间复杂度为 O ( n log n ),稳定且效率高。...计数排序不涉及比较操作,不需要额外的存储空间,因此在适用范围内具有较高的效率。 总结 本篇博客介绍了堆排序和计数排序两种高效的排序算法。

57400
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    计数排序与桶排序python实现

    计数排序与桶排序python实现 计数排序 计数排序原理: 找到给定序列的最小值与最大值 创建一个长度为最大值-最小值+1的数组,初始化都为0 然后遍历原序列,并为数组中索引为当前值-最小值的值...当数值中有非整数时,计数数组的索引无法分配 桶排序 桶排序原理: 桶排序与计数排序类似,但可以解决非整数的排序 桶排序相当于把计数数组划分为按顺序的几个部分 每一部分叫做一个桶,它来存放处于该范围内的数...然后再对每个桶内部进行排序,可以使用其他排序方法如快速排序 最后整个桶数组就是排列好的数据,再将其返回给原序列 举例: ?...桶排序实现 这里选择桶的数量为序列元素个数+1,范围分别是5等分与最大值,和上面那个图一样。...main__': a = [3.2,6,8,4,2,6,7,3] bucket_sort(a) print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8] 总结 计数排序与桶排序都是以牺牲空间换时间

    1.5K10

    排序8: 计数排序

    排序思想 2. 图解 3. 代码实现 3.1 逻辑 4. 特性总结 ---- 1. 排序思想 计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。 操作步骤: 1....代码实现 3.1 逻辑 a、求最大最小值:先遍历一遍数组找到最大值和最小值 max 和 min,这时候就能够确定相对的范围大小range = max  + min + 1(之所以加1是因为是闭区间要多加一个元素...b、计数:然后开始重新遍历一遍计数,我们遍历一遍原数组,每次取到的数字就是新开辟的数组的下标,这里因为我们为了取到相对位置,需要将取到的数组减去 min 我们++即可。...c、排序(将统计好的数字放到数组):我们遍历一遍排好的数组,次数大于1的数字(这里取到的数字需要重新加上min)按次数放到原数组中。...计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。 2. 时间复杂度: O(MAX(N, 范围 )) 3.

    68920

    【排序算法】—— 计数排序

    一、简介         计数排序,顾名思义就是记录数据出现的次数进行排序,时间复杂度为O(N+K),空间复杂度为O(N)。只能用于整型,对于比较集中重复率比较高数据更为适用。...tmp初始化为0,然后进行计数,比如第一个数字为1那么就在1下标位置加1,以此类推遍历完数组arr。...,其实只需要最大的值减最小的值再加1的长度的数组空间就够用了。同样在记录时先减去最小值,等赋值给原数组的时候再加回去。...for (int i = 0, j = 0; i < ret; i++) { while (tmp[i]--) arr[j++] = i + min; } } 三、适用范围         计数排序的缺点就是只能对整型数据进行排序...而且对于整形的排序他更适合的是最小值和最大值跨度比较小的数据,或者重复率比较高的数据。比如10个整数最小的是1最大的那个是100万。使用计数排序就会导致空间的开销很大,效率也比较低。

    29810

    【排序算法】—— 计数排序

    这种新序列遵循着一定的规则,体现出一定的规律,因此,经处理后的数据便于筛选和计算,大大提高了计算效率。对于一个排序算法的优劣,我们需要从它的时间复杂度、空间复杂度和稳定性三个方面来考虑。...这就是计数排序。我们再来看另外一种情况:         当数组中元素过大时,我们发现会有许多的空间没有用到,存在浪费。...很简单,我们先遍历一遍数组,找到最大值和最小值,它们的差便是我们需要的开辟空间的大小,也就是它们之间的范围。        ...,找最大值与最小值与统计元素出现此时的时间复杂度为O(N),取count中的元素存放在原数组的时间复杂度为O(range),因此计数排序的总时间复杂度为O(N + range)。...由于需要通过创建一个计数数组来完成我们的排序,因此空间复杂度为O(range)。

    38610

    【数据结构&&计数排序】计数排序

    ,随后对每个桶进行排序,最后再将所有桶的数据进行合并 基数排序 通过将待排序数值按位数分组,逐位进行排序,通常配合计数排序实现 计数排序 计数排序是一种非比较的排序算法,适用于特定条件下的排序,尤其是当待排序的元素范围较小其重复元素较多的时候...他的基本原理是利用一个额外的数组来记录每一个元素出现的次数,用次数来表达从而达到排序的目的,以下是排序的原理步骤 1.确定范围:首先确定待排序数组的元素的最大值和最小值 2.创建计数数组:根据范围创建一个技术数组...,数组的大小通常为最大值和最小值的差+1,用于存放每个元素的出现次数 3.计数:遍历原始数组,统计每个元素相同的次数,对每个元素在计数数组中对应的位置进行计数。...即:若元素为x,则计数数组的第x位置加一。 4.计算位置:通过累加计数数组的数值,得到每个元素在已排序数组中的最终位置。...5.排序输出,根据计数数组生成的已排序数组,遍历计数数组,按次数将对应的元素输出到结果数组中 计数排序的时间复杂度O(n+k),其中n是待排序元素的数量,k是计数数组的大小。

    95810

    算法渣-排序-计数排序

    没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法 线性排序 常见的三种以线性时间运行的算法:计数排序、基数排序和桶排序 需要注意的是线性排序算法是非基于比较的排序算法...(此处并非比较各元素的大小,而是通过对元素值的计数和计数值的累加来确定)。...这样一来,同样是95分的小红和小绿就能够清楚地排出顺序了,也正因此,优化版本的计数排序属于稳定排序。...时间复杂度:3N(计算最大最小数、计数、排好序的数组) + M(位置数组),去掉系数,时间复杂度是O(N+M) 空间复杂度:只考虑统计数组,那就是M 局限性 1.当数列最大最小值差距过大时,并不适用计数排序...比如给定20个随机整数,范围在0到1亿之间,这时候如果使用计数排序,需要创建长度1亿的数组。不但严重浪费空间,而且时间复杂度也随之升高。 2.当数列元素不是整数,并不适用计数排序。

    78920

    ①归并排序、快速排序 、堆排序、计数排序

    排序数组 315. 计算右侧小于当前元素的个数 561. 数组拆分 1122. 数组的相对排序(计数排序) 268. 丢失的数字(计数排序) 215. 数组中的第K个最大元素 347....,然后递归地对这些小数组进行排序,最后再将排好序的小数组合并成一个整体有序的数组。...排序(Conquer): 当每个子数组只包含一个元素时,认为它已经有序。 合并(Merge): 将两个有序的子数组合并成一个有序的数组。...: 建堆操作的时间复杂度为O(n),排序操作的时间复杂度为O(n log n)。...数组的相对排序(计数排序) ⚪点击跳转:1122. 数组的相对排序 给你两个数组,arr1 和 arr2,arr2 中的元素各不相同,arr2 中的每个元素都出现在 arr1 中。

    1.1K10

    外排序、基数排序与计数排序

    "1"; char file2[100] = "2"; for (int i = 0; i <= n; ++i) { sprintf(file2, "%d", i); //读取file1和file2...arr, 0, n); for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } printf("\n"); return 0; } 3.计数排序...  思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。...根据统计的结果将序列回收到原来的序列中 //非比较排序:基数排序 计数排序 桶排序 //计数排序 //思想:数组中的每个位置是下标对应的值的次数 一个值出现几次 它对应位置就会++几次 //所开空间数为...max-min+1个 a[i]-min就是映射的相对位置 //适用场景:适用范围相对集中的数据进行排序处理(负数也可以) //时间复杂度是O(N+range) //空间复杂度是O(range) //稳定性

    62220

    Python实现计数排序

    一、计数排序简介 计数排序(Counting Sort)是一种不比较数据大小的排序算法,是一种牺牲空间换取时间的排序算法。...三、Python实现计数排序 # coding=utf-8 def counting_sort(array): if len(array) < 2: return array...然后根据上面分析的排序原理,进行计数,再将数据添加到新列表中。i 表示计数列表的索引,也表示待排序列表中值为 i 的元素,j 表示值为 i 的元素有 j 个。 四、计数排序的时间复杂度和稳定性 1....时间复杂度 在计数排序中,需要走访待排序列表中的每一个元素,进行计数,列表长度为 n ,然后需要遍历计数列表,添加数据到新列表中,计数列表长度为 k+1 ,时间复杂度为 T(n)=n+k+1,再乘计数和添加数据的步骤数...(常数,不影响大O记法),所以计数排序的时间复杂度为 O(n+k) 。

    1.4K50

    排序算法(八):计数排序

    计数排序是一种非比较性质的排序算法,元素从未排序状态变为已排序状态的过程,是由额外空间的辅助和元素本身的值决定的。...计数排序过程中不存在元素之间的比较和交换操作,根据元素本身的值,将每个元素出现的次数记录到辅助空间后,通过对辅助空间内数据的计算,即可确定每一个元素最终的位置。...比较性质排序算法的时间复杂度有一个理论边界,即 。...所有元素的出现次数和元素值记录如下,其中 表示该元素出现的次数, 表示元素值: 可以发现,计数排序的该过程,其实就是将待排序集合中的每个元素值本身大小作为下标,依次进行了存放。...算法分析 由算法示例可知,计数排序的时间复杂度为 。因为算法过程中需要申请一个额外空间和一个与待排序集合大小相同的已排序空间,所以空间复杂度为 。

    85520

    非比较排序-计数排序

    1.计数排序 前面学习了归并排序,快速排序时间复杂度为O(n*logn)而有没有比这更快的排序算法呢?...当然是有的那就是计数排序,首先计数排序并不是比较排序算法,而是利用数组来实现的一种算法,想象一下这样一个场景,假如给数组{1,4,5,1,3}做一个排序,我们可以看出其中最大的值就是5,但是怎么利用数组实现排序呢...为什么必须要倒着遍历,如果不倒着遍历小灰和小绿的位置就发生了变化,也就不再是稳定的排序了。 java代码实现如下。 ?...我们来看看计数排序的时间复杂度和空间复杂度,首先我们找最大值和最小值执行了n次,然后计数数组产生值有需要遍历n次,也就是O(2*n),然后我们再变形了一次计数数组,就是k次,最后我们又遍历了一次原数组,...我们返回数组定义了一个和原始数组一样长的也就是n,然后定义了一个计数数组k,所以就是O(n+k),如果不考虑结果数组就是O(n)。

    97561

    Python算法——计数排序

    计数排序是一种线性时间复杂度的排序算法,具有稳定性和适用性广泛的特点。本文将详细介绍计数排序的工作原理和Python实现。...计数排序的工作原理 计数排序的基本思想是: 统计数组中每个元素出现的次数,得到元素的频率统计信息。 根据频率统计信息,重建有序数组。 计数排序的关键在于如何统计元素的频率以及如何重建有序数组。...Python实现计数排序 下面是Python中的计数排序实现: def counting_sort(arr): max_val = max(arr) min_val = min(arr)...max_val 和 min_val 分别是数组的最大值和最小值。 range_val 表示元素范围的大小。 初始化计数数组 count,用于统计每个元素出现的次数。...arr = [4, 2, 2, 8, 3, 3, 1] sorted_arr = counting_sort(arr) print("排序后的数组:", sorted_arr) 时间复杂度 计数排序的时间复杂度为

    73210

    八十五、再探希尔排序,桶排序,计数排序和基数排序

    「---- Runsen」 关于排序,其实还有很多,比如常见的希尔排序,桶排序,计数排序和基数排序,今天一口气把十大排序剩下的全部解决。...因此计数排序需要使用一个辅助数组计数列表,也可以叫做,因此空间复杂度不是 O(1) ,是一种牺牲空间换取时间的排序算法。...走访完整个待排序列表,计数列表中索引i的值j表示i的个数为j,统计出待排序列表中每个值的数量。 待排序数据的值就是辅助数组的索引,辅助数组索引对应的位置保存这个待排序数据出现的次数。...最后从辅助数组中取出待排序的数据,放到排序后的数组中。 最后创建一个新列表,遍历计数列表,对新列表进行添加数据就可以了。...,桶排序,计数排序和基数排序全部介绍完毕,后面引入有向图,最后进行烧脑的动态规划DP算法。

    94120

    ——非比较排序—计数排序

    根据统计的结果将序列回收到原来的序列中 找出最大和最小值: 首先遍历数组 a 一次,找到其中的最大值 max 和最小值 min。...创建计数数组: 根据最大值和最小值计算出数值范围 range = max - min + 1,并用 calloc 动态分配一个大小为 range 的整型数组 count。...(a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } int range = max - min + 1;//确定新创建数组的数据个数和原数组大小相同...时间复杂度:计数排序的时间复杂度为O(n+k),其中n是数组长度,k是数组中数据范围(最大值与最小值之差加一)。当k不是很大且远小于n时,计数排序非常高效。...空间复杂度:计数排序需要额外的计数数组,其空间复杂度为O(k),这使得它在处理大数据范围时可能比较消耗内存。 稳定性:计数排序是一种稳定的排序算法。

    66910

    排序算法指南:计数排序

    前言: 计数排序(Counting Sort)是一种非比较型的排序算法,它的核心思想是利用数组来存储输入数据中每个元素的出现次数,然后根据这些统计信息来确定输出序列。...一、计数排序的原理 计数排序适用于整数数据,且这些整数的范围不宜过大,它的基本步骤如下: ①找出范围:确定输入数组中最大值(max)和最小值(min),从而确定数据的范围range:max-min+1...输出排序数组: 遍历整个计数数组,将每个索引位置的值作为元素出现的次数,依次将该索引对应的元素输出到结果数组中。...出现了2次 二、计数排序的工作流程 以如下数组为例,数组a[2 3 8 7 1 2 2 2 7 3 9 8 2 1 4 2 4 6 9 2] 第一步:找到 min、max 扫描数组:...计数排序主要分 3 步: 1.

    50510
    领券