数据结构项目八课件

数据结构项目八共分为五个任务.项目八排序任务一排序的相关概念任务二插入排序任务三交换排序任务四选择排序任务五归并排序和基数排序.任务一排序的相关概念1．排序2．数据元素的存储结构3．算法的稳定性4．算法的评价.1．排序排序是指将一个数据元素的任意序列按关键字的递增或递减次序重新排列起来，使其成为一个按关键字有序排列的序列。内部排序是指将待排数据元素完全放置在内存中进行排序的方法。外部排序是指因待排数据元素数量太大，排序过程中不仅需要使用内存，还要借助外部存储器来完成的排序方法。.2．数据元素的存储结构数据元素可有3种存储结构：顺序结构、链式结构和地址向量结构。排序过程中一定要移动数据元素排序过程中不用移动数据元素，而只需要修改指针指将数据元素顺序存储的同时，另设一个指示各个数据元素位置的地址向量，这样在排序过程中不用移动数据元素，而只需修改地址向量中数据元素的“地址”即可顺序结构的数据类型定义如下：#defineMAXSIZE100 //顺序表的最大长度typedefstruct {KeyTypekey; //关键字项OtherTypeotheritem; //另外的数据项}RecordType;typedefstruct {RecordTyper[MAXSIZE+1];//定义数据元素数组，r[0]为哨兵单元intlength; //顺序表长度}SeqList;.3．算法的稳定性如果待排序的数据元素序列中有两个数据元素的关键字的值相同，经过排序后，两个数据元素的相对次序保持不变，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。关键字序列（35，2，15，6，81，6*）结果序列为（2，6，6*，15，35，81）表示为稳定的排序方法结果序列为（2，6*，6，15，35，81）表示为不稳定的排序方法.4．算法的评价可以从两个方面来评价某种排序算法的优劣：通过排序过程中所需的内存辅助空间的多少来衡量。通过排序过程中关键字的比较次数和数据元素的移动次数来反映。①空间复杂度：②时间复杂度：.任务二插入排序一、直接插入排序二、折半插入排序三、希尔排序.1．基本思想2．算法实现一、直接插入排序3．算法分析.1．基本思想将待排数据元素插入到已排好序的有序表中，从而得到一个新的有序表。对于一个具有n个数据元素的序列，进行直接插入排序具体过程：①将第1个数据元素看作一个已排好序的有序表。②将第i（2≤i≤n）个数据元素的关键字Ki依次与其前面数据元素的关键字Ki－1、Ki－2、…、K1进行比较，将所有关键字大于Ki的数据元素依次向后移动一个位置，直到某个数据元素的关键字Kj小于或者等于Ki时，将第i个数据元素插入到关键字为Kj的数据元素后面，即完成第i个数据元素的插入。③经过n－1次插入操作后，所有数据元素构成一个按关键字值大小排列的有序序列。.数据元素序列{35，66，2，15，6，81，6*，9}进行直接插入排序的过程：.2．算法实现voidInsertSort(SeqList *L)//对顺序表L作直接插入排序{inti,j;for(i=2;i<=L->Length;i++)//从第二个数据元素开始排序if(L->r[i].key<L->r[i-1].key) {//如果第i个数据元素的关键字小于其前面数据元素的关键字，则将其插入到有序表中L->r[0]=L->r[i]; //将待插入数据元素存入r[0]作为监视哨//搜索插入位置，将有序表中大于待排关键字的数据元素后移for(j=i-1;L->r[0].key<L->r[j].key;j--)L->r[j+1]=L->r[j]; L->r[j+1]=L->r[0]; }}//将待排数据元素插入到第j个数据元素之后.3．算法分析（1）空间复杂度排序过程中仅使用了一个辅助单元r[0]，算法的空间复杂度为O(1)。（2）时间复杂度直接插入排序的时间复杂度为O(n2)。（3）稳定性直接插入排序是一种稳定的排序算法。.二、折半插入排序1．算法实现2．算法分析.1．算法实现通过对有序表进行折半查找来确定插入位置，以减少关键字比较的次数。算法描述如下：voidBinSort(SeqList*L){//对顺序表L作折半插入排序inti,j;intlow,high,mid;for(i=2;i<=L->length;i++) //从第2个元素开始排序{L->r[0]=L->r[i]; //将待插入数据元素存入r[0]作为监视哨low=1;high=i-1; //设置初始查找区间while(low<=high) //搜索插入位置{mid=(low+high)/2; //求中间位置if(L->r[0].key<L->r[mid].key)high=mid–1;//在前半部分查找elselow=mid+1;} //在后半部分查找for(j=i-1;j>=low;j--) //将插入位置以后的数据元素后移L->r[j+1]=L->r[j];L->r[low]=L->r[0];}} //插入数据元素.2．算法分析（1）空间复杂度（2）时间复杂度（3）稳定性排序过程中仅使用了一个辅助单元r[0]，算法的空间复杂度为O(1)。折半插入排序的时间复杂度为O(n2)。折半插入排序是一种稳定的排序算法。.三、希尔排序1．基本思想2．算法实现3．算法分析.1．基本思想将待排序数据元素划分成若干个子序列，其中每个子序列由相隔某个“增量”的数据元素组成，然后对这些子序列分别进行直接插入排序，通过缩小“增量”对子序列进行调整。当整个序列基本有序时，对全部数据元素进行一次直接插入排序。具体过程：①按选定增量d1（d1＜n），将所有距离为d1的数据元素划分为一个子序列，对各个子序列进行直接插入排序。②选定增量d2（d2＜d1），对所有数据元素重新进行划分并对各子序列直接插入排序。③重复以上操作，直到增量di＝1，即将所有数据元素放在一个子序列中进行一次直接插入排序，最后得到所有数据元素按关键字有序排列的序列。.2．算法实现voidShellInsert(SeqList *L,intdi) {//对顺序表L作一趟希尔排序，di为增量inti,j;for(i=di+1;i<=L->Length;i++)if(L->r[i].key<L->r[i-di].key){//将第i个数据元素插入有序子序列L->r[0]=L->r[i]; //将第i个数据元素存入r[0]作为监视哨//查找插入位置，将子序列内插入位置后的数据元素后移for(j=i-di;j>0&&L->r[0].key<L->r[j].key;j=j-di)L->r[j+di]=L->r[j];L->r[j+di]=L->r[0];}}//插入数据元素.voidShellSort(SeqList*L,intd[],intt){//按增量序列d[]对顺序表L作t趟希尔排序intk;for(k=0;k<t;k++)ShellInsert(L,d[k]); //一趟增量为d[k]的希尔排序}.3．算法分析（1）空间复杂度（2）时间复杂度（3）稳定性排序过程中仅使用了一个辅助单元，算法的空间复杂度为O(1)。希尔排序是一种不稳定的排序算法。在数据量较少时，利用直接插入排序的效率较高；当待排序的数据元素数目较大时，希尔排序方法一般要比直接插入排序方法快。.任务三交换排序一、冒泡排序二、交换排序.一、冒泡排序1．基本思想2．算法实现3．算法分析.1．基本思想从头扫描待排序的数据元素序列，依次比较相邻两个数据元素的关键字大小，如果逆序，则交换它们的位置，逐步将待排序列变成有序序列。具体过程：①对待排序数据元素序列进行第一趟扫描，依次比较相邻两个数据元素的关键字大小，如果前面数据元素的关键字大于后面数据元素的关键字，就将它们交换，这样具有较大关键字的数据元素将不断后移，最后，具有最大关键字的数据元素移动到最后一个位置上；②第二趟扫描仅需对前n－1个数据元素进行，重复以上操作，使具有次大关键字的数据元素移动到第n－1个位置；③依此类推，直到某一趟扫描过程中没有发生数据元素的交换，则可结束冒泡排序。.对数据元素序列（35，66，2，15，6，81，6*，9）进行冒泡排序：.2．算法实现voidBubbleSort(SeqList *L)//对顺序表L作冒泡排序{inti,j,change;change=TRUE; //设置交换标志，初始值为TRUEfor(i=1;i<L->Length&&change;i++)//进行冒泡排序，无交换时结束{change=FALSE; //设置交换标志为FALSEfor(j=1;j<=L->Length-i;j++)//对未排好序的数据元素排序if(L->r[j].key>L->r[j+1].key)//比较相邻两个数据元素的大小{L->r[0]=L->r[j]; //要交换的数据元素暂时存入r[0]中L->r[j]=L->r[j+1];L->r[j+1]=L->r[0];change=TRUE;}}} //设置交换标志为TRUE.3．算法分析（1）空间复杂度（2）时间复杂度（3）稳定性冒泡排序过程中仅使用了一个辅助单元，算法的空间复杂度为O(1)。冒泡排序的时间复杂度为O(n2)。冒泡排序是一种稳定的排序算法。.二、快速排序1．基本思想2．算法实现3．算法分析.1．基本思想从待排数据元素序列中选取一个数据元素为基准，通过一趟扫描将待排序列分成两部分。其中一部分数据元素的关键字都小于或等于基准数据元素的关键字，而另一部分数据元素的关键字都大于或等于基准数据元素的关键字。对各部分不断划分，直到整个序列按关键字有序排列为止。.具体过程如下：①选取待排序列中的第一个数据元素为基准，将其复制到r[0]中，并令该位置为空；设置两个指针low和high，分别指向第一个数据元素和最后一个数据元素，即初始状态时r[low]为空。②从后向前扫描，若r[high]的关键字大于或等于基准关键字，则high向前移动一个位置，直到r[high]的关键字小于基准关键字时，将r[high]与r[low]交换。③从前向后扫描，若r[low]的关键字小于或等于基准关键字，则low向后移动一个位置，直到r[low]的关键字大于基准关键字时，将r[low]与r[high]交换。④重复步骤②和③，直至low＝high时，令r[low]＝r[0]，以r[low]为基准将待排序列划分为前后两部分，第一次划分完成。⑤按照以上方法，对各部分不断划分，直到各部分只有一个数据元素时，整个序列排序完成。.对数据元素序列（35，66，2，15，6，81，6*，9）进行一趟快速排序的过程：..2．算法实现intPartition(SeqList*L,intlow,inthigh){//以第一个数据元素为基准进行一趟快排，返回排序后基准数据元素的位置L->r[0]=L->r[low]; //以序列中第一个数据元素为基准while(low<high) //从序列两端交替向中间扫描{while(low<high&&L->r[high].key>=L->r[0].key)//从后向前扫描high--; //high指针前移L->r[low]=L->r[high];//将小于基准关键字的数据元素移到low所指位置while(low<high&&L->r[low].key<=L->r[0].key)//从前向后扫描low++; //low指针后移L->r[high]=L->r[low];}//将大于基准关键字的数据元素移到high所指位置L->r[low]=L->r[0]; //将基准数据元素移到low所指位置returnlow;} //返回排序后基准数据元素的位置voidQuickSort(SeqList*L,intlow,inthigh){//对顺序表L作快速排序intp;if(low<high) //表长度大于1{p=Partition(L,low,high);//对L进行一趟快速排序，返回基准数据元素的位置QuickSort(L,low,p-1); //对表的前半部分进行快速排序QuickSort(L,p+1,high); //对表的后半部分进行快速排序}}.3．算法分析（1）空间复杂度（2）时间复杂度（3）稳定性快速排序是一种不稳定的排序算法。最好情况下为O(log2n)，最坏情况下为O(n)。最好情况下为O(log2n)，最坏情况下为O(n2)，平均时间复杂度为O(nlog2n)。.任务四选择排序一、直接选择排序二、树形选择排序三、堆排序.一、直接选择排序1．基本思想2．算法实现3．算法分析.1．基本思想通过关键字的比较，每次从待排序列中选出关键字最小的数据元素，将其与待排序列的第一个数据元素交换，直到全部数据元素都有序排列。对于一个具有n个数据元素的序列，进行直接选择排序的具体过程是：①进行第一趟排序时，用r[1]与其余n－1个数据元素比较，选出关键字最小的数据元素与r[1]交换。②进行第二趟排序时，用r[2]与其余n－2个数据元素比较，选出关键字最小的数据元素与r[2]交换。③依此类推，进行第i趟排序时，用r[i]与其余n－i个数据元素比较，选出关键字最小的数据元素与r[i]交换。共需进行i－1趟选择，直到所有数据元素有序排列为止。.对数据元素序列（35，66，2，15，6，81，6*，9）进行直接选择排序的过程：.2．算法实现voidSelectSort(SeqList *L)//对顺序表L作直接选择排序{inti,j,t;for(i=1;i<L->Length;i++){进行第i趟排序时，选出待排序列中关键字最小的数据元素与r[i]交换t=i; //设置t的初值for(j=i+1;j<=L->Length;j++)if(L->r[j].key<L->r[t].key)//找到待排序列中关键字最小的数据元素t=j; //记录关键字最小的数据元素的下标if(t!=i) {//关键字最小的数据元素与第i个数据元素交换L->.r[0]=L->r[t];L->r[t]=L->r[i];L->.r[i]=L->r[0];}}}.3．算法分析（1）空间复杂度（2）时间复杂度（3）稳定性直接选择排序是一种不稳定的排序算法。排序过程中仅使用了一个辅助单元，算法的空间复杂度为O(1)。直接选择排序的平均时间复杂度为O(n2)。.二、树形选择排序2．算法分析1．基本思想.1．基本思想对待排序列的所有数据元素进行两两比较，选出每两个中的较小者，然后采取同样方法对这些较小者再进行两两比较，如此反复，直至选出关键字最小的数据元素并输出；将该数据元素置为∞，以便进行下一趟选择排序，……当所有数据元素全部输出，则排序完成。.对数据元素序列（35，66，2，15，6，81，6*，9）进行树形选择排序的过程如下：.2．算法分析（1）空间复杂度（2）时间复杂度（3）稳定性算法的空间复杂度为O(n)。时间复杂度为O(nlog2n)。树形选择排序是一种稳定的排序方法。.三、堆排序1．堆的定义2．基本思想3．算法实现4．算法分析.1．堆的定义n个关键字序列kl，k2，…，kn，当且仅当该序列满足如下性质时称为堆。.树中任一非叶子结点的关键字均不大于或不小于其左右孩子结点的关键字。其中，前者称为小顶堆，后者称为大顶堆。堆实质上是满足如下性质的完全二叉树：.2．基本思想将待排序列初始化为大顶堆（或小顶堆），然后将堆顶数据元素与最后一个叶子结点交换，输出该叶子结点表示的数据元素；然后将剩余的数据元素重新调整为大顶堆（或小顶堆），重复以上操作，直到所有数据元素有序输出。.对数据元素序列（35，66，2，15，6，81，6*，9）进行堆排序的过程如下所示。....3．算法实现voidHeapAdjust(SeqList*L,ints,intm){//将顺序表L中的r[s…m]调整为一个大顶堆intj;L->r[0]=L->r[s]; //保存根结点for(j=2*s;j<=m;j*=2) //沿关键字较大的孩子结点向下筛选{if(j<m&&L->r[j].key<L->r[j+1].key)j++; //令j为关键字较大的元素的下标if(L->r[0].key>=L->r[j].key)break; //若r[0]最大，将r[0]插入在位置s上else {L->.r[s]=L->r[j]; //将关键字最大的结点插入在位置ss=j;}} //沿关键字最大的结点进行下一层筛选L->r[s]=L->r[0];} //插入最后一个结点voidHeapSort(SeqList*L){//对顺序表L进行堆排序inti,j;for(i=L->length/2;i>0;i--)//将r[s…m]调整为一个大顶堆HeapAdjust(L,i,L->length); for(i=L->length;i>1;i--){L->r[0]=L->r[1]; //将堆顶元素与最后一个元素交换L->r[1]=L->r[i];L->r[i]=L->r[0];HeapAdjust(L,1,i-1);}} //将L.r[1…i-1]重新调整为大顶堆.4．算法分析（1）空间复杂度（2）时间复杂度（3）稳定性堆排序的时间复杂度为O(nlog2n)。堆排序是一种不稳定的排序方法。堆排序仅使用了一个辅助单元，算法的空间复杂度为O(1)。.任务五归并排序和基数排序一、归并排序二、基数排序.一、归并排序1．基本思想2．算法实现3．算法分析.1．基本思想对于一个具有n个数据元素的序列，将其中的每个数据元素看成长度为1的有序子表，然后对其进行两两归并，即第1个子表与第2个子表归并，第3个子表与第4个子表归并，依此类推，这样得到n/2个长度为2的有序表（若n为奇数，则最后一个有序表的长度为1）；在此基础上再进行两两归并，得到n/4个长度为4的有序表（最后一个有序表的长度可能小于4），依此类推，直至得到一个长度为n的有序表为止。.对数据元素序列（35，66，2，15，6，81，6*，9）进行归并排序的过程如下图所示。.2．算法实现voidMerge(RecordTyper1[],RecordTyper2[],intlow,intmid,inthigh){//r1[low…mid]和r1[mid+1…high]分别按关键字有序排列，将它们合并为有序序列存放//在r2[low…high]中inti,j,k;i=low;j=mid+1;k=low;//i、j分别为指向r1[low…mid]和r1[mid+1…high]的指针，将r1中的数据元素由小到大并入r2中while((i<=mid)&&(j<=high)) {//值小的送入r2if(r1[i].key<r1[j].key) {r2[k]=r1[i]; //r1[low…mid]中的元素送入r2i++;} //指针i后移else{r2[k]=r1[j]; //r1[mid+1…high]中的元素送入r2j++;} //指针j后移k++;}while(i<=mid) //若r1[low…mid]中有元素剩余，直接将剩余元素复制到r2中{ r2[k]=r1[i]; k++; i++;}while(j<=high) //若r1[mid+1…high]中有元素剩余，直接将剩余元素复制到r2中{ r2[k]=r1[j]; k++; j++;}}voidMSort(RecordTyper1[],RecordTyper2[],intlow,inthigh){//将r1[low…high]归并排序为r2[low…high]intmid;RecordType*r;r2=(RecordType*)malloc(sizeof(RecordType)*(high–low+1));//r2为辅助数组if(low==high) //若表长为1，则直接将r1复制到r2中r2[low]=r1[high];else{mid=(low+high)/2; //将r1[low…high]平分为两个子序列MSort(r1,r,low,mid); //将r1[low…mid]归并为r[low…mid]MSort(r1,r,mid+1,high);//将r1[mid+1…high]归并为r[mid+1…high]Merge(r,r2,low,mid,high);}}//将有序的r[low…mid]和r[mid+1…high]归并为有序的r2[low…high]voidMergeSort(SeqList*L){//对顺序表L作归并排序MSort(L->r,L->r,1,L->length);}.3．算法分析（1）空间复杂度（2）时间复杂度（3）稳定性归并排序的时间复杂度为O(nlog2n)。归并排序是一种稳定的排序方法。排序过程中需要一个与待排序列等长的辅助单元存放数据元素，因此，算法的空间复杂度为O(n)。.二、基数排序2．基本思想3．算法实现4．算法分析1．基本概念.1．基本概念基数排序是一种基于多关键字排序思想进行排序的排序方法。例如，表8-2给出的某班学生成绩单中包含了数学成绩和英语成绩（用A、B、C、D、E5个等级来表示），对该成绩单先按数学成绩的等级由高到低排序，数学成绩相同的学生再按英语成绩的等级由高到低排序。

