堆排序、快速排序、基数排序(静态链表)输出一组数组.doc

数据结构程序报告（5） 1. 需求分析：（1）堆排序、快速排序、基数排序（静态链表）输出一组数组【1】堆排序：对所有纪录建立最大堆 取出堆顶的最大纪录与数组末端的纪录交换，最大记录在下边n-1的位置，原数组末端元素临时处于根结点；将根元素向下调整到合适的位置，即剩下的n-1个记录重新调整为堆，再取新堆顶最大的记录，与数组n-2为交换；不断重复这一操作，直到堆为空。这时数组正好是从小到大排序。【2】快速排序：从待排序序列S中任意选择一个记录k作为轴值。将剩余的记录分割成左子序列L和右子序列R。L中所有记录都小于或等于k，R中记录都大于等于k，因此k正好位于正确的位置。对子序列L和R递归进行快速排序，直到子序列中只含有0或1个元素，推出递归。 【3】基数排序：高位优先法（MSD）分配排序。 低位优先法（LSD）分配排序。 从最低位k0开始排序，对于排好的序列再用次低位k1排序，依次重复，直至对最高位kd-1排好序后，整个序列成为有序的。这是一个分、收；分、收 .的过程。（2）输入输出要求：输入数组个数： 输入数组：快速排序：输入数组个数：输入数组：堆排序：输入数组个数：输入数组：基数排序：2. 算法设计： （1） QuickSort（）快速排序函数，Array 为待排序数组，left、right分别为数组两端，选择轴值p，分割前先将轴值放到数组末端，分割后轴值到达正确位置，对轴值左边和右边的子序列进行递归快速排序。（2） swap（）交换2个数。（3） Partition（）分割函数，定义l为左指针，r为右指针，开始分割l、r不断向中间移动，直到相遇。（4） MaxHeap（）最大堆类定义，包括BuildHeap（）建堆，LeftChild（）返回左孩子位置，Shiftdown（）从left开始向下筛选，RemoveMax（） 堆顶删除最大值（5） sort（）堆排序，依次找出最大记录，即堆顶。（6） radixsort（）静态链实现基数排序，n为数组长度，d为排序码个数，r为基数。（7） distribute（）分配过程，A中存放待排序记录，first为静态链中的第一个记录，i为第i个排序码，r为基数。（8） collect（）收集过程，Arra中存放待排序记录，first为静态链中的第一个记录，r为基数。（9） addrsort（）限行时间整理静态链表，使得数组按下标有序。附程序：#include#include #include using namespace std;#define MAX 100templatevoid QuickSort(Record Array,int left,int right)/快速排序if (right=left) return; int p=(left+right)/2; swap(Array,p,right); p=Partition(Array,left,right); QuickSort(Array,left,p-1); QuickSort(Array,p+1,right); templatevoid swap(Record Array,int p,int right)/交换两个数Record temp;temp=p;p=right;right=temp;template int Partition(Record Array,int left,int right) /分割函数 int l=left; int r=right; Record TempRecord=Arrayr; while(l!= r) while(Arrayl=TempRecord & lr) l+; if (l=TempRecord&lr) r-; if (lr) Arrayl=Arrayr; l+; Arrayl=TempRecord; return l; templateclass MaxHeap/堆类型public:T *heapArray;int CurrentSize;MaxHeap(T *Array,int n);void BuildHeap();int LeftChild(int pos);void Siftdown(int left); T& RemoveMax();templateMaxHeap:MaxHeap(T *Array,int n)/构造函数if(n=0)return;CurrentSize=n;heapArray=Array;BuildHeap();templatevoid MaxHeap:BuildHeap()/建堆for(int i=CurrentSize/2-1;i=0;i-)Siftdown(i);templateint MaxHeap:LeftChild(int pos)/返回左孩子return 2*pos+1;templatevoid MaxHeap:Siftdown(int left)/从left开始想向下筛选int i=left;int j=LeftChild(i);T temp=heapArrayi;while(jCurrentSize)if(jCurrentSize-1)&(heapArrayjheapArrayj+1)j+;if(tempheapArrayj)heapArrayi=heapArrayj;i=j;j=LeftChild(j);else break;heapArrayi=temp;templateT& MaxHeap:RemoveMax()/从堆顶删除最大值if(CurrentSize=0)/判断非空coutCant delete1)Siftdown(0);return heapArrayCurrentSize;template void sort(Record Array,int n)/堆排序 MaxHeap max_heap=MaxHeap(Array,n);/依次找出最大记录for(int i=0; in-1; i+) max_heap.RemoveMax();class Recordpublic:int key;int next;class staticqueuepublic:int head;int tail;template/静态链实现基数排序，n为数组长度，d为排序码个数，r为基数void radixsort(Record *arra,int n,int d,int r)int i,first=0;staticqueue *queue=new staticqueuer;for(i=0;in-1;i+)arrai.next=i+1;arran-1.next=-1;for(i=0;id;i+)distribute(arra,first,i,r,queue);collect(arra,first,r,queue);delete queue;addrsort(arra,n,first);templatevoid distribute(Record *arra,int first,int i,int r,staticqueue *queue)int j,k,a,curr=first;for(j=0;jr;j+)queuej.head=-1;while(curr!=-1)k=arracurr.key;for(a=0;a1;a+)k=k/r;k=k%r;if(queuek.head=-1)queuek.head=curr;else arraqueuek.tail.next=curr;queuek.tail=curr;curr=arracurr.next;templatevoid collect(Record *arra,int& first,int r,staticqueue *queue)int last,k=0;while(queuek.head=-1)k+;first=queuek.head;last=queuek.tail;while(kr-1)k+;while(kr-1&queuek.head=-1)k+;if(queuek.head!=-1)arralast.next=queuek.head;last=queuek.tail;arralast.next=-1;templatevoid addrsort(Record *arra,int n,int first)int i,j;j=first;Record temprec;for(i=0;in-1;i+)temprec=arraj;arraj=arrai;arrai=temprec;arrai.next=j;j=temprec.next;while(j=i)j=arraj.next;void main()int i,m,n,k;int *array;coutn;array=new intn;cout输入数组;for(i=0;iarrayi;QuickSort(array,0,n-1);cout快速排序：;for(i=0;in;i+)coutarrayi ;coutendlendl;coutm;array=new intm;cout输入数组:;for(i=0;iarrayi;sort(array,m);cout堆排序:;for(i=0;im;i+)coutarrayi ;coutendlendl;coutk;Record *arra=new Recordk;cout输入数组:;for(i=0;iarrak.key;radixsort(arra,k,2,10);cout基数排序:;for(i=0;ik;i+)coutarrai.key ;s