《数据结构实用教程（C语言版）》课件第8章 排序

第8章排序本章中主要介绍下列内容：排序的概念插入排序方法：直接插入排序和希尔排序交换排序方法：冒泡排序和快速排序选择排序方法：直接选择排序和堆排序归并排序方法本章目录8.1排序的基本概念18.2插入排序28.3交换排序38.4选择排序48.5归并排序58.6本章小结6结束8.1排序的基本概念8.1.1排序的定义8.1.2相关概念返回到总目录8.1.1排序的定义有n个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2，…，Kn}，相应的下标序列为1，2，…，n。通过排序，要求找出当前下标序列1，2，…，n的一种排列p1，p2，…，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn

，这样就得到一个按关键字有序的记录序列：{Rp1，Rp2，…，Rpn}。这样一种操作称为排序。简单的说，就是将无序序列按记录中的关键字排成以该关键字有序的序列过程就是排序。返回到本节目录关键字Ki可以是记录Ri的主关键字，也可以是记录Ri的次主关键字。若Ki是记录Ri的主关键字，则任何一个记录的无序序列经过排序后得到的结果是唯一的；若Ki是记录Ri的次主关键字，则经过排序后得到的结果可能不一唯一。这是因为在待排序的记录序列中可能存在两个或两个以上关键字相等的记录。返回到本节目录8.1.2相关概念1．内部排序整个排序过程完全在内存中进行，称为内部排序。2．外部排序由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。3．稳定排序和不稳定排序假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri领先于Rj(即i<j)，经过排序后得到的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，若相同关键字的先后次序在排序过程中发生变化者，则称所用的排序方法是不稳定的。返回到本节目录本章主要介绍的是内部排序。内部排序主要分为插入排序法、交换排序法、选择排序法和归并排序法。我们假定待排序的记录均是以顺序存储结构存放的，且假定记录的关键字均为整数。另外，假定待排序的记录是按递增顺序进行排序。其排序记录的数据类型定义如下：返回到本节目录#defineMaxSize100/*查找表中最大元素个数*/typedefintKeyType;/*重定义关键字类型为整型，也可以为其它类型*/typedefcharElemType;/*重定义数据项类型为字符型*/typedefstruct{KeyTypeKey;/*关键字域*/ElemTypedata;/*其他数据项*/}LineList;/*线性查找表类型*/返回到本节目录8.2插入排序8.2.1直接插入排序8.2.2希尔排序返回到总目录8.2.1直接插入排序1．直接插入排序的基本思想直接插入排序是一种最简单的排序方法，它的基本思想是依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。有n个记录的无序序列具体的排序过程可以描述如下：（1）首先将待排序记录序列中的第一个记录作为一个有序段，此时这个有序段中只有一个记录。（2）从第2个记录起到最后一个记录，依次将记录和前面子序列中的记录比较，确定记录插入的位置。返回到本节目录（3）将记录插入到子序列中，子序列中的记录个数加1，直至子序列长度和原来待排序列长度一致时排序结束。一共经过n-1趟就可以将初始序列的n个记录重新排列成按关键字值从小到大排列的有序序列。为了防止在比较过程中数组下标的溢出，我们设一个监视哨r[0]，即先将要比较的关键字存入监视哨r[0]中，然后再用r[0]从后向前进行比较。若r[0]小于所比较的关键字，则将该关键字向后移一位，并且继续向前比较，直到r[0]大于等于所比较的关键字时结束。因为我们是边比较边移动记录的，所以在当前比较记录的后面位置是空出来的，直接将r[0]存入即可。返回到本节目录【例8.1】设待排序的记录序列有n=7个记录，其关键字的初始序列为：{32，15，6，48，19，21，49}，请给出直接插入排序的过程。在序列中有两个相同关键字15，我们用方框将后一个15框上加以区分。解：直接插入排序过程如图8-1所示。就是对此记录序列进行直接插入排序的过程示意图。其中括号内部的关键字为已排好序的部分。返回到本节目录图8-1直接插入排序过程返回到本节目录2．直接插入排序的算法如算法8.1所示算法8.1voidInsertSort(LineListr[],intn){inti,j;for(i=2;i<=n;i++)/*一共需要比较n-1趟*/{r[0]=r[i];/*将r[0]赋为监视哨*/j=i-1;返回到本节目录while(r[0].Key<r[j].Key)/*搜索插入位置*/{r[j+1]=r[j];j=j-1;}r[j+1]=r[0];/*将原来r[i]中的记录放入第j+1个位置*/}}该算法的主函数同后面希尔排序的主函数，只是将调用语句改为InsertSort(r,n);即可。返回到本节目录3．直接插入排序算法分析：从空间角度来看，它只需要一个辅助空间r[0]。