高位优先法（MostSignificantDigitfirst，简称MSD）：先按数学成绩的等级由高到低将学生记录分成A、B、C、D、E5组，再分别对每组记录按英语成绩的等级由高到低进行排序。.低位优先法（LeastSignificantDigitfirst，简称LSD）：先按英语成绩的等级由高到低将学生记录分成A、B、C、D、E5组，再将其按从左到右、从上到下的顺序排列，得到关键字序列，如左图所示；然后按数学成绩的等级由高到低重新分成A、B、C、D、E5组，再将其按从左到右、从上到下的顺序排列，得到关键字序列，如右图所示；.2．基本思想根据基数的值设立相应个数的队列，排序时先按最低位子关键字的值进行排序，即按子关键字的不同值将各数据元素分配到相应的队列中，然后按照一定顺序将数据元素收集起来，此时得到的序列已按最低位子关键字有序排列。在此基础上按次低位子关键字的值进一步排序，依此类推，直至按关键字的最高位排序后，整个序列排序完成。.例如，对数据元素序列{35，66，2，15，6，81，6*，9}进行基数排序的过程如下图所示。..3．算法实现数据类型定义如下：#defineKEY_SIZE10 //关键字项数最大值#defineRADIX10 //关键字基数#defineLIST_SIZE20 //静态链表的最大容量typedefstruct{KeyTypekey[KEY_SIZE]; //子关键字数组OtherTypotheritem; //其他数据项intnext; //静态链表的指针域}RecordType;typedefstruct //定义静态链表类型{RecordTyper[LIST_SIZE+1]; //r[0]为头结点intkeynum; //当前关键字个数intlength; //静态链表的当前长度}SLinkList; typedefintheadtail[RADIX]; //指针数组类型.算法描述如下：voidDistribute(SeqList*L,inti,headtailhead,headtailtail){//静态链表L已按key[i+1]之后的关键字进行过“低位优先”排序，对L按第i个关键字key[i]进行第i趟分配inti,j;intp;for(j=0;j<=RADIX;j++) //将RADIX个队列进行初始化