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

数据结构程序报告（5）1.需求分析：（1）堆排序、快速排序、基数排序（静态链表）输出一组数组【1】堆排序：○1对所有纪录建立最大堆○2取出堆顶的最大纪录与数组末端的纪录交换，最大记录在下边n-1的位置，原数组末端元素临时处于根结点；将根元素向下调整到合适的位置，即剩下的n-1个记录重新调整为堆，再取新堆顶最大的记录，与数组n-2为交换；…；不断重复这一操作，直到堆为空。这时数组正好是从小到大排序。【2】快速排序：○1从待排序序列S中任意选择一个记录k作为轴值。○2将剩余的记录分割成左子序列L和右子序列R。○3L中所有记录都小于或等于k，R中记录都大于等于k，因此k正好位于正确的位置。○4对子序列L和R递归进行快速排序，直到子序列中只含有0或1个元素，推出递归。【3】基数排序：○1高位优先法（MSD）分配排序。○2低位优先法（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（）限行时间整理静态链表，使得数组按下标有序。附程序：#includeiostream#includestdlib.h#includetime.husingnamespacestd;#defineMAX100templateclassRecordvoidQuickSort(RecordArray[],intleft,intright)//快速排序{if(right=left)return;intp=(left+right)/2;swap(Array,p,right);p=Partition(Array,left,right);QuickSort(Array,left,p-1);QuickSort(Array,p+1,right);}templateclassRecordvoidswap(RecordArray[],intp,intright)//交换两个数{Recordtemp;temp=p;p=right;right=temp;}templateclassRecordintPartition(RecordArray[],intleft,intright)//分割函数{intl=left;intr=right;RecordTempRecord=Array[r];while(l!=r){while(Array[l]=TempRecord&&lr)l++;if(lr){Array[r]=Array[l];r--;}while(Array[r]=TempRecord&&lr)r--;if(lr){Array[l]=Array[r];l++;}}Array[l]=TempRecord;returnl;}templateclassTclassMaxHeap//堆类型{public:T*heapArray;intCurrentSize;MaxHeap(T*Array,intn);voidBuildHeap();intLeftChild(intpos);voidSiftdown(intleft);T&RemoveMax();};templateclassTMaxHeapT::MaxHeap(T*Array,intn)//构造函数{if(n=0)return;CurrentSize=n;heapArray=Array;BuildHeap();}templateclassTvoidMaxHeapT::BuildHeap()//建堆{for(inti=CurrentSize/2-1;i=0;i--)Siftdown(i);}templateclassTintMaxHeapT::LeftChild(intpos){//返回左孩子return2*pos+1;}templateclassTvoidMaxHeapT::Siftdown(intleft)//从left开始想向下筛选{inti=left;intj=LeftChild(i);Ttemp=heapArray[i];while(jCurrentSize){if((jCurrentSize-1)&&(heapArray[j]heapArray[j+1]))j++;if(tempheapArray[j]){heapArray[i]=heapArray[j];i=j;j=LeftChild(j);}elsebreak;}heapArray[i]=temp;}templateclassTT&MaxHeapT::RemoveMax()//从堆顶删除最大值{if(CurrentSize==0)//判断非空{coutCan'tdeleteendl;exit(1);}else{//交换并向下筛选Ttemp;temp=heapArray[0];heapArray[0]=heapArray[--CurrentSize];heapArray[CurrentSize]=temp;if(CurrentSize1)Siftdown(0);returnheapArray[CurrentSize];}}templateclassRecordvoidsort(RecordArray[],intn)//堆排序{MaxHeapRecordmax_heap=MaxHeapRecord(Array,n);//依次找出最大记录for(inti=0;in-1;i++)max_heap.RemoveMax();}classRecord{public:intkey;intnext;};classstaticqueue{public:inthead;inttail;};templateclassRecord//静态链实现基数排序，n为数组长度，d为排序码个数，r为基数voidradixsort(Record*arra,intn,intd,intr){inti,first=0;staticqueue*queue=newstaticqueue[r];for(i=0;in-1;i++)arra[i].next=i+1;arra[n-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);}templateclassRecordvoiddistribute(Record*arra,intfirst,inti,intr,staticqueue*queue){intj,k,a,curr=first;for(j=0;jr;j++)queue[j].head=-1;while(curr!=-1){k=arra[curr].key;for(a=0;a1;a++)k=k/r;k=k%r;if(queue[k].head==-1)queue[k].head=curr;elsearra[queue[k].tail].next=curr;queue[k].tail=curr;curr=arra[curr].next;}}templateclassRecordvoidcollect(Record*arra,int&first,intr,staticqueue*queue){intlast,k=0;while(queue[k].head==-1)k++;first=queue[k].head;last=queue[k].tail;while(kr-1){k++;while(kr-1&&queue[k].head==-1)k++;if(queue[k].head!=-1){arra[last].next=queue[k].head;last=queue[k].tail;}}arra[last].next=-1;}templateclassRecordvoidaddrsort(Record*arra,intn,intfirst){inti,j;j=first;Recordtemprec;for(i=0;in-1;i++){temprec=arra[j];arra[j]=arra[i];arra[i]=temprec;arra[i].next=j;j=temprec.next;while(j=i)j=arra[j].next;}}voidmain(){inti,m,n,k;int*array;cout输入个数:;cinn;array=newint[n];cout输入数组;for(i=0;in;i++){cinarray[i];}QuickSort(array,0,n-1);cout快速排序：;for(i=0;in;i++)coutarray[i];coutendlendl;cout输入个数:;cinm;array=newint[m];cout输入数组:;for(i=0;im;i++){cinarray[i];}sort(array,m);cout堆排序:;for(i=0;im;i++)coutarray[i];coutendlendl;cout输入个数:;cink;Record*arra=newRecord[k];cout输入数组:;for(i=0;ik;i++){cinarra[k].key;}radixsort(arra,k,2,10);cout基数排序:;for(i=0;ik;i++)coutarra[i].key;system(pause);}3.测试截图：4.总结：程序调试中的问题及解决方法：快速排序直接运用书上的算法，堆排序在建堆的过程需要修改书上的最小堆建立方法，基数排序运用书上的算法也可以很快的编出程序，总的来说这次上机题不算太难心得体会：经过这次编程，我意识到了数据结构这本书的重要性，有很多算法背很难背下来，这种工具书就是用来查资料的，具体的算法都在书上，直接用到程序中就ok了，还有就是对各种排序方法有了更深的理解