Добрый день.Я столкнулся с необходимостью освоить некоторые методы сортировки,такие как Быстрая сортировка,Сортировка Слиянием,Пирамидальная Сортировка и Порязрядная Сортировка.
И,если с первой всё понятно,то с другими не всё так прозрачно.Прошу помочь разобраться в некоторых кусочках кодов,реализующих данные методы сортировки.
Сортировка Слиянием
#include <iostream>
#include <conio.h>
using namespace std;
template <class T>
T* merge(T *m1, T* m2, int l1, int l2){
T* ret = new T[l1+l2];
int n = 0;
// Сливаем массивы, пока один не закончится
while (l1 && l2){
if (*m1 < *m2){
ret[n] = *m1;
m1++; l1--;}
else {
ret[n] = *m2;
m2++; l2--;}
n++;}
// Если закончился первый массив
if (l1 == 0){
for (int i=0; i<l2; i++){
ret[n++] = *m2++;}}
// Если закончился второй массив
else {
for (int i=0; i<l1; i++){
ret[n++] = *m1++;}}
return ret;}
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len){
int n=1, l, ost;
T * mas1;
while (n<len){
l=0;
while (l<len){
if (l+n >= len) break;
ost = (l+n*2>len) ? (len-(l+n)) : n;
mas1 = merge(mas+l, mas+l+n, n, ost);
for (int i=0; i<n+ost; i++) mas[l+i] = mas1[i];
delete [] mas1;
l+=n*2;}
n*=2;
}}
int main()
{
float a[128];int dl;
cout<<"Vvedite coli4estvo 4lenov v massive\n";
cin>>dl;
cout<<"Vvedite massiv\n";
for(int i=0;i<dl;i++)
{ cin>>a[i];}
mergeSort(a, dl);
for(int i=0;i<dl;i++)
cout<<" "<<a[i];
system("PAUSE");
getch();
}
Непонятна функция mergeSort,а именно что за переменные такие l,n,ost и len.
Пирамидальная Сортировка
#include <iostream>
using namespace std;
template<typename T>
void downHeap(T a[], long k, long n) {
// процедура просеивания следующего элемента
// До процедуры: a[k+1]...a[n] - пирамида
// После: a[k]...a[n] - пирамида
T new_elem;
long child;
new_elem = a[k];
while(k <= n/2) { // пока у a[k] есть дети
child = 2*k;
// выбираем большего сына
if( child < n && a[child] < a[child+1] )
child++;
if( new_elem >= a[child] ) break;
// иначе
a[k] = a[child]; // переносим сына наверх
k = child;
}
a[k] = new_elem;
}
template<typename T>
void heapSort(T a[], long size) {
long i;
T temp;
// строим пирамиду
for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1);
// теперь a[0]...a[size-1] пирамида
for(i=size-1; i > 0; i--) {
// меняем первый с последним
temp=a[i]; a[i]=a[0]; a[0]=temp;
// восстанавливаем пирамидальность a[0]...a[i-1]
downHeap(a, 0, i-1);
}
}
int main()
{
int arr[5] = {9,2,3,1,5};
heapSort(arr,5);
cout<<"[ ";
for(int i = 0; i < 5; ++i)
cout<<arr[i]<<" ";
cout<<"]"<<endl;
system("PAUSE");
return 0;
}
Здесь непонятна DownHeap,а конкретно,что с чем сравнивается в if'ах и почему child = 2*k.
Подскажите,пожалуйста,что к чему...Заранее благодарю!
