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

《堆排序、快速排序、基数排序(静态链表)输出一组数组》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

数据结构程序报告（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）输入输出要求：输入数组个数：输入数组：快速排序：输入数组个数：输入数组： 堆排序：输入数组个数：输入数组：基数排序：1.算法设计：（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#includeusingnamespacestd;#defineMAX100templatevoidQuickSort(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);}templatevoidswap(RecordArray[],intp,intright)//交换两个数{Recordtemp;temp=p;p=right; right=temp;}templateintPartition(RecordArray[],intleft,intright)//分割函数{intl=left;intr=right;RecordTempRecord=Array[r];while(l!=r){while(Array[l]<=TempRecord&&l=TempRecord&&lclassMaxHeap//堆类型{public:T*heapArray;intCurrentSize;MaxHeap(T*Array,intn);voidBuildHeap();intLeftChild(intpos);voidSiftdown(intleft);T&RemoveMax();};templateMaxHeap::MaxHeap(T*Array,intn)//构造函数{ if(n<=0)return;CurrentSize=n;heapArray=Array;BuildHeap();}templatevoidMaxHeap::BuildHeap()//建堆{for(inti=CurrentSize/2-1;i>=0;i--)Siftdown(i);}templateintMaxHeap::LeftChild(intpos){//返回左孩子return2*pos+1;}templatevoidMaxHeap::Siftdown(intleft)//从left开始想向下筛选{ inti=left;intj=LeftChild(i);Ttemp=heapArray[i];while(jT&MaxHeap::RemoveMax()//从堆顶删除最大值{if(CurrentSize==0)//判断非空{ cout<<"Can'tdelete"<1)Siftdown(0);returnheapArray[CurrentSize];}}templatevoidsort(RecordArray[],intn)//堆排序{MaxHeapmax_heap=MaxHeap(Array,n);//依次找出最大记录for(inti=0;i//静态链实现基数排序，n为数组长度，d为排序码个数，r为基数voidradixsort(Record*arra,intn,intd,intr){inti,first=0;staticqueue*queue=newstaticqueue[r];for(i=0;ivoiddistribute(Record*arra,intfirst,inti,intr,staticqueue*queue){intj,k,a,curr=first;for(j=0;jvoidcollect(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(kvoidaddrsort(Record*arra,intn,intfirst){inti,j;j=first;Recordtemprec;for(i=0;i>n; array=newint[n];cout<<"输入数组";for(i=0;i>array[i];}QuickSort(array,0,n-1);cout<<"快速排序：";for(i=0;i>m;array=newint[m];cout<<"输入数组:";for(i=0;i>array[i];}sort(array,m);cout<<"堆排序:"; for(i=0;i>k;Record*arra=newRecord[k];cout<<"输入数组:";for(i=0;i>arra[k].key;}radixsort(arra,k,2,10);cout<<"基数排序:";for(i=0;i