• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

计数排序算法(C语言实现)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

计数排序,  比较适合数值跨度比较小的,  也就是数组中最大值减去最小值得到的值尽量小,  同时数组元素又比较多的情况下用计数排序效率比较高,同时,计数排序算法基友稳定性。

计数排序的时间复杂度为O(n),计数排序是用来排序0到100之间的数字的最好的算法。

算法的步骤如下:

      1.找出待排序的数组中最大和最小的元素

      2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项

      3.对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)

      4.反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1

下面直接贴个C语言实现的代码:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void print_arry(int *arr,int n)
{
	int i;
	for(i = 0; i<n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void count_sort(int *arr, int *sorted_arr, int n)
{
	int *count_arr = (int *)malloc(sizeof(int) * 100);
	int i; 
	//初始化计数数组 
	for(i = 0; i<100; i++)
		count_arr[i] = 0;
	//统计i的次数 
	for(i = 0;i<n;i++)
		count_arr[arr[i]]++;
	//对所有的计数累加 
	for(i = 1; i<100; i++)
		count_arr[i] += count_arr[i-1]; 
	//逆向遍历源数组(保证稳定性),根据计数数组中对应的值填充到先的数组中 
	for(i = n; i>0; i--)
	{
		sorted_arr[count_arr[arr[i-1]]-1] = arr[i-1];
		count_arr[arr[i-1]]--;	
	} 
	free(count_arr);
}
int main() {
	int n,i;
	printf ("待排序数组的大小 n="); 
	scanf ("%d", &n); 
	
	int *arr = (int *)malloc(sizeof(int) * n);
	int *sorted_arr = (int *)malloc(sizeof(int) * n);
	
	srand (time (0));
	for (i = 0; i<n; i++)
	{
		arr[i] = rand() % 100;
	}
	printf ("随机生成数值为0~99的数组...\n");
	printf ("初始化数组: ");
	print_arry(arr, n);
	count_sort(arr, sorted_arr, n);
	printf ("排序后的数组:"); 
	print_arry(sorted_arr, n);
	return 0;
	system ("pause");
	
}


 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#索引器使用总结发布时间:2022-07-13
下一篇:
c++下使用libsvm发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap