美文网首页Be Coding
排序算法_计数排序

排序算法_计数排序

作者: KPort | 来源:发表于2015-07-23 18:09 被阅读40次

计数排序是一种非比较的排序,这种方法思路大概是先算出待排序数据里面的数字分别出现多少次,然后再依据这个存放进新的数组里面,输出这个数组,排序也就完成了。时间复杂度为o(n+k),很多人说是o(n),但其实只是接近而已。其中里面的n是排序的数据个数,而k是排序中最大的值,可想而知,在n确定的情况下,k的值越小,时间复杂度越低,例如就算n很小,但排序数是{2,5,3,10000}的话,那也需要很多时间,此排序方法就不怎么适用了。
程序例子:(主要参考排序核心方法,其他的写得不够好)
<pre><code>

include <iostream>

using namespace std;
//-------------------------
int data[100];//全局变量,用来存放待排序数据
int array_length;//数组的长度
int array_max;//数组中最大的值,也就是k
//---------------------------------
//初始化数组
void Init_array()
{
cout<<"Input:(End with 1000)";
for(int i=0;; i++)
{
cin>>data[i];
if(data[i]==1000)
{
array_length = i;//由此获得数组长度
break;
}
}
}
//-----------------------------------
//求数组中最大的数
void max_array()
{
int t;
array_max = data[0];
for(int i=0; i<array_length-1; ++i)
{
if(data[i]<data[i+1])
{
array_max = data[i+1];
}
else
{
t = data[i];
data[i] = data[i+1];
data[i+1] = t;
}
}
}
//----------------------------------
//计数排序
//参数分别是1.待排序数组,2.数组长度,3.待排序数组中最大的值,也就是k
void sort_counter(int d[], int n, int k)
{
int i, j = 0,p = 0;
// 实际需要的空间比K大1
k++;
//辅助数组,当然也可以用其他编程技术来代替
int counter[100] = {0};
// 计数
for(i=0; i<n; ++i)
{
p = d[i];
counter[d[i]]++; //counter数组下标为排序的数,下标对应的数组值为这个数出现的次数
}
//将计数结果保存到待排数据数组
for(i=0; i<k; ++i)
{
while(counter[i]-- > 0) //将出现的数字以及次数,依次放到数组中
{
d[j++] = i;
}
}
}
//主函数
int main(void)
{
Init_array();
max_array();
sort_counter(data, array_length-1, array_max);
int i;
for(i=0; i<array_length; ++i)
{
cout<<data[i]<<" ";
}
cout<<endl;
return 0;
}
</code></pre>

相关文章

  • 线性排序

    桶排序、计数排序、基数排序 一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。2.线性排序算法...

  • 算法and数据结构

    算法 冒泡排序 选择排序 计数排序

  • 排序算法-8---计数排序

    # 排序算法-8---计数排序 概念 计数排序(Counting sort)是一种稳定的线性时间排序算法。该算法于...

  • 08-计数排序(Counting Sort)

    计数排序(Counting Sort) 本节内容,继续介绍排序算法,在本节内容之前,介绍过7种排序算法,那计数排序...

  • 排序算法

    常见排序算法 本文涉及的算法有:冒泡排序选择排序计数排序 冒泡排序 伪代码 流程图 选择排序 伪代码 流程图 计数...

  • (转)排序算法

    排序算法点这里 数据结构与算法——计数排序、桶排序、基数排序

  • LeetCode大全

    1.常见排序算法: 常见的排序算法:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、...

  • 算法入门——计数排序、桶排序、基数排序

    上篇文章我们学习了算法入门——归并排序、希尔排序,这篇文章我们学习算法入门——计数排序、桶排序、基数排序。 计数排...

  • 面试算法知识梳理(12) - 二叉树算法第二部分

    面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 ...

  • 面试算法知识梳理(13) - 二叉树算法第三部分

    面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 ...

网友评论

    本文标题:排序算法_计数排序

    本文链接:https://www.haomeiwen.com/subject/tjtmqttx.html