《算法导论》 上的计数排序
文章图片
#include
<
iostream
>
文章图片
#include
<
string
>
文章图片
using namespace
std;
文章图片
const int
MaxN
= 40
;
文章图片
文章图片
void
counting_sort(
int
A[],
int
B[],
int
k)
文章图片
文章图片
...
{
文章图片
int C[MaxN];
文章图片
//for(int i = 0;
i < MaxN;
i++)
文章图片
//C[i] =0;
//初始化
文章图片
memset(C, 0, sizeof(C)/sizeof(C[0]));
文章图片
for(int i = 0;
i < k;
i++)
文章图片
C[A[i]] = C[A[i]] + 1;
//C[i]包含元素值是i的个数
文章图片
// cout<<"C["<
文章图片
for(int j = 1;
j < k;
j++)
文章图片
C[j] = C[j] + C[j-1];
//C[i]包含等于或小于i的元素的个数
文章图片
for(j = k-1;
j >= 0;
j--)
文章图片
文章图片
...{
文章图片
B[C[A[j]]-1] = A[j];
文章图片
C[A[j]] = C[A[j]] -1;
文章图片
}//对于每个A[j], 值C[A[j]]即为A[j]在输出数组中的最终位置，因为共有C[A[j]]
文章图片
//个元素小于等于A[j].由于各个元素可能不一定是不同的，因此，每当将一个值A[j]放在数组B中，
文章图片
//都要减小C[A[j]]的值。
文章图片
文章图片
文章图片
}
文章图片
文章图片
int
main()
文章图片
文章图片
文章图片
...
{
文章图片
文章图片
int A[6]=...{4,4,5,1,1,1};
文章图片
int B[MaxN];
文章图片
memset(B, 0, MaxN);
文章图片
counting_sort(A, B, 6);
文章图片
文章图片
for(int i = 0;
i < sizeof(A)/sizeof(A[0]);
i++)
文章图片
cout<<"B["<
文章图片
文章图片
return 0;
文章图片
}
文章图片
//
《算法导论》中:计数排序的思想就是对每一个输入元素x，确定出小于x的元素个数
文章图片
//
但是我觉得计数排序的应用范围太狭小了，对于元素相差较大者，不易使用。
文章图片
//
如果按照元素的比较方法来实现到可以克服这个问题，但是计算排序的效率高就在于不比较元素之间的
文章图片
//
大小来实现。否则，效率一定会降低，而且演化成比较排序。
推荐阅读
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 《跨界歌手》:亲情永远比爱情更有泪点
- 诗歌:|诗歌: 《让我们举起世界杯，干了！》
- 期刊|期刊 | 国内核心期刊之（北大核心）
- 《魔法科高中的劣等生》第26卷（Invasion篇）发售
- 人间词话的智慧
- 《一代诗人》37期，生活，江南j，拨动心潭的一泓秋水
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术
- 书评——《小行星》