数据结构（第2版）（C语言实现）课件：排序

排序

排序（sorting）是计算机程序设计的一个特别重要的技术，计算机的各个应用领域都有它的身影。如在处理学生考试成绩和元素的查找等都涉及到了对数据的排序。排列有序的折半查找要比顺序查找的效率要高许多。本章主要给大家介绍几种常用的排序技术：插入排序、选择排序、交换排序、归并排序和基数排序。

本章重点和难点：

1、希尔排序

2、快速排序

3、堆排序

4、归并排序

5、基数排序8.1基本概念

排序：把一个无序的元素序列按照元素的关键字递增或递减排列为有序的序列。假设包含n个元素（记录）的序列

(E1,E2,…,En)

其对应的关键字为

(k1,k2,…,kn)

需确定1,2,…,n的一种排列p1,p2,…,pn，使关键字满足以下非递减（或非递增）关系：

kp1≤kp2≤…≤kpn

从而使元素构成一个非递减（或非递增）的序列：

(Ep1,Ep2,…,Epn)

这样的一种操作被称为排序。8.1基本概念

稳定排序和不稳定排序：在待排序的记录序列中，若存在两个或两个以上关键字想到呢个的记录。假设ki=kj(1≤i≤n,1≤j≤n,i≠j)，且排序前的对应的记录Ei领先于Ej（即i<j）。若在排序之后，如果元素Ei仍领先于Ej，则称这种排序采用的方法是稳定的。如果经过排序之后，元素Ej领先于Ei（即i<j），则称这种排序方法是不稳定的。一个排序算法的好坏可以主要通过时间复杂度、空间复杂度和稳定性来衡量。无论算法稳定还是不稳定的，都不会影响到排序的最终结果。8.1基本概念

内排序和外排序：由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两类：内部排序和外部排序。内部排序也称为内排序，指的是待排序记录存放在计算机随机存储器中进行的排序过程；外部排序也称为外排序，指的是待排序记录的数据流很大，以致内存一次不能容纳全部记录，在排序的过程中需要不断对外存进行访问的排序过程。8.1基本概念

内排序的方法有许多，按照排序过程中采用的策略将排序分为几个大类：插入排序、选择排序、交换排序和归并排序。在排序过程中，需要以下两种基本操作：（1）比较两个元素相应关键字的大小；（2）将元素从一个位置移动到另一个位置。其中，第（1）种操作对大多数排序方法来说都是必要的，第（2）种操作可通过改变记录的存储方式可以避免。8.1基本概念待排序的记录序列有3种存储方式：（1）顺序存储。待排序的元素存储在一组连续的存储单元中，这类似于线性表的顺序存储，在序列中相邻的两个记录Ei和Ej，它们的物理位置也相邻。在这种存储方式中，记录之间的次序关系由其存储位置决定，则实现排序必须要移动记录。（2）链式存储。待排序元素存储在一组不连续的存储单元中，这类似于线性表的链式存储，序列中相邻的两个记录Ei和Ej，其物理位置不一定相邻。在这种存储方式中，记录之间的关系由附设的指针指示，在进行排序时，不需要移动元素，只需要修改指针即可。（3）静态链表。带排序记录存放在静态链表中，记录之间的关系由被称为游标的指针指示，实现排序不需要移动元素，只需要修改游标即可。8.2插入排序8.2.1直接插入排序

直接插入排序（StraightInsertionSort）是一种最简单的插入排序算法。基本算法思想：假设待排序元素有n个，初始时，已排序子集只有一个元素，即第1个元素；未排序子集是剩下的n-1个元素。

例如，有4个待排序元素22、6、17和8，排序前的状态如图9.1所示。8.2插入排序第1趟排序：将无序集中的第一个元素，也就是6与有序集中的元素22进行比较，因为22>6，所以需要先将22向后移动一个位置，然后将6插入到第一个位置，如图8.2所示。其中，阴影部分表示无序集，白色部分表示有序集。第2趟排序：将无序集的元素17从右到左依次与有序集中的元素比较，即先与22比较，因为17<22，所以先将22向后移动一个位置，然后比较17与第1个元素6的大小，因为17>6，所以将17放在第2个元素的位置，如图8.3所示。8.2插入排序第3趟排序：将待排序集合中的元素8与已经有序的元素集合从右到左依次比较，先与22比较。因为8<22，所以需要将22向后移动一个位置并与前一个元素17比较。由于8<17，将17向后移动并继续与6进行比较。因为8>6，所以将8放在第2个位置，如图8.4所示。8.2插入排序

