记数排序

Dear 丶 2022-08-22 04:54 27阅读 0赞

记数排序思路：

首先遍历一遍，找到最大和最小的数，利用最大和最小开辟空间，记为tmp.然后统计各个数字出现的次数，利用出现的次数，遍历tmp,根据出现的次数，重新写入数组a中

</pre><pre name="code" class="cpp">//计数排序
    void CountSort(int* a, int size)
    {
    	assert(a);
    	int max = a[0];
    	int min = a[0];
    	for (int i = 0; i < size; i++)  //利用最大和最小开辟空间
    	{
    		if (a[i]>max)
    		{
    			max = a[i];
    		}
    		if (a[i] < min)
    		{
    			min = a[i];
    		}
    	}
    	int* tmp = new int[max - min + 1];//ex:0到8--要开9个空间
    	memset(tmp, 0, sizeof(int)*(max - min + 1));  //记得初始化，不然计数会出现一堆随机值
    	for (int i = 0; i < size; i++)
    	{
    
    		++tmp[a[i]-min];
    	}
    	int j = 0;
    	for (int i = 0; i < size; i++)
    	{
    		while (tmp[i]>0)
    		{
    			a[j++] = i+min;
    			tmp[i]--;
    		}
    	}
    
    
    }
    void Print(int *arr, int size)
    {
    	for (int i = 0; i < size; i++)
    	{
    		cout << arr[i] << " ";
    	}
    	cout << endl;
    }
    
    void TestCountSort()
    {
    	//int array[] = { 10, 12, 11, 10 ,19};
    	int array[] = { 10, 11, 13, 12, 19, 16, 18, 15, 17, 14 };
    	CountSort(array, sizeof(array) / sizeof(array[0]));
    	Print(array, sizeof(array) / sizeof(array[0]));
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，27人围观）

还没有评论，来说两句吧...

相关阅读

相关科学记数法中的e

![20191009191333910.png][] [日萌社][Link 1] [人工智能AI：Keras PyTorch MXNet TensorFlow Pa

梦里梦外;/ 2023年07月05日 11:47/ 0 赞/ 26 阅读

相关记数排序

记数排序思路：首先遍历一遍，找到最大和最小的数，利用最大和最小开辟空间，记为tmp.然后统计各个数字出现的次数，利用出现的次数，遍历tmp,根据出现的次数，重新写入数组a中

Dear 丶/ 2022年08月22日 04:54/ 0 赞/ 28 阅读

相关 Vijos P1848记数问题【sprintf用法】

P1848记数问题未递交标签： [NOIP普及组2013][NOIP_2013] \[显示标签\] 描述试计算在区间 1 到 n 的所有整数中,数字 x(0

我就是我/ 2022年08月20日 13:16/ 0 赞/ 167 阅读

相关数组的排序

素组的排序 <span style="font-size:18px;"><strong>/ copyright (c) 2014.烟大计算机学院

红太狼/ 2022年08月14日 02:54/ 0 赞/ 229 阅读

相关三数排序java

public class ThreeNumberSort \{ //方法1 sortNum1方法用三目运算的方法从小到大输出三个数 private static

谁践踏了优雅/ 2022年06月16日 23:50/ 0 赞/ 38 阅读

相关数组的排序

问题描述【项目3 - 数组的排序】（1）编写函数，完成冒泡排序要求不能改变下面的main函数。 ![20171012201216829][] 程序代码

雨点打透心脏的1/2处/ 2022年06月07日 06:13/ 0 赞/ 214 阅读

相关冒泡排序（数组）

/ @author LLJ 冒泡排序 / public class MaoPao { public s

小鱼儿/ 2022年05月22日 11:39/ 0 赞/ 239 阅读

相关直接排序（数组）

/ @author LLJ 直接排序（数组） / public class SelectSort {

逃离我推掉我的手/ 2022年05月22日 11:39/ 0 赞/ 196 阅读

相关 java实现数排序-冒泡排序

一、原理： 1. 冒泡排序----比较相邻的两个数，将较大的数放在右端。 2. N个数冒泡排序—需要进行（N-1）趟排序，第i趟需做（N-i）次比较。第

男娘i/ 2022年04月17日 04:15/ 0 赞/ 252 阅读

相关 1024 科学记数法

1024 科学计数法 (20)（20 分）科学计数法是科学家用来表示很大或很小的数字的一种方便的方法，其满足正则表达式\[±\]\[1-9\]”.”\[0-9\]+E\

末蓝、/ 2022年02月19日 02:49/ 0 赞/ 263 阅读