从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。算法执行时间在最坏的情况下是O(n2)。在这种插入过程中两个15先后位置没有发生变化，所以直接插入排序是一种稳定排序方法。返回到本节目录8.2.2希尔排序1．希尔排序的基本思想希尔排序又称为缩小增量排序，其基本思想是：先将待排序的记录划分为几组，从而减小参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，最后再对所有的记录实施直接插入排序。希尔排序的具体方法如下：返回到本节目录

（1）取定一个正整数d1<n，把d1作为间隔值，把全部记录从第一个记录起进行分组，所有距离为dk1倍数的记录放在一组中，在各组内进行直接插入排序。（2）取定一个正整数d2<d1，重复上述分组和排序工作，直至取di=1为止，即所有记录在一个组中进行直接插入排序。希尔提出的d1=，di+1=。返回到本节目录【例8.2】已知待排序的一组记录的关键字初始排列为{25，36，12，68，45，16，37，22}，请给出希尔排序的过程。解：其希尔排序的过程如图8-2所示。图8-2希尔排序的过程返回到本节目录2．希尔排序的算法（1）希尔排序如算法8.2所示。算法8.2voidShellSort(LineListr[],intn){inti,j,d;d=n/2;/*初始步长为表长的一半*/while(d>0){for(i=d;i<=n;i++){r[0]=r[i];/*设监视哨*/

j=i-d;返回到本节目录while(j>=0&&r[0].Key<r[j].Key){r[j+d]=r[j];j=j-d;}r[j+d]=r[0];j=j-d;}d=d/2;}}返回到本节目录8.3交换排序交换排序的基本方法是：通过两两比较待排序记录的关键字，若有不满足次序要求的一对数据则交换，直到全部满足为止。本节主要介绍冒泡排序和快速排序两种排序方法。8.3.1冒泡排序8.3.2快速排序返回到总目录8.3.1冒泡排序1．冒泡排序的基本思想冒泡排序是交换排序中一种简单的排序方法。它的基本思想是对所有相邻记录的关键字值进行比较，如果是逆序（r[j]>r[j+1]），则将其交换，最终达到有序化。其处理过程为：（1）将整个待排序的记录序列划分成有序区和无序区。初始状态有序区为空，无序区包括所有待排序的记录。返回到本节目录（2）对无序区从前向后依次将相邻记录的关键字进行比较，若逆序则将其交换，从而使得关键字值小的记录向上“飘”（左移），关键字值大的记录向下“沉”（右移）。每经过一趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由n个记录组成的记录序列，最多经过n-1趟冒泡排序，就可以将这n个记录重新按关键字顺序排列。返回到本节目录【例8.3】已知有10个待排序的记录，它们的关键字序列为{43，12，35，18，26，57，7，21，43，46}，给出冒泡排序法进行排序的过程。（两个相同的关键字43，后面的43用方框框上）解：冒泡排序的过程如图8-3所示。其中括号内表示有序区。返回到本节目录图8-3冒泡排序的过程返回到本节目录2．冒泡排序算法（1）基本的冒泡排序算法对由n个记录组成的记录序列，最多经过（n-1）趟冒泡排序，就可以使记录序列成为有序序列，第一趟定位第n个记录，此时有序区只有一个记录；第二趟定位第n-1个记录，此时有序区有两个记录；以此类推，直到最后所有的记录都进入有序区，排序结束。完整的冒泡排序算法如算法8.3所示。返回到本节目录算法8.3voidBubbleSort1(LineListr[],intn){inti,j;LineListtemp;for(i=n-1;i>0;i--)/*i为每趟排序的数组最大下标值*/for(j=0;j<=i-1;j++)/*一趟交换排序*/ if(r[j].Key>r[j+1].Key)/*若逆序*/{temp=r[j];r[j]=r[j+1];r[j+1]=temp;}}返回到本节目录（2）改进的冒泡排序算法在冒泡排序过程中，一旦发现某一趟没有进行交换操作，就表明此时待排序记录序列已经成为有序序列，冒泡排序再进行下去已经没有必要，应立即结束排序过程。如例8.1题中，在第六趟排序后，序列已经成为有序序列，从第七次到第九次排序就没有必要。为实现这一方法我们在循环体内设一个查看是否有记录交换的变量，在每趟比较时查看是否有交换，如果没有，则提前结束循环。改进的冒泡排序算法如算法8.4所示。返回到本节目录算法8.4voidBubbleSort2(LineListr[],intn){inti,j,exchange;/*exchange为标记是否交换的标识变量*/LineListtemp; for(i=n-1;i>0;i--)/*i为每趟排序的数组最大下标值*/ {exchange=0;

返回到本节目录for(j=0;j<=i-1;j++)/*一趟交换排序*/ if(r[j].Key>r[j+1].Key)/*若逆序*/ {temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=1;} if(exchange==0)return; }}返回到本节目录8.3.2快速排序快速排序（QuickSort）是对起泡排序的一种改进。1．快速排序的基本思想快速排序又称为分区交换排序，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。返回到本节目录具体过程是：首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选取一个记录（通常选取第一个记录）作为支点（或枢轴），并以该记录的关键字值为基准，从位于待排序记录序列左右两端开始，逐渐向中间靠拢，交替与基准记录的关键字进行比较、交换。每次比较，若遇左侧记录的关键字值大于基准记录的关键字，则将其与基准记录交换，使其移到基准记录的右侧；若遇右侧记录的关键字值小于基准值，则将其与基准记录交换，使其移至基准记录的左侧，最后让基准记录到达它的最终位置。返回到本节目录此时，基准记录将待排序记录分成了左右两个区域，位于基准记录左侧的记录都小于或等于基准记录的关键字，位于基准记录右侧的所有记录的关键字都大于或等于基准记录的关键字，这就是一趟快速排序。一趟快速排序之后，再分别对左右两个区域进行快速排序，以此类推，直到每个分区域都只有一个记录为止。此时整个待排序记录按关键值有序排列，至此排序结束。返回到本节目录【例8.2】已知一个无序序列，其关键字值为{32，42，7，48，15，48，12，18}的记录序列，给出进行快速排序的过程。（其中有两个相同的关键字48，后一个用括号括起）解：冒泡排序的过程如图8-4所示（小括号（）内的关键字表示支点，中括号[]内关键字为待排序区间）。返回到本节目录返回到本节目录（b）完整的快速排序过程图8-4快速排序过程示意图返回到本节目录2．快速排序的算法（1）快速排序的算法如算法8.5所示。算法8.5voidQuickSort(LineListr[],intfirst,intend){inti,j;LineListtemp;i=first;j=end;temp=r[i];/*初始化*/while(i<j)返回到本节目录{while(i<j&&temp.Key<=r[j].Key)j--;r[i]=r[j];while(i<j&&r[i].Key<=temp.Key)i++;r[j]=r[i];}r[i]=temp;if(first<i-1)QuickSort(r,first,i-1);/*对左侧分区域进行快速排序*/if(i+1<end)QuickSort(r,i+1,end);/*对右侧分区域进行快速排序*/}返回到本节目录8.4选择排序选择排序是指在排序过程序中，依次从待排序的记录序列中选择出关键字值最小的记录、关键字值次小的记录、……，并分别将它们定位到序列左侧的第1个位置、第2个位置、……，最后剩下一个关键字值最大的记录位于序列的最后一个位置，从而使待排序的记录序列成为按关键字值由小到大排列的的有序序列。8.4.1直接选择排序8.4.2堆排序返回到总目录8.4.1直接选择排序1．直接选择排序的基本思想简单选择排序的基本思想是：每一趟在n-i+1(i=1,2,3,...,n-1)个记录中选取关键字最小的记录作为有序序列中的第i个记录。它的具体实现过程为：（1）将整个记录序列划分为有序区域和无序区域，有序区域位于最左端，无序区域位于右端，初始状态有序区域为空，无序区域含有待排序的所有n个记录。（2）设置一个整型变量index，用于记录在一趟的比较过程中，当前关键字值最小的记录位置。返回到本节目录开始将它设定为当前无序区域的第一个位置，即假设这个位置的关键字最小，然后用它与无序区域中其他记录进行比较，若发现有比它的关键字还小的记录，就将index改为这个新的最小记录位置，随后再用a[index].key与后面的记录进行比较，并根据比较结果，随时修改index的值，一趟结束后index中保留的就是本趟选择的关键字最小的记录位置。（3）将index位置的记录交换到有序区域的第一个位置，使得有序区域扩展了一个记录，而无序区域减少了一个记录。不断重复（2）、（3），直到无序区域剩下一个记录为止。此时所有的记录已经按关键字从小到大的顺序排列就位。返回到本节目录（1）直接选择排序的程序如算法8.6所示。算法8.6voidSelectSort(LineListr[],intlength)/*对记录数组r做简单选择排序，length为数组的长度*/{inti,j,k,n;LineListx;n=length;2．直接选择排序的算法返回到本节目录for(i=0;i<n;++i){k=i;for(j=i+1;j<=n;++j)if(r[j].Key<r[k].Key)k=j;if(k!=i){x=r[i];r[i]=r[k];r[k]=x;}}}/*SelectSort*/返回到本节目录8.4.2堆排序1．堆的定义堆排序是另一种基于选择的排序方法。我们先介绍一下什么是堆？然后再介绍如何利用堆进行排序。堆定义：由n个元素组成的序列{k1，k2，……，kn-1，kn}，当且仅当满足如下关系时，称之为堆。返回到本节目录若将堆看成是一棵以k1为根的完全二叉树，则这棵完全二叉树中的每个非终端结点的值ki均不大于（或不小于）其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这n个结点中的最小者或最大者。一般的，堆顶元素为最小值，该堆成为小根堆；堆顶元素为最大值，该堆成为大根堆。例如，下列A、B两个序列为堆，对应的完全二叉树如图8-5所示。序列A={56，32，28，22，16，7，13，18}构成的是大根堆；序列B={5，13，18，22，35，24}构成的是小根堆。返回到本节目录（a）堆顶元素取最大值，为大根堆（b）堆顶元素取最小值，为小根堆图8-5堆的示例返回到本节目录2．堆排序的方法堆排序的基本思想是：首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小（或次大）的记录，以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。因此，堆排序的关键步骤有两个：一是构造堆，即如何将一个无序序列建成初始堆；第二是调整堆，即如何在输出堆的根结点之后，调整剩余元素成为一个新的堆。首先考虑第二个问题，调整堆；然后再考虑第一个问题，构造堆。返回到本节目录（1）调整堆假设有一个小根堆，当输出堆顶元素（根结点）后，以堆中最后一个元素替代它。此时根结点的左子树和右子树均为堆，则只需自上而下进行调整即可。首先将堆顶元素与其左、右子树根结点的值进行比较，如果堆顶元素比它的两个子结点都小，则已经是堆；否则，让堆顶元素与其中较小的孩子结点交换，先让堆顶满足堆的性质。可能因为交换，使交换后的结点为根的子树不再满足堆的性质，则重复向下调整，当调整使新的更小子树依旧满足堆的性质时，重新建堆的过程结束。这种自上而下的建堆过程称为结点向下的“筛选”。图8-6是一个小根堆的排序输出过程。