假设待排序元素有8个，分别是17、46、32、87、58、9、50、38。使用直接插入排序对该元素序列的排序过程如图8.5所示。8.2插入排序直接插入排序算法描述如下。voidInsertSort(SqList*L)/*直接插入排序*/{ inti,j; DataTypet; for(i=1;i<L->length;i++)/*前i个元素已经有序，从第i+1个元素开始与前i个有序的关键字比较*/ { t=L->data[i+1]; /*取出第i+1个元素，即待排序的元素*/ j=i; while(j>-1&&t.key<L->data[j].key)/*寻找当前元素的合适位置*/ { L->data[j+1]=L->data[j]; j--; } L->data[j+1]=t; /*将当前元素插入合适的位置*/ }}8.2插入排序8.2.2折半插入排序折半插入排序算法是直接插入排序的改进。它的主要改进在于，在已经有序的集合中使用折半查找法确定待排序元素的插入位置。在找到要插入的位置后，将待排序元素插入到相应的位置。假设待排序元素有7个：67、53、73、21、34、98、12。使用折半插入排序对该元素序列第一趟排序过程如图8.6所示。8.2插入排序第2趟折半插入排序过程如图8.7所示。8.2插入排序voidBinInsertSort(SqList*L)/*折半插入排序*/{ inti,j,mid,low,high; DataTypet; for(i=1;i<L->length;i++) { t=L->data[i+1]; /*取出第i+1个元素，即待排序的元素*/ low=1,high=i; while(low<=high) /*利用折半查找思想寻找当前元素的合适位置*/ { mid=(low+high)/2; if(L->data[mid].key>t.key) high=mid-1; else low=mid+1; } for(j=i;j>=low;j--) /*移动元素，空出要插入的位置*/ L->data[j+1]=L->data[j]; L->data[low]=t; /*将当前元素插入合适的位置*

}}8.2插入排序8.2.3希尔排序希尔排序（shell’ssort）也称为缩小增量排序（diminishingincrementsort），它也属于插入排序类的算法，但时间效率比前几种排序有较大改进。

例如，利用希尔排序的算法思想，对元素的关键字序列(56,22,67,32,59,12,89,26,48,37)进行排序，其排序过程如图8.8所示。8.2插入排序voidShellInsert(SqList*L,intc)/*对顺序表L进行一次希尔排序，c是增量*/{ inti,j; DataTypet; for(i=c+1;i<=L->length;i++)/*将距离为c的元素作为一个子序列进行排序*/ { if(L->data[i].key<L->data[i-c].key) /*如果后者小于前者，则需要移动元素*/ { t=L->data[i]; for(j=i-c;j>0&&t.key<L->data[j].key;j=j-c) L->data[j+c]=L->data[j]; L->data[j+c]=t;/*依次将元素插入到正确的位置*/ } }}8.2插入排序voidShellInsertSort(SqList*L,intdelta[],intm)/*希尔排序，每次调用算法ShellInsert,delta是存放增量的数组*/{ inti; for(i=0;i<m;i++) /*进行m次希尔插入排序*/ { ShellInsert(L,delta[i]); }}希尔排序的分析是一个非常复杂的事情，问题主要在于希尔排序选择的增量，但是经过大量的研究，当增量的序列为2m-k+1-1时，其中m为排序的次数，1≤k≤t，其时间复杂度为O(n3/2)。希尔排序的空间复杂度为O(1)。

8.2插入排序8.2.4插入排序应用举例

【例8.1】利用直接插入排序、折半插入排序和希尔排序对关键字为(56,22,67,32,59,12,89,26,48,37)的元素序列进行排序。【分析】主要考察直接插入排序、折半插入排序和希尔排序的算法思想。8.3.1简单选择排序简单选择排序是一种简单的选择类排序算法，它是通过依次找到待排序元素序列中最小的数据元素，并将其放在序列的最前面，从而使待排序元素序列变为有序序列。它的基本算法思想描述如下：假设待排序的元素序列有n个，在第一趟排序过程中，从n个元素序列中选择最小的元素，并将其放在元素序列的最前面即第一个位置。在第二趟排序过程中，从剩余的n-1个元素中，选择最小的元素，将其放在第二个位置。依次类推，直到没有待比较的元素，简单选择排序算法结束。8.3选择排序简单选择排序的算法描述如下。voidSelectSort(SqList*L,intn)/*简单选择排序*/{ inti,j,k; DataTypet; /*将第i个元素的关键字与后面[i+1...n]个元素的关键字比较，将关键字最小的的元素放在第i个位置*/ for(i=1;i<=n-1;i++) { j=i; for(k=i+1;k<=n;k++) /*关键字最小的元素的序号为j*/ if(L->data[k].key<L->data[j].key) j=k; if(j!=i) /*如果序号i不等于j，则需要将序号i和序号j的元素交换*/ { t=L->data[i]; L->data[i]=L->data[j]; L->data[j]=t; } }}8.3选择排序8.3选择排序

给定一组元素序列，其元素的关键字为(56,22,67,32,59,12,89,26)，简单选择排序的过程如图8.10所示。8.3.2堆排序1．什么是堆和堆排序堆排序(heapsort)是利用了二叉树的树形结构进行排序。所谓堆，排序的算法思想：堆排序主要是利用了二叉树的树形结构，按照完全二叉树的编号次序，将元素序列的关键字依次存放在相应的结点。然后从叶子结点开始，从互为兄弟的两个结点中（没有兄弟结点除外），选择一个较大（或较小）者与其双亲结点比较，如果该结点大于（或小于）双亲结点，则将两者进行交换，使较大（或较小）者成为双亲结点。将所有的结点都做类似操作，直到根结点为止。这时，根结点的元素值的关键字最大（或最小）。8.3选择排序堆中的每一个结点都大于（或小于）其孩子结点。堆的数学形式定义为：假设存在n个元素，其关键字序列为(k1,k2,…,ki,…,kn)，如果有：如果将这些元素的关键字存放在一维数组中，将此一维数组中的元素与完全二叉树一一对应起来，则完全二叉树中的每个非叶子结点的值都不小于（或不大于）孩子结点的值。8.3选择排序

在堆中，堆的根结点元素值一定是所有结点元素值的最大值或最小值。例如，序列(87,64,53,51,23,21,48,32)和(12,35,27,46,41,39,48,55,89,76)都是堆，相应的完全二叉树表示如图8.11所示。8.3选择排序如果将堆中的根结点（堆顶）输出之后，然后将剩余的n-1个结点的元素值重新建立一个堆，则新堆的堆顶元素值是次大（或次小）值，将该堆顶元素输出。然后将剩余的n-2个结点的元素值重新建立一个堆，反复执行以上操作，直到堆中没有结点，就构成了一个有序序列，这样的重复建堆并输出堆顶元素的过程称为堆排序。8.3选择排序2．建堆堆排序的过程就是建立堆和不断调整使剩余结点构成新堆的过程。假设将待排序的元素的关键字存放在数组a中，第1个元素的关键字a[1]表示二叉树的根结点，剩下的元素的关键字aa[2…n]分别与二叉树中的结点按照层次从左到右一一对应。例如，a[1]的左孩子结点存放在a[2]中，右孩子结点存放在a[3]中，a[i]的左孩子结点存放在a[2*i]中，右孩子结点存放在a[2*i+1]中。8.3选择排序

例如，给定一组元素，其关键字序列为(21,47,39,58,39,57,48,62)，建立大顶堆的过程如图8.12所示。结点的旁边为对应的序号。建立后的大顶堆，其非叶子结点的元素值均不小于左、右子树结点的元素值。8.3选择排序建立大顶堆的算法描述如下所示。voidCreateHeap(SqList*H,intn)/*建立大顶堆*/{ inti; for(i=n/2;i>=1;i--) /*从序号n/2开始建立大顶堆*/ AdjustHeap(H,i,n);}8.3选择排序voidAdjustHeap(SqList*H,ints,intm)/*调整H.data[s...m]的关键字，使其成为一个大顶堆*/{ DataTypet; intj; t=(*H).data[s]; /*将根结点暂时保存在t中*/ for(j=2*s;j<=m;j*=2) { if(j<m&&(*H).data[j].key<(*H).data[j+1].key) /*沿关键字较大的孩子结点向下筛选*/ j++; /*j为关键字较大的结点的下标*/ if(t.key>(*H).data[j].key)/*如果孩子结点的值小于根结点的值，则不进行交换*/ break; (*H).data[s]=(*H).data[j]; s=j; } (*H).data[s]=t; /*将根结点插入到正确位置*/}8.3选择排序3．调整堆具体实现：当堆顶元素输出后，可以将堆顶元素放在堆的最后，即将第1个元素与最后一个元素交换a[1]<->a[n]，则需要调整的元素序列就是a[1…n-1]。从根结点开始，如果其左、右子树结点元素值大于根结点元素值，选择较大的一个进行交换。即如果a[2]>a[3]，则将a[1]与a[2]比较，如果a[1]>a[2]，则将a[1]与a[2]交换，否则不交换。如果a[2]<a[3]，则将a[1]与a[3]比较，如果a[1]>a[3]，则将a[1]与a[3]交换，否则不交换。重复执行此操作，直到叶子结点不存在，就完成了堆的调整，构成了一个新堆。8.3选择排序8.3选择排序

例如，一个大顶堆的关键字序列为(87,64,53,51,23,21,48,32)，当输出87后，调整剩余的关键字序列为一个新的的大顶堆的过程如图8.13所示。。8.3选择排序调整堆的算法实现如下。voidHeapSort(SqList*H)/*对顺序表H进行堆排序*/{ DataTypet; inti; CreateHeap(H,H->length); /*创建堆*/ for(i=(*H).length;i>1;i--) /*将堆顶元素与最后一个元素交换，重新调整堆*/ { t=(*H).data[1]; (*H).data[1]=(*H).data[i]; (*H).data[i]=t; AdjustHeap(H,1,i-1); /*将(*H).data[1..i-1]调整为大顶堆*/ }}8.4交换排序8.4.1冒泡排序冒泡排序(bubblesort)是一种简单的交换类排序算法，它是通过交换相邻的两个数据元素，逐步将待排序序列变成有序序列。它的基本算法思想描述如下：假设待排序元素有n个，从第1个元素开始，依次交换相邻的两个逆序元素，直到最后一个元素为止。当第1趟排序结束，就会将最大的元素移动到序列的末尾。然后按照以上方法进行第2趟排序，次大的元素将会被移动到序列的倒数第2个位置。依次类推，经过n-1趟排序后，整个元素序列就成了一个有序的序列。每趟排序过程中，值小的元素向前移动，值大的元素向后移动，就像气泡一样向上升，因此将这种排序方法称为冒泡排序。8.4交换排序

例如，一组元素序列的关键字为(56,22,67,32,59,12,89,26,48,37)，对该关键字序列进行冒泡排序，第一趟排序过程如图8.15所示。8.4交换排序

从图8.15容易看出，第一趟排序结束后，关键字最大的元素被移动到序列的末尾。按照这种方法，冒泡排序的全过程如图8.16所示。8.4交换排序冒泡排序的算法描述如下。voidBubbleSort(SqList*L,intn)/*冒泡排序*/{ inti,j,flag; DataTypet; for(i=1;i<=n-1&&flag;i++) /*需要进行n-1趟排序*/ { flag=0; for(j=1;j<=n-i;j++) /*每一趟排序需要比较n-i次*/ if(L->data[j].key>L->data[j+1].key)

{ t=L->data[j]; L->data[j]=L->data[j+1]; L->data[j+1]=t; flag=1;

} }}8.4交换排序8.4.2快速排序快速排序的算法思想是：从待排序记录序列中选取一个记录（通常是第一个记录）作为枢轴，其关键字设为key，然后将其余关键字小于key的记录移至前面，而将关键字大于key的记录移至后面，结果将待排序记录序列分为两个子表，最后将关键字key的记录插入到其分界线的位置。我们将这个过程称为一趟快速排序。通过这一趟划分后，就以关键字为key的记录为界，将待排序序列分为两个子表，前面的子表所有记录的关键字均不大于key，而后面子表的所有记录的关键字均不小于key。继续对分割后的子表进行上述划分，直至所有子表的表长不超过1为止，此时的待排序记录就成了一个有序序列。9.4交换排序【算法步骤】设待排序序列存放在数组a[1…n]中，n为元素个数，设置两个指针i和j，初值分别为1和n，令a[1]作为枢轴元素赋给pivot，a[1]相当于空单元，然后执行以下操作：（1）j从右往左扫描，若a[j].key<pivot.key，将a[j]移至a[i]中，此时a[j]相当于空单元，并执行一次i++操作；（2）i从左至右扫描，直至a[i].key>pivot.key，将a[i]移至a[j]中，并执行一次j--操作；（3）重复执行（1）和（2），直到出现i≥j，则将元素pivot移动到a[i]中。此时整个元素序列在位置i被划分成两个部分，前一部分的元素关键字都小于a[i].key，后一部分元素的关键字都大于等于a[i].key。即完成了一趟快速排序。8.4交换排序

例如，一组元素序列的关键字为(37,19,43,22,22,89,26,92)，根据快速排序算法思想，第一次划分的过程如图8.17所示。8.4交换排序

从图8.17容易看出，当一趟快速排序完毕之后，整个元素序列被枢轴的关键字37划分为两个部分，前一个部分的关键字都小于37，后一部分元素的关键字都大于等于37。其实，快速排序的过程就是以枢轴为中心将元素序列划分的过程，直到所有的序列被划分为单独的元素，快速排序完毕。8.4交换排序intPartition(SqList*L,intlow,inthigh)/*对顺序表L.r[low..high]的元素进行一趟排序*/{DataTypet;KeyTypepivotkey; pivotkey=(*L).data[low].key;/*将表的第一个元素作为枢轴元素*/ t=(*L).data[low]; while(low<high) /*从表的两端交替地向中间扫描*/ { while(low<high&&(*L).data[high].key>=pivotkey) high--; if(low<high) /*将当前high指向的元素保存在low位置*/ { (*L).data[low]=(*L).data[high]; low++; }while(low<high&&(*L).data[low].key<=pivotkey) /*从表的始端向后扫描*/ low++; if(low<high) /*将当前low指向的元素保存在high位置*/ { (*L).data[high]=(*L).data[low]; high--; }

}(*L).data[low]=t;/*将枢轴元素保存在low=high的位置*/ returnlow; /*返回枢轴所在位置*/}8.4交换排序8.4交换排序voidQuickSort(SqList*L,intlow,inthigh)/*对顺序表L进行快速排序*/{ intpivot; if(low<high) /*如果元素序列的长度大于1*/ { pivot=Partition(L,low,high); /*将待排序序列L.r[low..high]划分为两部分*/ QuickSort(L,low,pivot-1); /*对左边的子表进行递归排序，pivot是枢轴位置*/ QuickSort(L,pivot+1,high); /*对右边的子表进行递归排序*/ }}8.4交换排序

快速排序在最好的情况下是每趟排序将序列一分两半，从表中间开始，将表分成两个大小相同的子表，类似折半查找，这样快速排序的划分的过程就将元素序列构成一个完全二叉树的结构，分解的次数等于树的深度即log2n，因此快速排序总的比较次数为T(n)≤n+2T(n/2)≤n+2*(n/2+2*T(n/4))=2n+4T(n/4)≤3n+8T(n/8)≤…≤nlog2n+nT(1)。因此，在最好的情况下，时间复杂度为O(nlog2n)。8.4.3交换排序应用举例【例8.2】一组元素的关键字序列为(37,22,43,32,19,12,89,26,48,92)，使用冒泡排序和快速排序对该元素进行排序，并输出冒泡排序和快速排序的每趟排序结果。【分析】主要考察两种交换排序即冒泡排序和快速排序的算法思想。这两种算法都是对存在逆序的元素进行交换，从而实现排序。主要区别在于：冒泡排序通过比较相邻的两个元素，并对两个相邻的逆序元素进行交换；而快速排序则是选定一个枢轴元素作为参考元素，设置两个指针，分别从表头和表尾开始，将当前扫描的元素与枢轴元素进行比较，存在逆序的元素不一定是相邻的元素，如果存在逆序，则交换之。8.3交换排序8.5归并排序

归并排序(MergingSort)的基本思想是：将两个或两个以上的元素有序序列组合，使其成为一个有序序列。其中最为常用的是2路归并排序。2路归并排序的主要思想是：假设元素的个数是n，将每个元素作为一个有序的子序列，然后将相邻的两个子序列两两归并，得到个长度为2的有序子序列。然后将相邻的两个有序子序列两两归并，得到个长度为4的有序子序列。如此重复，直至得到一个长度为n的有序序列为止。8.5归并排序voidMerge(DataTypes[],DataTypet[],intlow,intmid,inthigh)/*将有序的s[low...mid]和s[mid+1..high]归并为有序的t[low..high]*/{ inti,j,k; i=low,j=mid+1,k=low; while(i<=mid&&j<=high) /*将s中元素由小到大地合并到t*/ { if(s[i].key<=s[j].key) { t[k]=s[i++]; } else { t[k]=s[j++]; } k++; } while(i<=mid) /*将剩余的s[i..mid]复制到t*/ t[k++]=s[i++]; while(j<=high) /*将剩余的s[j..high]复制到t*/ t[k++]=s[j++];}8.5归并排序voidMergeSort(DataTypes[],DataTypet[],intlow,inthigh)/*2路归并排序，将s[low...high]归并排序并存储到t[low...high]中*/{ intmid; DataTypet2[MaxSize]; if(low==high) t[low]=s[low]; else { mid=(low+high)/2; /*将s[low...high]分为s[low...mid]和s[mid+1...high]*/ MergeSort(s,t2,low,mid); /*将s[low...mid]归并为有序的t2[low...mid]*/ MergeSort(s,t2,mid+1,high); /*将s[mid+1...high]归并为有序的t2[mid+1...high]*/ Merge(t2,t,low,mid,high); /*将t2[low...mid]和t2[mid+1..high]归并到t[low...high]*/ }}8.6基数排序基数排序是一种与前面所述各种排序方法完全不同的方法，前面的排序主要通过对元素的关键字进行比较和移动记录这两种操作，而实现基数排序则不需要进行对关键字比较。

例如，一组元素序列的关键字为(334,45,21,467,821,562,342,45)。这组关键字位数最多的是3位，在排序之前，首先将所有的关键字都看作是一个3位数字组成的数，即(324,285,021,467,821,562,342,045)。对这组关键字进行基数排序需要进行3趟分配和收集。首先需要对该关键字序列的最低位进行分配和搜集，然后对十位数字进行分配和收集，最后是对最高位的数字进行分配和收集。一般情况下，采用链表实现基数排序。8.6基数排序

一般情况下，采用链表实现基数排序。对最低位进行分配和收集的过程如图8.21所示。其中，数组f[i]保存第i个链表的头指针，数组r[i]保存第i个链表的尾指针。

对十位数字分配和收集的过程如图8.22所示。

8.6基数排序对百位数字分配和收集的过程如图8.23所示。

经过第一趟排序即对个位数作为关键字进行分配后，关键字被分为9类，个位数字相同的数字被划分为一类，然后对分配后的关键字进行收集之后，得到以个位数字非递减排序的序列。同理，经过第二趟分配和收集后，得到以十位数字非递减排序的序列。经过第三趟分配和收集后，得到最终的排序结果。8.6基数排序基数排序的算法主要包括分配和收集。#defineMaxNumKey6/*关键字项数的最大值*/#defineRadix10 /*关键字基数，此时是十进制整数的基数*/#defineMaxSize1000typedefintKeyType;typedefstruct{ KeyTypekey[MaxNumKey];/*关键字*/ intnext;}SListCell; /*静态链表的结点类型*/typedefstruct{ SListCelldata[MaxSize]; /*存储元素，data[0]为头结点*/ intkeynum; /*每个元素的当前关键字个数*/ intlength; /*静态链表的当前长度*/}SList; /*静态链表类型*/typedefintaddr[Radix]; /*指针数组类型*/8.6基数排序基数排序的分配算法实现如下所示。voidDistribute(SListCelldata[],inti,addrf,addrr)/*为data中的第i个关键字key[i]建立Radix个子表，使同一子表中元素key[i]相同*//*f[0..Radix-1]和r[0..Radix-1]分别指向各个子表中第一个和最后一个元素*/{ intj,p; for(j=0;j<Radix;j++) /*将各个子表初始化为空表*/ f[j]=0; for(p=data[0].next;p;p=data[p].next) { j=trans(data[p].key[i]); /*将对应的关键字字符转化为整数类型*/ if(!f[j]) /*f[j]是空表，则f[j]指示第一个元素*/ f[j]=p; else da