堆排序、快速排序、基数排序（静态链表）输出一组数组(2)

}

}

Array[l]=TempRecord;

return l;

}

template class MaxHeap

//堆类型

{ public: T *heapArray; intCurrentSize;

MaxHeap(T *Array,int n); voidBuildHeap(); intLeftChild(intpos); voidSiftdown(int left); T&RemoveMax();

};

template

MaxHeap::MaxHeap(T *Array,int n)

{

//构造函数

}

if(n<=0)

return;

CurrentSize=n; heapArray=Array; BuildHeap();

template

void MaxHeap::BuildHeap() { }

template

intMaxHeap::LeftChild(intpos){ }

template

void MaxHeap::Siftdown(int left) {

//从left开始想向下筛选

return 2*pos+1;

//返回左孩子

for(int i=CurrentSize/2-1;i>=0;i--)

Siftdown(i);

//建堆

}

int i=left; int j=LeftChild(i); T temp=heapArray[i]; while(j

heapArray[i]=temp;

if((j

j++;

if(temp

else break;

heapArray[i]=heapArray[j]; i=j;

j=LeftChild(j);

template

T&MaxHeap::RemoveMax() //从堆顶删除最大值 {

if(CurrentSize==0) {

//判断非空

cout<<\ exit(1);

}

else{ //交换并向下筛选

T temp;

temp=heapArray[0];

heapArray[0]=heapArray[--CurrentSize]; heapArray[CurrentSize]=temp; if(CurrentSize>1)

Siftdown(0);

returnheapArray[CurrentSize];

}

}

template void sort(Record Array[],int n)

//堆排序

{

MaxHeapmax_heap=MaxHeap(Array,n);

最大记录 for(int i=0; i

max_heap.RemoveMax();

}

//依次找出

class Record{ public: };

classstaticqueue{ public: };

template r为基数

voidradixsort(Record *arra,intn,intd,int r){

inti,first=0;

staticqueue *queue=new staticqueue[r]; for(i=0;i

//静态链实现基数排序，n为数组长度，d为排序码个数，

int head; int tail;

int key; int next;