首页 > 其他分享 >COUNTING-SORT(计数排序) and

COUNTING-SORT(计数排序) and

时间:2024-08-05 22:27:12浏览次数:14  
标签:SORT ... 排序 int ++ 计数 length COUNTING

计数排序         

        计数排序假设n个输入元素(适用于小范围区间)中的每一个都是在0到k区间内的一个整数,其中k为某个整数。当k=O(n)时,排序的运行时间为\Theta (n).

        计数排序的基本思想:对每一个输入的元素x,确定小于x的元素个数。利用这一信息,就可以直接把x放到它在输出数组中的位置上了。例如,如果有17个元素小于x,则x就应该在第18个输出位置上。当有几个元素相同时,这一方案要略做修改。因为不能把它们放在同一个输出位置上。

         我们假设个数组 A[0...n-1 ],   A.length = n,  k 为A中最大元素,我们还需要两个数组:B(0...n)存放排序的输出,C[0...k] 提供临时存储空间

伪代码:

COUNTING-SORT(A , B , k)

        let C[0...k]  be a new array            

        for i = 0 to k                             //将数组C都置为0

                C[ i ] = 0

        for j = 0 to A.length                        

                C[ A [ j ] ] = C[ A [ j ] ] + 1

        for i = 1 to k                                        //找到元素的位置

             C [ i ] = C[ i ] + C[ i -1 ];   

        for j = A.length downto 0

                B[ C[ A[ j ] ]  - 1 ]  =A[ j ]

                C[ A[ j ] ]  = C[ A[ j ] ] -1

看图理解:

根据上图排完序后相同元素的位置与排之前相同,所以计数排序是稳定的排序

算法分析:

COUNTING-SORT(A , B , k)

        let C[0...k]  be a new array                     1

        for i = 0 to k                                             k+1

                C[ i ] = 0                                           k

        for j = 0 to A.length                                   n+1

                C[ A [ j ] ] = C[ A [ j ] ] + 1                  n

        for i = 1 to k                                                k

             C [ i ] = C[ i ] + C[ i -1 ];                           k-1

        for j = A.length downto 0                             n+1

                B[ C[ A[ j ] ]  - 1 ]  =A[ j ]                      n

                C[ A[ j ] ]  = C[ A[ j ] ] -1                         n

可知时间消耗为\Theta (n)

我们写一个存在负数的计数排序代码:

#include<iostream>
using namespace std;

//计数排序
void COUNTING_SORT(int A[], int B[],int k,int size,int n)
{
	int* C = (int*)malloc(sizeof(int) * k);
	for (int i = 0; i < k; ++i)
	{
		C[i] = 0;
	}
	for (int j = 0; j < size; ++j)
	{
		C[A[j] + n]++;
	}
	for (int i = 1; i < k; ++i)
	{
		C[i] = C[i] + C[i - 1];
	}
	for (int j = size - 1; j >= 0; --j)
	{
		B[C[A[j]+n]-1] = A[j];
		C[A[j] + n]--;
	}
	free(C);
}

//打印
void Print(int A[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		cout << A[i] << " ";
	}
	cout << endl;
}
int main()
{
	int A[] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };//想要负数存入计数数组C中,要将负数变为正数
	int size = sizeof(A) / sizeof(int);
	int n = 25; //每个元素都加上n值存入数组C
	int k = 46;
	int B[16];
	cout << "要排列的数组为:" << endl;
	Print(A, size);
	COUNTING_SORT(A, B, k, size,n);
	cout << "使用计数排序后:" << endl;
	Print(B, size);

}

结果:

要排列的数组为:
13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7
使用计数排序后:
-25 -23 -22 -16 -7 -5 -4 -3 -3 7 12 13 15 18 20 20

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      

标签:SORT,...,排序,int,++,计数,length,COUNTING
From: https://blog.csdn.net/Hennan_Dianzi_C/article/details/140932110

