Сортировка слиянием

Август 15th, 2011 § 0 comments

Сортировка слиянием относиться к классу алгоритмов “разделяй и властвуй”. Является устойчивой. Сложность алгоритма O(n*log(n)), требует выделение дополнительной памяти. Алгоритм изобретен Джоном фон Нейманом в 1945г. Ниже приведен код реализации.


void merge(int*src,int left,int middle,int right)
{
 int* aux = new int[right-left];
 int i=left;
 int j=middle+1;
 int index=0;

 for(int k=left;k<=right;k++)
 {
 if(i>middle)
 {
 aux[index]=src[j];
 j++;
 }else if(j>right)
 {
 aux[index]=src[i];
 i++;
 }else if(src[i]<src[j])
 {
 aux[index]=src[i];
 i++;
 }else
 {
 aux[index]=src[j];
 j++;
 }
 index++;
 }
for(int k=0;k<=right-left;k++)
 src[k+left]=aux[k];

}
void MergeSort(int* src,int left,int right)
{
 if(left>=right)
 return;
 int middle = (right+left)/2;
 MergeSort(src,left,middle);
 MergeSort(src,middle+1,right);
 merge(src,left,middle,right);

}

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля отмечены *

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Смотреть фильмы онлайн