| Код |
#include<iostream.h>
/**
* слияние упорядоченных частей массива в буфер temp
* a -- сортируемый массив
* lb -- левая граница
* split -- индекс, по которому делится массив
* rb -- правая граница
**/
void merge( int *a, int lb, int split, int rb )
{
int pos1, pos2, pos3, *temp;
pos1 = lb;
pos2 = split+1;
pos3 = 0;
temp = new int[ (rb-lb)+1 ];
while( pos1 <= split && pos2 <= rb )
{
if( a[ pos1 ] < a[ pos2 ] )
{
temp[pos3++] = a[pos1++];
}
else
{
temp[ pos3++ ] = a[ pos2++ ];
}
}
while( pos2 <= rb )
{
temp[ pos3++ ] = a[ pos2++ ];
}
while( pos1 <= split )
{
temp[ pos3++ ] = a[ pos1++ ];
}
for( pos3 = 0; pos3 < rb-lb+1; pos3++ )
{
a[lb+pos3] = temp[pos3];
}
delete [] temp;
}
void mergeSort( int *a, int lb, int rb )
{
int split;
if( lb < rb ) // если есть более 1 элемента происходит деление
{
split = (lb + rb)/2; // делим массив
mergeSort( a, lb, split ); // сортировать левую половину
mergeSort( a, split+1, rb ); // сортировать правую половину
merge( a, lb, split, rb ); // слить результаты в общий массив
}
}
int main()
{
int mass[]={ 1, -20, 8, 9, 0, 2, 7, 3, 10 };
mergeSort( mass, 0, 9 );
for( int i=0; i<9; i++ )
{
cout << mass[ i ] << " ";
}
return 0;
}
|
|
