# 帮小弟我看看一个排序有关问题(3)

www.MyException.Cn  网友分享于：2013-03-08  浏览：18次

//递归调用实现快速排序函数
template <typename T>
void QuickSort(T * pA, int p, int r)
{
if(p < r)
{
int q;
q = Partition(pA, p, r);
QuickSort(pA, p, q-1);
QuickSort(pA, q+1, r);
}
}
//---------------------------------------------------

//=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
//归并排序算法
//=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
//将两个数组a[], b[]合并为一个数组c[]
void mergeAB(int c[], int cl,
int a[], int al, int ar,
int b[], int bl, int br )
{
int i = al, j = bl;

for (int k = cl; k < cl+ar-al+br-bl+1; ++k)
{
if (i > ar) {c[k] = b[j++]; continue;}
if (j > br) {c[k] = a[i++]; continue;}
c[k] = ( a[i] < b[j] ) ? a[i++]: b[j++];
}
}

//两路归并排序
template <typename T>
void merage(T * a, int al, int am, int ar)
{
T * b = new T[ar - al +1];
int i = al, j = am + 1;

for(int k=0; k < ar - al + 1; ++k)
{
if(i > am) { b[k] = a[j++]; continue; }
if(j > ar) { b[k] = a[i++]; continue; }
b[k] = (a[i] < a[j]) ? a[i++]: a[j++];
}
for(int m=0; m < ar - al + 1; ++m)
a[m+al] = b[m];

delete [] b;
}

//归并排序算法
template <typename T>
void mergesort(T *R, int L, int H)
{
int M;
if(L < H)
{
M = (H + L)/2 ;
mergesort(R, L, M);
mergesort(R, M+1, H);
merage <T> (R, L, M, H);
}
}
//--------------------------

//=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
//堆排序算法
//=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
//取左孩子索引
int left(int i)
{
return i*2;
}

//取右孩子索引
int right(int i)
{
return i*2 + 1;
}

//通过递归将节点i的值插入到堆的合适位置
// A:0--arraysize-1,i代表数组从0开始的第几个元素，如a[2]为第3个元素
template <typename T>
void heapify(T Array[], int heap_size, int i)
{

T temp;
int lIndex, rIndex, largest;
lIndex = left(i); //取节点i的左孩子索引
rIndex = right(i); //取节点i的右孩子索引

if (lIndex <=heap_size && (Array[lIndex-1] > Array[i-1]))
largest = lIndex;
else
largest = i;

if(rIndex <=heap_size && Array[rIndex-1]> Array[largest-1])
largest = rIndex;

if(largest !=i)
{
temp = Array[largest-1];
Array[largest-1] = Array[i-1];
Array[i-1] = temp;
if(2*largest > heap_size) //左孩子为空时返回,达最大递归深度
return;
}
else //largest等于i时不需要在进行递归
return;

heapify(Array, heap_size, largest);
}

//建立堆
template <typename T>
void BuildHeap(T Array[], int size)
{
for(int i= size/2+1; i > = 1; --i)
heapify <T> (Array, size, i);
}

// 堆排序函数
template <typename T>
void HeapSort(T Array[], int size)
{
int heap_size = size;
BuildHeap <T> (Array, size);
for(int i = size; i > = 2 ; --i)
{
swap(Array[0], Array[i-1]);
heap_size = heap_size -1;
heapify <T> (Array, heap_size, 1);
}

}
//---------------------------

//交换函数
template <typename T>
inline void mySwap(T& a,T& b)
{
T temp(a);
a = b;
b = temp;
}

//***************************************************