返回到本节目录图8-6一个小根堆的排序过程返回到本节目录（2）构造堆为了构造初始堆，可以在已是堆的两个子序列中面加上它们的根结点，并且作必要的调整使之成为更大的堆。加上根结点后，可以不满足堆的定义，则可以用前面所述的“筛选”方法，使之成为堆。所以，一个无序序列构造堆的过程就是反复“筛选”的过程。返回到本节目录若将n个待排序记录的关键字序列看成是一个完全二叉树，则最后一个非叶子结点是第

个元素。首先，将n个叶子结点看成是n个堆，然后从第

个结点开始，依次将第

个结点，第

-1个结点，…，第1个结点按照堆的定义逐一加到它们的子结点上，直到建成一个完全的堆。返回到本节目录例如，图8-7（a）中的完全二叉树表示一个有8个元素的无序序列：{49，38，65，97，76，13，27，49}（相同的两个关键字49，其中后面一个用49表示），则构造堆的过程如图8-7（b）~（f）所示。返回到本节目录图8-7无序完全二叉树构造堆的过程返回到本节目录3．堆排序算法（1）筛选过程如算法8.7所示。算法8.7voidSift(LineListr[],intlow,inthigh)/*假设r[k..high]是以r[k]为根的完全二叉树,且分别以r[2k]和r[2k+1]为根的左、右子树为大根堆,调整r[k],使整个序列r[k..high]满足堆的性质*/{inti=low,j=2*i;LineListtmp=r[i];/*暂存“根”记录r[k]*/返回到本节目录while(j<=high){if(j<high&&r[j].Key<r[j+1].Key) j=j+1;/*若存在右子树,且右子树根的关键字大,则沿右分支“筛选”*/if(tmp.Key<r[j].Key){r[i]=r[j]; i=j; j=2*i;}/*继续筛选*/elsebreak;}r[i]=tmp;/*r[k]填入到恰当的位置*/}/*sift*/返回到本节目录（2）堆排序的算法如算法8.8所示。算法8.8voidHeapSort(LineListr[],intn)/*对记录数组r建堆,n为数组的长度*/{inti;LineListtmp;for(i=n/2;i>=1;i--)Sift(r,i,n);for(i=n;i>=1;i--)/*自第n个记录开始进行筛选建堆*/{tmp=r[1];r[1]=r[i];r[i]=tmp;Sift(r,1,i-1);

}}返回到本节目录8.5归并排序1．归并排序的基本思想归并排序是另一类排序方法。所谓归并是指将两个或两个以上的有序表合并成一个新的有序表。归并排序的基本思想是：首先，将r[0..n-1]看成是n个长度为1的有序表，将相邻的有序表成对归并，得到n/2个长度为2的有序表。然后，再将这些有序表成对归并，得到n/4个长度为4的有序表，如此反复进行下去，最后得到一个长度为n的有序表。返回到总目录由于归并是在相邻的两个有序表中进行的，因此，上述排序方法也叫二路归并排序。如果归并操作在相邻的多个有序表中进行，则叫多路归并排序。在此只讨论二路归并排序（简称归并排序）。2．归并排序过程示例

