|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Kommander Bomber 2:5059/26.17 24 Dec 2002 20:46:10
To : Sergey Panfilov
Subject : Re: быстpая соpтиpовка
--------------------------------------------------------------------------------
Привет, Alexx!
AO> помогите плиз, а то вpемени мало. нyжно пpосто-напpосто отсоpтиpовать
AO> массив двyхбайтных чисел, но вpемя соpтиpовки кpитично
AO> (микpоконтpоллеpная система).
Hадеюсь, по исходнику поймешь как работает. Основная функция - sort.
=== Здесь начинается src.c ===
typedef unsigned short uint16;
typedef long int32;
typedef short int16;
typedef int16 sizer;
/*typedef int32 sizer;*/
void sort1(uint16 *mas, sizer razm) {
uint16 swp, prefix;
sizer i,j;
sizer Pakety[128];
if (razm>2/*или не 2, а больше, тогда оставшееся отработать отдельно,
например использовать quicksort для razm, удовлетворяющих
условию 256+2*razm>razm*log(2,razm)*/) {
prefix=mas[0]&0xff80;
for (i=0; i<128; i++) Pakety[i]=0;
for (i=0; i<razm; i++) Pakety[mas[i]&0x7f]++;
j=0;
for (i=0; i<128; i++)
while (Pakety[i]--)
mas[j++]=prefix|((uint16)i);
} else
if (mas[0]>mas[1]) {
swp=mas[0];mas[0]=mas[1];mas[1]=swp;
}
}
uint16 *sort(uint16 *Massiv, sizer Razmer) {
sizer Pakety[512],i,t;
uint16 *Massiv1;
for (i=0; i<512; i++) Pakety[i]=0;
for (i=0; i<Razmer; i++) Pakety[Massiv[i]>>7]++;
for (i=1; i<512; i++) Pakety[i]+=Pakety[i-1];
Massiv1=(uint16 *)malloc(Razmer*sizeof(uint16));
for (i=0; i<Razmer; i++)
Massiv1[--Pakety[Massiv[i]>>7]]=Massiv[i];
for (i=0; i<511; i++)
if ((t=Pakety[i+1]-Pakety[i])>1)
sort1(&Massiv1[Pakety[i]], t);
if ((t=Razmer-Pakety[511])>1)
sort1(&Massiv1[Pakety[i]], t);
return Massiv1;
}
=== А здесь src.c кончается ===
--- GoldED/W32 3.0.1-asa8
* Origin: -or- (2:5059/26.17)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
