8.2 Counting sort

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

<< Introduction to algorithms >> ( Second Edition )

8.2 Counting sort

Counting sort assumes that each of the n input elements is an integer in the range

0 to k, for some integer k. When k = O( n ), the sort runs in O( n ) time.

The basic idea of counting sort is to determine, for each input element x, the

number of elements less than x. This information can be used to place element x

directly into its position in the output array. For example, if there are 17 elements

less than x, then x belongs in output position 18. This scheme must be modified

slightly to handle the situation in which several elements have the same value, since

we don't want to put them all in the same position.

Solution:

// 声明:本代码旨在实现原文的思想

// copyleft 2004 http://blog.csdn.net/mskia

// email: bitrain@hotmail.com

#ifndef Counting_Sort_by_mskia

#define Counting_Sort_by_mskia

namespace te {

void counting_sort( unsigned int *first , unsigned int *last ) {

unsigned int max = 0;

for ( unsigned int *p = first; p <= last; ++p ) {

if ( *p > max ) {

max = *p;

}

}

unsigned int len = max + 1;

unsigned int *counter = new unsigned int [ len ];

for ( unsigned int i = 0; i < len; ++i ) {

counter[ i ] = 0;

}

for ( unsigned int *p = first; p <= last; ++p ) {

++counter[ *p ];

}

for ( unsigned int i = 0; i < len; ++i ) {

unsigned int &t = counter[ i ];

while ( t > 0 ) {

*( first++ ) = i;

--t;

}

}

delete[] counter;

return;

}

}

#endif

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航