相关文章

  • Unity强化工程 之 Mask & SortingGroup
    本文仅作笔记学习和分享,不用做任何商业用途本文包括但不限于unity官方手册,unity唐老狮等教程知识,如有不足还请斧正1.Mask遮罩故名思意就是起到遮挡作用的罩子:精灵遮罩-Unity手册如果我想让sprite与遮罩发生交互,那么我需要勾选spritrrenderer的交互选项之后就可......
  • FPGA设计之跨时钟域(CDC)设计篇(5)----同步FIFO的两种设计方法(计数器法/高位扩展法 | 手撕
    1、什么是FIFO?        FIFO(FirstInFirstOut)是一种先进先出的数据缓存器,在逻辑设计里面用的非常多。它是一种存储器结构,被广泛应用于芯片设计中。FIFO由存储单元队列或阵列构成,第一个被写入队列的数据也是第一个从队列中读出的数据。        FIFO设计可......
  • c++中的sort
    前言Hello,大家好啊,我是文宇。正文sort函数是C++标准库提供的用于对数组或容器中的元素进行排序的函数。通过使用快速排序或其它高效的排序算法,sort函数能够以非常高效的方式对元素进行排序。sort函数用法灵活多样,可以对不同类型的元素进行排序,并且可以通过自定义比较函数或......
  • “命令行利器:sort、uniq、date、ntpdate详解与实战“
    当今操作系统中的命令行工具不仅是管理和调试系统的利器,也是程序员和系统管理员的重要工具。在Unix和类Unix系统中,sort、uniq、date和ntpdate是几个常用的命令,它们各自拥有独特的功能,可以在日常工作中极大地提高效率。本文将深入探讨这些命令的用法和实际应用。1. sort命令s......
  • 背包计数问题的多项式优化
    此优化针对以下计数问题:n件物品,背包容量为m,第i件物品体积为\(a_i\),求装满的方案数。(01背包)n种物品,背包容量为m,第i件物品体积为\(a_i\),数量无限,求装满的方案数。(完全背包)n种物品,背包容量为m,第i件物品体积为\(a_i\),数量为\(b_i\),求装满的方案数。(多重背包)\((1\l......
  • LeetCode 1387. Sort Integers by The Power Value
    原题链接在这里:https://leetcode.com/problems/sort-integers-by-the-power-value/description/题目:Thepowerofaninteger x isdefinedasthenumberofstepsneededtotransform x into 1 usingthefollowingsteps:if x iseventhen x=x/2if x is......
  • python用List的内建函数list.sort进行排序
    对List进行排序,Python提供了两个方法方法1用List的内建函数listsort进行排序listsort(func=None,key=None,reverse=False)Python实对List进行排序,Python提供了两个方法方法1.用List的内建函数list.sort进行排序list.sort(func=None,key=None,reverse=False)>>>list=......
  • 【笔记】计数选讲:容斥、LGV、集合幂级数、GF 2024.8.2
    今天写的很乱。[HEOI2013]SAO容斥。因为我们已经知道父亲\(<\)儿子时的情况(\(n!/\prod_isiz_i\),也适用于森林),那么儿子\(<\)父亲的情况就容斥掉,无限制的就当作那条边不存在。树上背包,记录当前节点为根的连通块大小和容斥系数的积。*[ECFinal23A]DFSOrder4转写为:统计多......
  • BZOJ2839/LG10596 集合计数 题解(二项式反演+扩展欧拉定理)
    题目大意:一个有\(N\)个元素的集合有\(2^N\)个不同子集(包含空集),现在要在这\(2^N\)个集合中取出若干集合(至少一个),使得它们的交集的元素个数为\(K\),求取法的方案数,答案模\(10^9+7\)。为表述方便,不妨设这\(i\)个元素分别为\(1\simn\)。前置知识:二项式反演。考虑设\(g(......
  • 回调函数和qsort,strcmp函数
    有任何不懂的问题可以评论区留言,能力范围内都会一一回答1.回调函数是什么?回调函数就是一个通过函数指针调用的函数。如果你把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,被调用的函数就是回调函数。回调函数不是由该函数的实现方直接调用,......