#ifndef MERGESORT_H
#define MeRGESORT_H
#include <cmath>
#include <vector>
namespace MyNameSpace
{
typedef int (*comparefunc)(void* , void*, void*);
template<typename T>
void merge(std::vector<T>& array, comparefunc compare, void* userDefinedObject, int start, int middle, int end)
{
int leftLength = middle - start + 1;
int rightLength = end - middle;
T left[leftLength];
T right[rightLength];
int i;
int j;
for (i = 0; i < leftLength; ++i)
{
left[i] = array[start + i];
}
for (j = 0; j < rightLength; ++j)
{
right[j] = array[middle + j + 1];
}
i = 0;
j = 0;
for (int k = start; k <= end; ++k)
{
T leftElement = left[i];
T rightElement = right[j];
if (i < leftLength && (j >= rightLength || compare(&leftElement, &rightElement, userDefinedObject) <= 0))
{
array[k] = leftElement;
++i;
} else if (j < rightLength)
{
array[k] = rightElement;
++j;
}
}
}
template<typename T>
void sort(std::vector<T>& array, comparefunc compare, void* userDefinedObject, int start, int end)
{
if (start >= end)
{
return;
}
int middle = std::floor((start + end) * 0.5);
sort(array, compare, userDefinedObject, start, middle);
sort(array, compare, userDefinedObject, middle + 1, end);
merge(array, compare, userDefinedObject, start, middle, end);
}
template<typename T>
void mergeSort(std::vector<T>& array, comparefunc comparator, void* userDefinedObject)
{
int left = 0;
int right = array.size() - 1;
sort(array, comparator, userDefinedObject, left, right);
}
}
#endif
--------------------------------------------------- 实际测试-----------------------------------------------------------------------
int main(void) {
{
int array[]={0, 9, 1, 8, 2, 7, 3, 6, 4, 5};
std::vector<int> testVector(array, array+ sizeof(array)/sizeof(array[0]));
mergeSort(testVector, compare_sorts, &userDefinedObject);
int expected[]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for(int i=0; i<sizeof(array)/sizeof(array[0]); ++i)
{
if(array[i] != expected[i])
{
cout << "sorts: "<<i<<endl;
}
}
}
{
Node array[] = {Node(5,0), Node(10,1), Node(5,2), Node(0,3)};
std::vector<Node> testVector(array, array + sizeof(array)/sizeof(array[0]));
mergeSort(testVector, compare_stableSorts, &userDefinedObject);
Node expected[]={Node(0,3), Node(5,0), Node(5,2), Node(10,1)};
for(int i=0; i<sizeof(array)/sizeof(array[0]); ++i)
{
if(array[i].value != expected[i].value || array[i].index != expected[i].index)
{
cout << "stable sorts:" << i << endl;
}
}
}
{
BoundingSphere array[]={BoundingSphere(Cartesian3(-2.0, 0.0, 0.0), 1.0),
BoundingSphere(Cartesian3(-1.0, 0.0, 0.0), 1.0),
BoundingSphere(Cartesian3(-3.0, 0.0, 0.0), 1.0)
};
BoundingSphere expected[]={BoundingSphere(Cartesian3(-3.0, 0.0, 0.0), 1.0),
BoundingSphere(Cartesian3(-2.0, 0.0, 0.0), 1.0),
BoundingSphere(Cartesian3(-1.0, 0.0, 0.0), 1.0),
};
std::vector<BoundingSphere> testVector(array, array + sizeof(array)/sizeof(array[0]));
mergeSort(testVector, compare_object, &userDefinedObject);
for(int i=0; i<sizeof(array)/sizeof(array[0]); ++i)
{
if(!(array[i].equals( expected[i])))
{
cout << "sorts with user defined object:" << i << endl;
}
}
}
}