第9章-排序分析优秀PPT.ppt

第九章 排 序19.1基本概念基本概念9.2插入排序插入排序9.3交换排序交换排序9.4选择排序选择排序本章书目本章书目 9.5归并排序归并排序9.6基数排序基数排序9.7各种内排序的比较各种内排序的比较小结与习题小结与习题29.1 9.1 基本概念基本概念排序排序1排序的分类排序的分类2内排序内排序33排序排序排序的定义排序的定义给定一个记录集合（给定一个记录集合（r1,r2,rn），），其相应的关键码分别为（其相应的关键码分别为（k1,k2,kn），），排序是将这些记录排成依次为排序是将这些记录排成依次为（rs1,rs2,rsn）的一个序列，使得相）的一个序列，使得相应的关键码满足应的关键码满足ks1ks2ksn（非降（非降序或升序）或序或升序）或ks1ks2ksn（非升序（非升序或降序）。或降序）。4排序算法的稳定性排序算法的稳定性若对随意的数据元素序列，运用某个若对随意的数据元素序列，运用某个排序方法，对它按关键码进行排序排序方法，对它按关键码进行排序若相同关键码元素间若相同关键码元素间的位置关系，排序前的位置关系，排序前与排序后保持一样，与排序后保持一样，称此排序方法是稳定称此排序方法是稳定的；的；不能保持一样的排不能保持一样的排序方法则称为不稳序方法则称为不稳定的。定的。5排序的分类排序的分类依据参与排序的数据元素（记录）是否全部依据参与排序的数据元素（记录）是否全部放置在内存中可把排序分为内排序和外排序。放置在内存中可把排序分为内排序和外排序。内排序：指待排序列完全存放在内存中所内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。进行的排序过程，适合不太大的元素序列。外排序：指排序过程中还需访问外存储器，外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，足够大的元素序列，因不能完全放入内存，只能运用外排序。只能运用外排序。6排序的分类排序的分类依据排序所依据的关键码的个数可以依据排序所依据的关键码的个数可以把排序分为单键排序和多键排序。把排序分为单键排序和多键排序。单键排序：依据一个关键码进行的排单键排序：依据一个关键码进行的排序。序。多键排序：依据多个关键码进行的排多键排序：依据多个关键码进行的排序。序。7排序的分类排序的分类依据排序的方法是否建立在关键码比较的基依据排序的方法是否建立在关键码比较的基础上可以把排序分为：础上可以把排序分为：基于比较：主要是通过关键码之间的比较和基于比较：主要是通过关键码之间的比较和记录的移动这两种操作来实现的排序。记录的移动这两种操作来实现的排序。不基于比较：依据待排序数据的特点所实行不基于比较：依据待排序数据的特点所实行的其它方法，通常是没有大量的关键码之间的其它方法，通常是没有大量的关键码之间的比较和记录的移动操作的排序。的比较和记录的移动操作的排序。8内排序的方法内排序的方法内部排序的过程是一个内部排序的过程是一个逐步扩大逐步扩大记录的记录的有有序序列长度序序列长度的过程。的过程。经过一趟排序经过一趟排序有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区9内排序的主要方法内排序的主要方法选择类选择类交换类交换类归并类归并类插入类插入类各种各种排序排序直接直接插入插入折半折半插入插入表表插入插入希尔希尔将无序子序列中的一个或几个将无序子序列中的一个或几个记录记录“插入插入”到有序序列中，到有序序列中，从而增加记录的有序子序列的从而增加记录的有序子序列的长度，最终完全排序工作。长度，最终完全排序工作。10内排序的主要方法内排序的主要方法选择类选择类交换类交换类归并类归并类插入类插入类各种各种排序排序冒泡排序冒泡排序快速排序快速排序通过通过“交换交换”无序序列中的记无序序列中的记录从而得到其中关键字最小或录从而得到其中关键字最小或最大的记录，并将它加入到有最大的记录，并将它加入到有序子序列中，以此方法增加记序子序列中，以此方法增加记录的有序子序列的长度。录的有序子序列的长度。11内排序的主要方法内排序的主要方法选择类选择类交换类交换类归并类归并类插入类插入类各种各种排序排序从记录的无序子序列中从记录的无序子序列中“选择选择”关键字关键字最小或最大最小或最大的记录，的记录，并将它并将它加入到有序子序列加入到有序子序列中，中，以此方法增加记录的有序子序以此方法增加记录的有序子序列的长度。列的长度。简单简单选择选择树形树形选择选择堆排序堆排序12内排序的主要方法内排序的主要方法选择类选择类交换类交换类归并类归并类插入类插入类各种各种排序排序二路归并二路归并排序排序通过通过“归并归并”两个或两个以上两个或两个以上的记录有序子序列，逐步增加的记录有序子序列，逐步增加记录有序序列的长度。记录有序序列的长度。139.2 9.2 插入排序插入排序 直接插入排序直接插入排序1折半插入排序折半插入排序2表插入排序表插入排序3希尔排序希尔排序414算法思想算法思想仅有一个记录的表总是有序的，因此，仅有一个记录的表总是有序的，因此，对于对于n个记录的表，可从其次个记录起个记录的表，可从其次个记录起先直到第先直到第n个记录，逐个向有序表中进个记录，逐个向有序表中进行插入操作，从而得到行插入操作，从而得到n个记录按关键个记录按关键码有序的表。码有序的表。干脆插入排序干脆插入排序15干脆插入排序干脆插入排序操作步骤：操作步骤：Step1:选取选取L.key1 作为初始的有序序列作为初始的有序序列,i=2;Step2:将将L.keyi插入到前面的有序序列中，使插入到前面的有序序列中，使 其有序序列长度增加其有序序列长度增加1；Step3:i=i+1，若，若i的值小于表长，则重复的值小于表长，则重复Step2，否则排序结束。否则排序结束。16干脆插入排序干脆插入排序算法分析：算法分析：空间效率：仅用了一个协助单元，空间效率：仅用了一个协助单元，O(1)。时间效率：时间效率：最好状况下：初始序列是依次的最好状况下：初始序列是依次的最坏状况下：初始序列是逆序的最坏状况下：初始序列是逆序的平均状况下：初始序列是无序的平均状况下：初始序列是无序的稳定性：是一种稳定的排序方法。稳定性：是一种稳定的排序方法。17干脆插入排序干脆插入排序总比较次数=n-1 最好最好最坏最坏平均平均总移动次数=2(n-1)18折半插入排序折半插入排序算法思想算法思想设在依次表中有一设在依次表中有一个对象序列个对象序列V0,V1,Vn-1。其中。其中,V0,V1,Vi-1是已经排好序的对象。在插入是已经排好序的对象。在插入Vi时时,利用折半查找法找寻利用折半查找法找寻Vi的插的插入位置。入位置。19折半插入排序折半插入排序n操作步骤：操作步骤：nStep1:依次表中前依次表中前j-1个记录有序，将第个记录有序，将第j个个记录插入。记录插入。n令令low=1；high=j-1；r0=rj；nStep2:若若lowhigh，得到插入位置，转，得到插入位置，转Step5;nStep3:若若lowhigh，则取有序子表的中点，则取有序子表的中点nm=(low+high)/2；nStep4:若若r0.keyr0.next；将；将i指向指向第一个记录位置；第一个记录位置；Step2:若若i=l-length时，调整结束；否则时，调整结束；否则:2.1若若i=j，j=l-rj.next；数据元素应在这重量中，不用调整处理下；数据元素应在这重量中，不用调整处理下一个结点：一个结点：i+；转；转Step2；2.2若若ji，则，则l-ri.eleml-rj.elem；保存下一个结点地址：；保存下一个结点地址：p=l-rj.next；同时保持后续链表不被中断：；同时保持后续链表不被中断：l-rj.next=l-i.next；l-i.next=j；指向下一个处理的结点：；指向下一个处理的结点：j=p；i+；转；转Step2;2.3若若ji，j重量中原记录已移走，沿重量中原记录已移走，沿j的指针域找寻原记录的位置：的指针域找寻原记录的位置：while(jrj.next；转到；转到2.1。24表插入排序表插入排序举例说明举例说明Play25表插入排序表插入排序算法分析：算法分析：时间困难度：设有序表长度为时间困难度：设有序表长度为i，则须要比较，则须要比较至多至多i+1次，修改指针两次。因此，总比较次次，修改指针两次。因此，总比较次数与干脆插入排序相同，修改指针总次数为数与干脆插入排序相同，修改指针总次数为2n次。所以，时间困难度仍为次。所以，时间困难度仍为O(n2)。空间困难度：表插入排序的空间困难度为空间困难度：表插入排序的空间困难度为O(1)。稳定性：表插入排序是一种稳定的排序方法。稳定性：表插入排序是一种稳定的排序方法。26希尔排序希尔排序算法思想算法思想先将整个待排记录分割成若干个子先将整个待排记录分割成若干个子序列，在子序列中分别进行干脆插序列，在子序列中分别进行干脆插入排序，待整个序列基本有序的时入排序，待整个序列基本有序的时候，再对全体序列进行一次干脆插候，再对全体序列进行一次干脆插入排序。入排序。27希尔排序希尔排序操作步骤：操作步骤：Step1:选择一个步长序列选择一个步长序列t1，t2，tk，其，其中中 titj，tk=1；Step2:按步长序列个数按步长序列个数k，对序列进行，对序列进行k趟排序；趟排序；Step3:每趟排序，依据对应的步长每趟排序，依据对应的步长ti，将待排，将待排序列分割序列分割 成若干长度为成若干长度为m的子序列，分别对各子的子序列，分别对各子表进行直表进行直 接插入排序。仅步长因子为接插入排序。仅步长因子为1时，整个时，整个序列作为序列作为 一个表来处理，表长度即为整个序列的一个表来处理，表长度即为整个序列的长度。长度。28希尔排序希尔排序举例说明：举例说明：Play29希尔排序希尔排序算法分析：算法分析：时间困难度：由于希尔排序是依靠于增量的时间困难度：由于希尔排序是依靠于增量的选取，它的时间困难度是在选取，它的时间困难度是在O(nlog2n)O(n2)之间。之间。空间困难度：在希尔排序的过程中只须要一空间困难度：在希尔排序的过程中只须要一个协助空间用于暂存当前待插入的记录，因个协助空间用于暂存当前待插入的记录，因此，希尔排序的空间困难度为此，希尔排序的空间困难度为O(1)。稳定性：希尔排序方法是一种不稳定的排序稳定性：希尔排序方法是一种不稳定的排序方法。方法。309.3 9.3 交换排序交换排序冒泡排序冒泡排序1快速排序快速排序231冒泡排序冒泡排序假设在排序过程中，记录序列假设在排序过程中，记录序列R1.n的状态为：的状态为：第第 i 趟冒泡排序趟冒泡排序无序序列无序序列R1.n-i+1有序序列有序序列 Rn-i+2.nn-i+1无序序列无序序列R1.n-i有序序列有序序列 Rn-i+1.n比较相邻记录，将关比较相邻记录，将关键字最大的记录键字最大的记录交换交换到到 n-i+1 的位置上的位置上32冒泡排序冒泡排序算法思想算法思想对对n个记录的表，第一趟冒泡得到一个记录的表，第一趟冒泡得到一个关键码最大的记录个关键码最大的记录rn，其次趟冒，其次趟冒泡对泡对n-1个记录的表，再得到一个关个记录的表，再得到一个关键码最大的记录键码最大的记录rn-1，如此重复，如此重复，直到直到n个记录按关键码有序的表。个记录按关键码有序的表。33冒泡排序冒泡排序一趟冒泡方法：一趟冒泡方法：Step1:i=1；/设置从第一个记录起先进设置从第一个记录起先进行两两比较行两两比较Step2:若若ij，一趟冒泡结束。，一趟冒泡结束。Step3:比较比较ri.key与与ri+1.key，若，若ri.keyri+1.key，不交换，转，不交换，转Step5;Step4:当当ri.keyri+1.key时，时，r0=ri；ri=ri+1；ri+1=r0；/将将ri与与ri+1交换交换Step5:i=i+1；对下两个记录进行两两比较，；对下两个记录进行两两比较，转转Step2;34冒泡排序冒泡排序操作步骤：操作步骤：Step1:从从n记录的表尾起先，记录的表尾起先，j=n；Step2:若若jri+1.key时，时，将将ri与与ri+1交换交换;Step7:i=i+1；调整对下两个记录进行两两比较，调整对下两个记录进行两两比较，转转Step4;36冒泡排序冒泡排序语言描述语言描述:templatevoidBubbleSort(SqList&L)for(inti=1;iL.length;i+)/用用i限制比限制比较趟数共较趟数共n-1趟趟typet;/协助变量，作交协助变量，作交换用换用for(intj=1;jL.keyj+1)t=L.keyj;L.keyj=L.keyj+1;L.keyj+1=t;/交换交换L.keyj和和L.keyj+1的值的值37冒泡排序冒泡排序算法分析：算法分析：空间困难度：冒泡排序的空间困难度为空间困难度：冒泡排序的空间困难度为O(1)。时间困难度：总共要进行时间困难度：总共要进行n-1趟冒泡，对趟冒泡，对j个个记录的表进行一趟冒泡须要记录的表进行一趟冒泡须要j-1次关键码比较。次关键码比较。冒泡排序的时间困难度为冒泡排序的时间困难度为O(n2)。稳定性：冒泡排序是一种稳定的排序方法。稳定性：冒泡排序是一种稳定的排序方法。38快速排序快速排序算法思想：算法思想：找一个记录，以它的关键字作为找一个记录，以它的关键字作为“枢轴枢轴”，凡其，凡其关键字关键字小于枢轴小于枢轴的记录均移动至该的记录均移动至该记录之前记录之前，反，反之，凡关键字之，凡关键字大于枢轴大于枢轴的记录均移动至该的记录均移动至该记录之记录之后后。致使一趟排序之后，记录的无序序列。致使一趟排序之后，记录的无序序列Rs.t将分割成两部分：将分割成两部分：Rs.i-1和和Ri+1.t，且，且 Rj.key Ri.key Rj.key (sji-1)枢轴枢轴 (i+1jt)。39快速排序快速排序示例示例stlowhigh设设 Rs=52 为枢轴为枢轴high23low80high14low52R052lowhighhighhighlow40快速排序快速排序操作步骤：操作步骤：Step1:假如待排子序列中元素的个数大于假如待排子序列中元素的个数大于1，则以，则以L.rlow作为枢轴，进行一次划分；作为枢轴，进行一次划分；否则排序结束。否则排序结束。Step2:对枢轴左半子序列重复对枢轴左半子序列重复Step1;Step3:对枢轴右半子序列重复对枢轴右半子序列重复Step1;41快速排序快速排序算法分析：算法分析：空间困难度：快速排序是递归的，递归调用空间困难度：快速排序是递归的，递归调用层次数与其二叉树的深度一样。因而，存储层次数与其二叉树的深度一样。因而，存储开销在志向状况下为开销在志向状况下为O(log2n)；在最坏状况；在最坏状况下，为下，为O(n)。时间困难度：最好状况下为时间困难度：最好状况下为O(nlog2n)，最，最坏状况，快速排序蜕化为冒泡排序。坏状况，快速排序蜕化为冒泡排序。稳定性：快速排序是一个不稳定的排序方法。稳定性：快速排序是一个不稳定的排序方法。429.4 9.4 选择排序选择排序简单选择排序简单选择排序1树形选择排序树形选择排序2堆排序堆排序343简洁选择排序简洁选择排序假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列 Ri.n 第第 i 趟趟简洁选择排序简洁选择排序从中选出关键字最小的记录有序序列R1.i无序序列 Ri+1.n44简洁选择排序简洁选择排序算法思想算法思想:第一趟，从第一趟，从n个记录中找出关键码最小个记录中找出关键码最小的记录与第一个记录交换；其次趟，的记录与第一个记录交换；其次趟，从其次个记录起先的从其次个记录起先的n-1个记录中再选个记录中再选出关键码最小的记录与其次个记录交出关键码最小的记录与其次个记录交换；如此，第换；如此，第i趟，则从第趟，则从第i个记录起先个记录起先的的n-i+1个记录中选出关键码最小的记个记录中选出关键码最小的记录与第录与第i个记录交换，直到整个序列按个记录交换，直到整个序列按关键码有序。关键码有序。45简洁选择排序简洁选择排序操作步骤：操作步骤：Step1:从从L.keyi 从从L.keylength记录中记录中选择选择一个关键字值一个关键字值最小最小的记录，将其下标保存至的记录，将其下标保存至min中；中；Step2:若若L.keyiL.keymin;则交换这两个记则交换这两个记录录;否则转否则转Step3;Step3:i=i+1,若若iL.length，则转，则转Step1;否则排否则排序结束。序结束。46简洁选择排序简洁选择排序算法分析：算法分析：时间困难度：从算法中可看出，简洁选择排时间困难度：从算法中可看出，简洁选择排序移动记录的次数较少，但关键码的比较次序移动记录的次数较少，但关键码的比较次数照旧是，算法的时间困难度仍是数照旧是，算法的时间困难度仍是O(n2)。空间困难度：简洁选择排序算法只须要一个空间困难度：简洁选择排序算法只须要一个协助空间来作为交换记录用的暂存单元。因协助空间来作为交换记录用的暂存单元。因此，它的空间困难度此，它的空间困难度O(1)。稳定性：简洁选择排序是一种稳定的排序方稳定性：简洁选择排序是一种稳定的排序方法。法。47树形选择排序树形选择排序操作步骤操作步骤:Step1:从最底层叶子结点起先，按层一一从最底层叶子结点起先，按层一一进行兄弟间的竞赛，关键字值较大者上升进行兄弟间的竞赛，关键字值较大者上升为子树根结点，直到树的顶层为止；为子树根结点，直到树的顶层为止；Step2:将树的根结点输出，把底层叶子中将树的根结点输出，把底层叶子中值相同的结点值改为值相同的结点值改为0；假如输出的结点；假如输出的结点总数小于初始时树的叶子结点总数，则重总数小于初始时树的叶子结点总数，则重复复Step1;否则结束排序。否则结束排序。48树形选择排序树形选择排序算法分析：算法分析：时间困难度：除了最大关键字之外，每选择时间困难度：除了最大关键字之外，每选择一个次大的关键字只须要进行一个次大的关键字只须要进行log2n次比较，次比较，因此，它的时间困难度为因此，它的时间困难度为O(nlogn)。空间困难度：须要附加空间困难度：须要附加n个协助空间用来保个协助空间用来保存排序的结果，还要存排序的结果，还要n-1个协助空间作为排个协助空间作为排序过程中运用。因此，它的空间困难度序过程中运用。因此，它的空间困难度O(n)。稳定性：树形选择排序是一种不稳定的排序稳定性：树形选择排序是一种不稳定的排序方法。这是因为在比较的过程中是跳动式进方法。这是因为在比较的过程中是跳动式进行的。行的。49堆排序堆排序堆的定义：堆的定义：第一种定义方式：第一种定义方式：设有设有n个元素的序列个元素的序列 k1，k2，kn，当且仅当满足下述关系之一时，称之为堆。，当且仅当满足下述关系之一时，称之为堆。其次种定义方式：其次种定义方式：堆是具有下列性质的完全二叉树：每个堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值结点的值都小于或等于其左右孩子结点的值（称为小根堆或小顶堆）；或者每个结点的（称为小根堆或小顶堆）；或者每个结点的值都大于或等于其左右孩子结点的值（称为值都大于或等于其左右孩子结点的值（称为大根堆或大顶堆）。大根堆或大顶堆）。iiiikkkk212+或 iiiikkkk212+（i=1,2,，n/2）50堆排序堆排序算法思想：算法思想：设有设有n个元素，将其按关键码排序。首先将这个元素，将其按关键码排序。首先将这n个元素按关键码个元素按关键码建成堆建成堆，将堆顶元素输出，得，将堆顶元素输出，得到到n个元素中个元素中关键码最小关键码最小(或最大或最大)的元素。然后，的元素。然后，再对剩下的再对剩下的n-1个元素建成堆，输出堆顶元素，个元素建成堆，输出堆顶元素，得到得到n个元素中关键码次小个元素中关键码次小(或次大或次大)的元素。如的元素。如此反复，便得到一个按关键码有序的序列。称此反复，便得到一个按关键码有序的序列。称这个过程为堆排序。这个过程为堆排序。51堆排序堆排序堆排序需解决的两个问题：堆排序需解决的两个问题：1.怎样建堆：怎样建堆：如何将如何将n个元素的序列按关键码个元素的序列按关键码建成堆；建成堆；2.怎样调整：怎样调整：输出堆顶元素后，怎样调整剩余输出堆顶元素后，怎样调整剩余n-1个元素，使其按关键码成为一个新堆。个元素，使其按关键码成为一个新堆。52堆排序堆排序建堆方法：建堆方法：先把待排序序列构造成一棵先把待排序序列构造成一棵完全二叉树完全二叉树;然后从下往上然后从下往上,自右而左进行筛选自右而左进行筛选,最终得到堆最终得到堆.36 30 91 47 24 12 5385 a.8a.8个结点的初始状态个结点的初始状态 例：例：53堆排序堆排序36 30 8585 4747 24 12 53 91 c.c.对第对第3 3个结点开始筛选个结点开始筛选b.b.从第从第4 4个结点起先筛选个结点起先筛选 36 30 91 47 24 12 5385 36 12 8585 4747 24 30 53 91 d.d.第第2 2个结点为根的子树已是堆个结点为根的子树已是堆54堆排序堆排序36 12 8585 4747 24 30 53 91 36 53 8585 4747 24 30 12 91 e.e.对整棵树进行筛选对整棵树进行筛选55堆排序堆排序操作步骤：操作步骤：Step1:i=1,对依次表对依次表L1L.lengh-i+1中中的建大顶堆；的建大顶堆；Step2:将堆顶元素和将堆顶元素和LL.lengh-i+1交换；交换；Step3:i=i+1,若若iv 或或 jt，则比较选取结束转，则比较选取结束转Step4；Step3:选取选取ri和和rj中关键码较小的存入协助中关键码较小的存入协助数组数组rf。假如。假如 ri.keyrj.key，则，则rfk=ri；i+；k+；否则，；否则，rfk=rj；j+；k+。转转Step2;Step4:将尚未处理完的子表中元素存入将尚未处理完的子表中元素存入rf：Step5:合并结束。合并结束。59二路归并排序二路归并排序递归算法操作步骤：递归算法操作步骤：Step1:将待排序的记录序列分为将待排序的记录序列分为两个相等两个相等的子序列，分别将这两个子序列进行排的子序列，分别将这两个子序列进行排序；序；Step2:调用一次归并算法调用一次归并算法Merge，将这两，将这两个有序子序列合并成一个含有全部记录个有序子序列合并成一个含有全部记录的有序序列。的有序序列。60二路归并排序二路归并排序算法分析算法分析:时间困难度：归并过程对应由叶向根生时间困难度：归并过程对应由叶向根生成一棵二叉树的过程，所以归并趟数约成一棵二叉树的过程，所以归并趟数约等于二叉树的高度等于二叉树的高度-1，即，即log2n，每趟，每趟归并需移动记录归并需移动记录n次，故时间困难度为次，故时间困难度为O(nlog2n)。空间困难度：须要一个与表等长的协助空间困难度：须要一个与表等长的协助元素数组空间，所以空间困难度为元素数组空间，所以空间困难度为O(n)。稳定性：由一次归并算法中的稳定性：由一次归并算法中的if语句可语句可知，二路归并算法是一种稳定的算法。知，二路归并算法是一种稳定的算法。619.6 9.6 基数排序基数排序基数排序是一种借助基数排序是一种借助“多关键字排序多关键字排序”的思想来实现的思想来实现“单关键字排序单关键字排序”的的内部排序算法内部排序算法。多关键码排序多关键码排序1链式基数排序链式基数排序262多关键码排序多关键码排序定义：定义：n个记录的序列个记录的序列R1,R2,，Rn对关键对关键字字(Ki1,Ki2,Kid)有序是指：对于序列有序是指：对于序列中随意两个记录中随意两个记录Ri和和Rj(1ijn)都满足都满足下列下列(词典词典)有序关系：有序关系：(Ki1,Ki2,Kid)(Kj1,Kj2,Kjd)，其中，其中:K1被称为被称为“最主最主”位关键字，位关键字，Kd被称为被称为“最次最次”位关位关键字。键字。63多关键码排序多关键码排序两种方法两种方法最高位优先最高位优先MSD法法先对先对K1进行排序，并按进行排序，并按K1的不同值将记录的不同值将记录序列分成若干子序列之后，分别对序列分成若干子序列之后，分别对K2进行进行排序，排序，.，依次类推，直至最终对最次依次类推，直至最终对最次位关键字排序完成为止。位关键字排序完成为止。最低位优先最低位优先LSD法法先对先对Kd进行排序，然后对进行排序，然后对Kd-1进行排序，进行排序，依次类推，直至对最主位关键字依次类推，直至对最主位关键字K1排序完排序完成为止。成为止。64多关键码排序多关键码排序例如例如:学生记录含三个关键字学生记录含三个关键字:系别、班号和系别、班号和班内的序列号，其中以系别为最主位关键字。班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下的排序过程如下:无序序列无序序列对对K3排序排序对对K2排序排序对对K1排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,3065链式基数排序链式基数排序算法思想：算法思想：从最低位关键码起，按关键码的不同值从最低位关键码起，按关键码的不同值将序列中的记录将序列中的记录“安排安排”到到RADIX个个队列中，然后再队列中，然后再“收集收集”之。如此重复之。如此重复d次即可。链式基数排序是用次即可。链式基数排序是用RADIX个个链队列作为安排队列，关键码相同的记链队列作为安排队列，关键码相同的记录存入同一个链队列中，收集则是将各录存入同一个链队列中，收集则是将各链队列按关键码大小依次链接起来。链队列按关键码大小依次链接起来。66链式基数排序链式基数排序操作步骤：操作步骤：Step1:初始化，建立待排序列的静态初始化，建立待排序列的静态链表链表SL；Step2:从最低位关键码起先，按关键从最低位关键码起先，按关键码值将码值将SL中记录安排到各个单链表中；中记录安排到各个单链表中；Step3:依据关键码的值，从小到大将依据关键码的值，从小到大将各个单链表进行收集，重复各个单链表进行收集，重复Step2，直，直到排序完成。到排序完成。67链式基数排序链式基数排序例：例：初始状态：初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配930063083184505278008109589269一趟收集：一趟收集：68链式基数排序链式基数排序505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集：一趟收集：69链式基数排序链式基数排序008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集：二趟收集：70链式基数排序链式基数排序算法分析：算法分析：时间效率：设待排序列为时间效率：设待排序列为n个记录，个记录，d个关键码，个关键码，关键码的取值范围为关键码的取值范围为radix，则进行链式基数排序，则进行链式基数排序的时间困难度为的时间困难度为O(d(n+radix)。空间效率：须要空间效率：须要2*radix个指向队列的协助空间，个指向队列的协助空间，以及用于静态链表的以及用于静态链表的n个指针。个指针。稳定性：在基数排序的过程中，并没有交换记录稳定性：在基数排序的过程中，并没有交换记录的前后位置，因此该排序方法是一种稳定的排序的前后位置，因此该排序方法是一种稳定的排序方法。方法。719.7 9.7 各种内部排序方法的比较各种内部排序方法的比较排序方法排序方法 平均情况平均情况 最好情况最好情况 最坏情况最坏情况 辅助空间辅助空间 直接插入排序直接插入排序 O(n2)O(n)O(n2)O(1)希尔排序希尔排序 O(nlog2n)O(n2)O(n1.3)O(n2)O(1)起泡排序起泡排序 O(n2)O(n)O(n2)O(1)快速排序快速排序 O(nlog2n)O(nlog2n)O(n2)O(log2n)O(n)简单选择排序简单选择排序 O(n2)O(n2)O(n2)O(1)堆排序堆排序 O(nlog2n)O(nlog2n)O(nlog2n)O(1)归归并排序并排序 O(nlog2n)O(nlog2n)O(nlog2n)O(n)基数排序基数排序 O(d(n+rd)O(d(n+rd)O(d(n+rd)O(rd)72小小 结结排序技术排序技术插入排序插入排序交换排序交换排序选择排序选择排序归并排序归并排序直直接接插插入入排排序序希希尔尔排排序序改进改进冒冒泡泡排排序序快快速速排排序序改进改进其它排序其它排序简简单单选选择择排排序序堆堆排排序序改进改进二二路路归归并并排排序序基基排排序序731 1、名词说明：、名词说明：排序，内部排序，外部排序，堆排序，内部排序，外部排序，堆 2 2、对于给定的一组键值：、对于给定的一组键值：8383，4040，6363，1313，8484，3535，9696，5757，3939，7979，6161，1515，分别画出应用干脆，分别画出应用干脆插入排序、干脆选择排序、快速排序、归并排序插入排序、干脆选择排序、快速排序、归并排序对上述序列进行排序中各趟的结果。对上述序列进行排序中各趟的结果。3 3、举例说明本章介绍的各排序方法中哪些是不稳定、举例说明本章介绍的各排序方法中哪些是不稳定的？的？4 4、编写一个双向气泡排序的算法，即相邻两遍向相、编写一个双向气泡排序的算法，即相邻两遍向相反方向起泡。反方向起泡。习习 题题745 5、设计一个用链表表示的干脆选择排序算法。、设计一个用链表表示的干脆选择排序算法。6 6、插入排序中找插入位置的操作可以通过二分法查、插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的插入排找的方法来实现。试据此写一个改进后的插入排序方法。序方法。7 7、一个线性表中的元素为正整数或负整数。设计一、一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表前一个算法，将正整数和负整数分开，使线性表前一半为负整数，后一半为正整数。不要求对这些元半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量削减交换次数。素排序，但要求尽量削减交换次数。8 8、试比较干脆插入排序、干脆选择排序、快速排序、试比较干脆插入排序、干脆选择排序、快速排序、堆排序、归并排序的时、空性能。堆排序、归并排序的时、空性能。习习 题题759 9、全国有、全国有1000010000人参与物理竞赛，只录用成果优异人参与物理竞赛，只录用成果优异的前的前1010名，并将他们从高分到低分输出。而对落名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种状况下，选的其他考生，不需排出名次，问此种状况下，用何种排序方法速度最快？为什么？用何种排序方法速度最快？为什么？1010、已知待排序的序列为（、已知待排序的序列为（503503，8787，512512，6161，908908，170170，897897，275275，653653，462462），试完成下列各题。），试完成下列各题。(1)(1)依据以上序列建立一个堆（画出第一步和最依据以上序列建立一个堆（画出第一步和最终堆的结果图），希望先输出最小值。终堆的结果图），希望先输出最小值。(2)(2)输出最小值后，如何得到次小值。（并画出输出最小值后，如何得到次小值。（并画出相应结果图）相应结果图）习习 题题76The End77