【例8.3】对具有初始输入序列{26，5，77，1，61，11，59，15，48，19}的记录采用归并排序法进行排序，序列在每遍扫描时合并的情况如图8-8所示。其中h为归并排序的有序表中元素个数，n为表总长度。初始h=1，以后hi+1=2hi，当n>h时进行归并排序，当n<h时结束归并排序。返回到本节首页图8-8归并排序过程返回到本节首页3．归并排序的算法（1）一次归并算法在上面所示的过程中，有两个过程，一个是每两个有序表的归并，然后是多次归并操作，最后实现整个归并过程。先介绍将两个有序表归并为一个有序表的算法Merge()。设两个有序表存放在同一数组中相邻的位置上：r[low..mid]，r[mid+1..high]。先将它们合并到一个局部的暂存数组r1中，待合并完成后将r1复制回r中。为了简便，称r[low..mid]为第一段，r[mid+1..high]为第2段。每次从两个段中取出一个记录进行关键字的比较，将较小者放入r1中，最后将各段中余下的部分直接复制到r1中。这样r1是一个有序表，再将其复制回r中。算法如算法8.9所示。返回到本节首页算法8.9voidMerge(LineListr[],intlow,intmid,inthigh){LineList*r1;inti=low,j=mid+1,k=0;/*k是r1的下标,i,j分别为第1,2段的下标*/r1=(LineList*)malloc((high-low+1)*sizeof(LineList));while(i<=mid&&j<=high)if(r[i].Key<=r[j].Key){r1[k]=r[i];i++;k++;}返回到本节首页e