数据结构与算法分析第八章内部排序.pdf

《数据结构与算法分析第八章内部排序.pdf》由会员分享，可在线阅读，更多相关《数据结构与算法分析第八章内部排序.pdf（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第八章第八章第八章第八章 内部排序内部排序内部排序内部排序概念术语概念术语概念术语概念术语排 序：排 序：按照结点中的某项值对集合中结点进行升序或降序的排列按照结点中的某项值对集合中结点进行升序或降序的排列关键字：关键字：排序时参照的数据项，有主次之分排序时参照的数据项，有主次之分稳定性：稳定性：如果排序操作使等值结点的相对位置(主要是指前后关系)保持不变，则排序是稳定的，否则是不稳定的。如果排序操作使等值结点的相对位置(主要是指前后关系)保持不变，则排序是稳定的，否则是不稳定的。内部排序：内部排序：排序序列放在内存中排序序列放在内存中外部排序：外部排序：需要对外存进行访问需要对外存进行访问

2、内排序分类内排序分类内排序分类内排序分类按排序过程依据的按排序过程依据的按排序过程依据的按排序过程依据的原则原则原则原则分为：插入排序分为：插入排序分为：插入排序分为：插入排序交换排序交换排序交换排序交换排序选择排序选择排序选择排序选择排序归并排序归并排序归并排序归并排序基数排序基数排序基数排序基数排序按排序过程所需的按排序过程所需的按排序过程所需的按排序过程所需的工作量工作量工作量工作量分：简单排序分：简单排序分：简单排序分：简单排序 O(nO(n2 2)先进排序先进排序先进排序先进排序 O(nlogO(nlogn n)基数排序基数排序基数排序基数排序 O(dO(dn)n)内内内内部部部部排

3、排排排序序序序 插入排序插入排序插入排序插入排序 交换排序交换排序交换排序交换排序 选择排序选择排序选择排序选择排序 归并排序归并排序归并排序归并排序 基数排序基数排序基数排序基数排序有序表中插入元素，并保持其有序有序表中插入元素，并保持其有序将表中关键字比较，位置不对交换将表中关键字比较，位置不对交换先查找关键字，再交换。先查找关键字，再交换。将两个有序的关键字序列进行归并将两个有序的关键字序列进行归并不比较，按多关键字排序方法不比较，按多关键字排序方法直接直接折半折半2-路路希尔希尔冒泡冒泡快速快速简单简单树型树型堆堆 直接插入排序直接插入排序直接插入排序直接插入排序 例：给定以下关键字：

4、例：给定以下关键字：49 38 65 97 76 13 27 49 i=1 (49)(49)38 65 97 76 13 27 49 i=2 (38)(3849)65 97 76 13 27 49 i=3 (65)(38 49 65)97 76 13 27 49 i=4 (97)(38 49 65 97)76 13 27 49 i=5 (76)(38 49 65 7697 )13 27 49 i=6 (13)(1338 49 65 76 97 )27 49 i=7 (27)(13 2738 49 65 76 97 )49 i=8 (49)(13 27 38 49 4965 76 97 )基本思

5、想基本思想基本思想基本思想：依次将每个待排序的记录插入到一个有序子文件依次将每个待排序的记录插入到一个有序子文件依次将每个待排序的记录插入到一个有序子文件依次将每个待排序的记录插入到一个有序子文件的合适位置的合适位置的合适位置的合适位置(有序子文件记录数增有序子文件记录数增有序子文件记录数增有序子文件记录数增1 1 1 1)插入排序1插入排序1O(nO(n2 2)稳定稳定稳定稳定直接插入排序的算法直接插入排序的算法typedef int SortData;void InsertSort(SortData V,int n)/按非递减顺序对表进行排序按非递减顺序对表进行排序SortData tem

6、p;int i,j;for(i=1;i 0;j-)/从后向前顺序比较从后向前顺序比较if(temp Vj-1)Vj=Vj-1;else break;Vj=temp;?算法评价算法评价算法评价算法评价?时间复杂度时间复杂度时间复杂度时间复杂度?若待排序记录按关键字从小到大排列若待排序记录按关键字从小到大排列若待排序记录按关键字从小到大排列若待排序记录按关键字从小到大排列(正序正序正序正序)?关键字比较次数：关键字比较次数：关键字比较次数：关键字比较次数：112=nni?记录移动次数：记录移动次数：记录移动次数：记录移动次数：)1(222=nni?若待排序记录按关键字从大到小排列若待排序记录按关键

7、字从大到小排列若待排序记录按关键字从大到小排列若待排序记录按关键字从大到小排列(逆序逆序逆序逆序)?关键字比较次数关键字比较次数：2)1)(2(2+=nnini?记录移动次数：记录移动次数：记录移动次数：记录移动次数：2)1)(4()1(2+=+=nnini?若待排序记录是随机的，取平均值若待排序记录是随机的，取平均值?关键字比较次数：关键字比较次数：42n?记录移动次数记录移动次数记录移动次数记录移动次数：42nT(n)=O(n)?空间复杂度空间复杂度：S(n)=O(1)S(n)=O(1)?折半插入排序折半插入排序折半插入排序折半插入排序?2 2 2 2-路插入排序路插入排序路插入排序路插入

8、排序 直接插入排序的改进直接插入排序的改进直接插入排序的改进直接插入排序的改进折半插入排序折半插入排序折半插入排序折半插入排序(Binary Binary Binary Binary InsertsortInsertsortInsertsortInsertsort)基本思想基本思想设在顺序表中有一 个对象序列设在顺序表中有一 个对象序列 V0,V1,Vn-1。其中。其中,V0,V1,Vi-1 是已经排好序的对象。在插入是已经排好序的对象。在插入Vi 时时,利用折半搜索法寻找利用折半搜索法寻找Vi 的插入位置。的插入位置。折半插入排序的算法折半插入排序的算法typedef int SortDat

9、a;void BinInsSort(SortData V,int n)SortData temp;int Left,Right;for(int i=1;i n;i+)Left=0;Right=i-1;temp=Vi;while(Left=Right)int mid=(Left+Right)/2;if(temp=Left;k-)Vk+1=Vk;/记录后移记录后移VLeft=temp;/插入插入 2 2 2 2-路插入排序路插入排序路插入排序路插入排序 例：给定以下关键字：例：给定以下关键字：初始状态初始状态49 38 65 97 76 13 27 49 i=1 (49 )i=2 (49 )(38

10、)i=3 (49 65)(38)i=4 (49 65 97)(38)i=5 (49 65 76 97)(38)i=6 (49 65 76 97)(13 38)i=7 (49 65 76 97)(13 27 38)i=8 (49 4965 76 9713 27 38)final first 插入排序2插入排序2 希尔排序希尔排序希尔排序希尔排序基本思想基本思想：分割成若干个较小的子文件，对各个子文件分别进行直接插入排序，当文件达到基本有序时，再对整个文件进行一次直接插入排序。：分割成若干个较小的子文件，对各个子文件分别进行直接插入排序，当文件达到基本有序时，再对整个文件进行一次直接插入排序。49

11、 38 65 97 76 13 27 49 55 4d=3一趟排序结果：二趟排序结果：d=1d=513 27 49 55 4 49 38 65 97 76三趟排序结果：13 4 4938 27 49 55 65 97 764 13 27 38 4949 55 65 76 97 插入排序3插入排序3typedef int SortData;void ShellSort(SortData V,int n)SortData temp;int gap=n/2;/gap是间隔是间隔while(gap!=0)/循环循环,直到直到gap为零为零for(int i=gap;i=gap;j=j-gap)if(t

12、emp 1&change;-i)/bubble_sort for(i=n-1,change=TRUE;i1&change;-i)/bubble_sort change=FALSEchange=FALSE;/change 为元素进行交换标志/change 为元素进行交换标志forfor(j=0;j aj+1)(j=0;j aj+1)aj aj+1;change=TRUEaj aj+1;change=TRUE;/一趟起泡;/一趟起泡时间复杂度:时间复杂度:O(nO(n2 2)?算法描述?算法评价?时间复杂度时间复杂度?最好情况（正序最好情况（正序）?比较次数：n-1?移动次数：0?最坏情况（逆序最

13、坏情况（逆序）?比较次数：)(21)(211nninni=?移动次数：)(23)(321nninni=?空间复杂度空间复杂度：S(n)=O(1)T(n)=O(n)快速排序快速排序快速排序快速排序交换排序2交换排序2快速排序是目前内部排序中最快的方法。快速排序是目前内部排序中最快的方法。基本思想：基本思想：基本思想：基本思想：选取某个记录，（通常选文件的第一个记录），将所有关键字不大于它的记录放在它的前面，将所有关键字不小于它的记录放在它的后面，这样遍历一趟文件后，将文件以该记录为界分为两部分，然后对各部分重复上述过程，直到每一部分仅剩一个记录为止。选取某个记录，（通常选文件的第一个记录），将所

14、有关键字不大于它的记录放在它的前面，将所有关键字不小于它的记录放在它的后面，这样遍历一趟文件后，将文件以该记录为界分为两部分，然后对各部分重复上述过程，直到每一部分仅剩一个记录为止。快速排序的效率跟初始文件中关键字的排列有关。快速排序的效率跟初始文件中关键字的排列有关。?快速排序?排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，x=rp.key?初始时令i=s,j=t?首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换?再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换?重复上述两步，直至i=j为止?再分别对两个子序列进行快速排序

15、，直到每个子序列只含有一个记录为止例初始关键字：4938 65 97 76 13 27 50 ijxji完成一趟排序：(27 38 13)49(76 97 65 50)分别进行快速排序：(13)27 (38)49(50 65)76 (97)快速排序结束：1327 38 4950 6576 974927ijijij4965ji1349ij4997ijVoid QuickSort(ElemType a,int s,int t)/采用快速排序方法对数组a中as-at区间进行排序/开始进行非递归调用时s和t的初值应分别为0和n-1/对当前排序区间进行一次划分Int I=s,j=t+1;/给I 和 j初

16、值ElemType x=as;/把基准元素的值暂存X中DoDo j-;while(aj.stn x.stn);/从后先前顺序查找一个要向前一区间交换的元素Do i+;whie(ai.stn x.stn);/从前先后顺序查找一个要向后一区间交换的元素If(ij)/当条件成立时交换ai aj的值ElemType temp=ai;ai=aj;aj=temp;While(ij);/条件成立时继续进行一次划分中的比较和交换As=aj;aj=x;/交换as和aj的值，得到前后两后两个子区间If(sj-1)QuickSort(a,s,j-1);/在当前左区间内超过一个元素的情况下递归处理左区间If(j+1)

17、QuickSort(a,j+1,t)/在当前右区间内超过一个元素的情况下递归处理右区间?void QSort(SqList&L,intlow,inthigh)/对顺序表L中的子序列L.rrow,high作快速排序if(lowhigh)/长度大于1?pivotloc=Partition(L,low,high);/将L.rlow,high一分为二?QSort(L,low,pivotloc-1);/对低子表递归排序，pivotloc是枢轴位置?QSort(L,pivotloc,high);/对高字表递归排序 intPartition(Sqlist&L,intlow,inthigh)/交换顺序表中字表

18、rlow,high的记录，枢轴记录到位，并返回其所在位，L.r0=L.rlow;/用第一个记录作枢轴记录pivotkey=L.rlow.key;/枢轴记录关键字while(lowhigh)/从表的两端交替向中间扫描while(low=pivotkey)-high;L.rlow=L.rhigh;/将比枢轴记录小的记录移到底端while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;/将比枢轴记录大的记录移到高端 L.rlow=L.r0;/枢轴记录到位return low;/返回枢轴位置?算法描述?算法评价?时间复杂度?最好情况（每次总是选到中间值

19、作枢轴）T(n)=O(nlogn)?最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n)?理想状态下T(n)=O(nlogn)?空间复杂度：需栈空间以实现递归?最坏情况：S(n)=O(n)?一般情况：S(n)=O(log2n)例：给定以下关键字：例：给定以下关键字：初始状态初始状态49 38 65 97 76 1327 49 第 一趟第 一趟13 13 38 65 97 76 49 2749 第 二趟第 二趟13 13 272765 97 76 49 38 49 第 三趟第 三趟13 13 2727383897 76 4965 49 第 四趟第 四趟13 13 27273838494

20、976 97 65 49 最后结果最后结果13 13 2727383849494949 656576769797 简单选择排序简单选择排序简单选择排序简单选择排序基本思想基本思想：对文件进行：对文件进行n-1趟排序，第趟排序，第i趟趟(i=1,2,.n-1)是在从到是在从到 n的的n-i+1个记录中选择关键字最小的记录，并将它与第个记录中选择关键字最小的记录，并将它与第i记录进行交换。记录进行交换。选择排序选择排序O(nO(n2 2)稳定稳定稳定稳定?Void SelectSort(ElemType a,int n)?ElemTYpe x;?Int I,j,k;?For(i=1;i=n;i+)

21、?K=i;/用K保存当前得到的最小排序元素下标，初值为I?For(j=i+1;j=n;j+)?/从当前排序区间中顺序查找出具有最小排序的元素ak?If(aj.stn ak.stn)?k=j;?If(k!=i)/把ak对调到此排序区间的第一个位置，即i-1位置?X=ai;ai=ak;ak=x;?堆排序堆排序堆排序堆排序?堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik2i+1例（96，83，27，38，11，9）例（13，38，27，50，76，65，49，97）9627911388313273849

22、65765097可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值?堆排序堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫个元素的次小值；重复执行，得到一个有序序列，这个过程叫?堆排序需解决的两个问题堆排序需解决的两个问题：?如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？?如何在输出堆顶

23、元素之后，调整剩余元素，使之成为一如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？个新的堆？?第二个问题解决方法第二个问题解决方法筛选筛选?方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”例13273849657650979727384965

24、765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 27 384965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 657665

25、972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 97?假定待排序的n相元素存放于一维数组a中，则对ai进行筛选的算法为：?Void sift(ElemTYpe a,int n)?ElemTYpe x=ai;/待筛结点暂存于x中?Int j=2*i+1;/aj是ai的左孩子?While(j=n-1)?/当ai的左孩子不为空时循环?If(j aj+1.stn)?J+;/若右孩子的排序码较小，则把j修改为右孩子的下标?If(x.

26、stn aj.stn)?Ai=aj;/将aj调到双亲位置上?I=j;j=2*i+1;/修改i和j的值，以便继续筛?Else?Break;/若找到x的最终位置，终止?Ai=x;/被筛结点的值放入最终位置?第一个问题解决方法第一个问题解决方法?如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？?方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例 含8个元素的无序序列（49，38，65，97，76，13，27，50）496538271376975049653827137650974913382765765097491338

27、27657650971327384965765097练习?判别（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是请调整成堆?Void HeapSort(ElemType a,int n)?ElemTYpe x;?Int I;?For(i=n/2-1;i=0;i-)?Sift(a,n,i);/建立初始堆?For(i=1;i=n-1;i+)?/进行n-1次for,完成堆排序?X=a0;a0=an-i;an-i=x;/将树根结点的值同当前区间内最后一个结点的值对换?Sift(a,n-I,0);/筛a0结点，得到n-i个结点堆?算法评价?时间复杂度：最坏情况下T(n)=O

28、(nlogn)?空间复杂度：S(n)=O(1)归并排序归并排序归并排序归并排序 例：给定以下关键字：例：给定以下关键字：初始状态初始状态 49 38 65 97 76 13 27 第一趟第一趟 38 49 65 97 13 76 27 第二趟第二趟 38 49 65 97 13 27 76 最后结果最后结果 13 27 38 49 65 76 97 归并排序归并排序基本思想基本思想：将文件的每个记录视为一个有序子文件；然后两两子文件进行：将文件的每个记录视为一个有序子文件；然后两两子文件进行2-路归并；重复，直到只剩一个长度为路归并；重复，直到只剩一个长度为n的有序文件的有序文件O(nlogn

29、O(nlogn)不稳定不稳定不稳定不稳定?算法描述?算法评价?时间复杂度：T(n)=O(nlog2n)?空间复杂度：S(n)=O(n)多关键字排序：多关键字排序：例对52张扑克牌按以下次序排例对52张扑克牌按以下次序排2323AA 22 33 AA 22 33 A23A23AA两个关键字：花色（两个关键字：花色（）面值（23面值（23A）A）并且“花色”地位高于“面值并且“花色”地位高于“面值 基数排序基数排序基数排序基数排序基数排序基数排序基数排序的步骤基数排序的步骤 从关键字的低位开始进行第 从关键字的低位开始进行第i趟趟(i=1,2,.d)分配即将单链表中的记录依次按关键字的第分配即将单

30、链表中的记录依次按关键字的第i位分配到相应编号的队列中；分配完毕后，将各队列的记录按队列编号顺序收集成一个单链表；重复，直到第位分配到相应编号的队列中；分配完毕后，将各队列的记录按队列编号顺序收集成一个单链表；重复，直到第d趟收集完毕，所得单链表已成为有序表。趟收集完毕，所得单链表已成为有序表。基数排序基数排序基数排序基数排序法是一种用多关键字排序思想对单逻辑关键字法是一种用多关键字排序思想对单逻辑关键字法是一种用多关键字排序思想对单逻辑关键字法是一种用多关键字排序思想对单逻辑关键字进行排序，而无需进行关键字比较的新排序方法，其基本操进行排序，而无需进行关键字比较的新排序方法，其基本操进行排序

31、，而无需进行关键字比较的新排序方法，其基本操进行排序，而无需进行关键字比较的新排序方法，其基本操作是作是作是作是“分配分配分配分配”和和和和“收集收集收集收集”。例初始状态：例初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配一趟分配930063083184505278008109589269一趟收集：一趟收集：505008109930063269278083184589二趟收集：二趟收集：0831845890635052699

32、30e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配二趟分配008109278930063083184505278008109589269一趟收集：一趟收集：008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配三趟分配063083269278505589505008109930063269278083184589二趟收集：二趟收集：?算法评价算法评价?时间复杂度：时间复杂度：?分配：T(n)=O(n)分配：T(n)=

33、O(n)?收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：n收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：n记录数d记录数d关键字数rd关键字数rd关键字取值范围关键字取值范围?空间复杂度：S(n)=2rd个队列指针+n个指针域空间空间复杂度：S(n)=2rd个队列指针+n个指针域空间各种排序方法的比较各种排序方法的比较各种排序方法的比较各种排序方法的比较 比较次数比较次数 移动次数移动次数附加存储附加存储排排 序序 方方 法法最好最好最最差差最好最好最最差差稳定稳定 性性最好最好最最差差直接插入排序直接插入排序nn2 0n2 1折半插入排序折半插入排序n log2n

34、 0n2 1起泡排序起泡排序nn2 0n2 1快速排序快速排序nlog2nn2n log2nn2 log2nn2简单选择排序简单选择排序n2 0n 1锦标赛排序锦标赛排序n log2nn log2n n堆排序堆排序n log2nn log2n 1归并排序归并排序n log2nn log2n n树型排序树型排序各种排序方法的选用各种排序方法的选用迄今为止，已有的排序方法远远不止本章讨论的这些方法，人们之所以热衷于研究多种排序方法，不仅是由于排序在计算机中所处的重要地位，而且还因为不同的方法各有其优缺点，可适用于不同的场合。选取排序方法时需要考虑的因素有：迄今为止，已有的排序方法远远不止本章讨论的

35、这些方法，人们之所以热衷于研究多种排序方法，不仅是由于排序在计算机中所处的重要地位，而且还因为不同的方法各有其优缺点，可适用于不同的场合。选取排序方法时需要考虑的因素有：待排序的记录数目待排序的记录数目n；记录本身信息量的大小；关键字的结构及分布情况；对排序稳定性的要求；语言工具的条件，辅助空间的大小等。依据这些因素，可得出如下几点结论：；记录本身信息量的大小；关键字的结构及分布情况；对排序稳定性的要求；语言工具的条件，辅助空间的大小等。依据这些因素，可得出如下几点结论：（1）若）若n较小（譬如较小（譬如n50)，可采用直接插入排序或直接选择。由于直接插入排序所需记录移动操作较直接选择排序多，

36、因此若记录本身信息量较大时，则选用直接选择排序为宜。，可采用直接插入排序或直接选择。由于直接插入排序所需记录移动操作较直接选择排序多，因此若记录本身信息量较大时，则选用直接选择排序为宜。（2）若文件的初始状态已是按关键字基本有序，则选用直接插入排序为宜。）若文件的初始状态已是按关键字基本有序，则选用直接插入排序为宜。（3）若）若n较大，则应采用时间复杂度为较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序的排序方法：快速排序堆排序或归并排序，快速排序是目前基于内部排序的中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最少，但堆排序所需的辅助空间少于快速排序，并

37、且不会出现序可能出现的最坏情况，这两种排序方法都是不稳定的，若要求排序稳定则可选用归并排序。堆排序或归并排序，快速排序是目前基于内部排序的中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最少，但堆排序所需的辅助空间少于快速排序，并且不会出现序可能出现的最坏情况，这两种排序方法都是不稳定的，若要求排序稳定则可选用归并排序。（4）前面讨论的排序算法，当记录本身信息量较大时，为了避免浪费大量时间移动记录，可以用链表作为存储结构，如插入排序和归并排序都易于在链表上实现，并分别称之为表和归并表，但有的方法，如快速排序和堆排序，在链表上难于实现，在这种情况下，可以提取关键字建立索引表，然后，对索引表进行排序。然而更为简单的方法是）前面讨论的排序算法，当记录本身信息量较大时，为了避免浪费大量时间移动记录，可以用链表作为存储结构，如插入排序和归并排序都易于在链表上实现，并分别称之为表和归并表，但有的方法，如快速排序和堆排序，在链表上难于实现，在这种情况下，可以提取关键字建立索引表，然后，对索引表进行排序。然而更为简单的方法是;引入一个整形向量作为辅助表，排序前，若排序算法中要求交换，则只需交换引入一个整形向量作为辅助表，排序前，若排序算法中要求交换，则只需交换RI和和Rj即可，排序结束后，向量就指示了记录之间的顺序关系即可，排序结束后，向量就指示了记录之间的顺序关系