第9章-排序总结备课讲稿课件

第9章-排序总结9.1 9.1 基本概念基本概念排序排序1排序的分类排序的分类2内排序内排序32排序排序排序的定义排序的定义给定一个记录集合（给定一个记录集合（r1,r2,rn），），其相应的关键码分别为（其相应的关键码分别为（k1,k2,kn），），排序是将这些记录排成顺序为排序是将这些记录排成顺序为（rs1,rs2,rsn）的一个序列，使得相）的一个序列，使得相应的关键码满足应的关键码满足ks1ks2ksn（非降（非降序或升序）或序或升序）或ks1ks2ksn（非升序（非升序或降序）。或降序）。3排序算法的稳定性排序算法的稳定性若对任意的数据元素序列，使用某个若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序排序方法，对它按关键码进行排序若相同关键码元素间若相同关键码元素间的位置关系，排序前的位置关系，排序前与排序后保持一致，与排序后保持一致，称此排序方法是称此排序方法是稳定稳定的；的；不能保持一致的排不能保持一致的排序方法则称为序方法则称为不稳不稳定定的。的。4排序的分类排序的分类按照参加排序的数据元素（记录）按照参加排序的数据元素（记录）是否全部是否全部放置在内存中放置在内存中可把排序分为内排序和外排序。可把排序分为内排序和外排序。内排序：内排序：指待排序列完全存放在内存中所进行指待排序列完全存放在内存中所进行的排序过程，的排序过程，适合不太大的元素序列适合不太大的元素序列。外排序：外排序：指排序过程中还需访问外存储器，指排序过程中还需访问外存储器，足足够大的元素序列够大的元素序列，因不能完全放入内存，只能，因不能完全放入内存，只能使用外排序。使用外排序。5排序的分类排序的分类按照排序所按照排序所依据的关键码的个数依据的关键码的个数可以可以把排序分为单键排序和多键排序。把排序分为单键排序和多键排序。单键排序：单键排序：根据一个关键码进行的排序。根据一个关键码进行的排序。多键排序：多键排序：根据多个关键码进行的排序。根据多个关键码进行的排序。6排序的分类排序的分类按照排序的方法按照排序的方法是否建立在关键码比较是否建立在关键码比较的基的基础上可以把排序分为：础上可以把排序分为：基于比较基于比较：主要是通过关键码之间的比较和记主要是通过关键码之间的比较和记录的移动这两种操作来实现的排序。录的移动这两种操作来实现的排序。不基于比较不基于比较：根据待排序数据的特点所采取的根据待排序数据的特点所采取的其它方法，通常是没有大量的关键码之间的比其它方法，通常是没有大量的关键码之间的比较和记录的移动操作的排序。较和记录的移动操作的排序。7内排序的方法内排序的方法内部排序的过程是一个内部排序的过程是一个逐步扩大逐步扩大记录的记录的有有序序列长度序序列长度的过程。的过程。经过一趟排序经过一趟排序有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区8内排序的主要方法内排序的主要方法选择类选择类交换类交换类归并类归并类插入类插入类各种各种排序排序直接直接插入插入折半折半插入插入表表插入插入希尔希尔将无序子序列中的一个或几个将无序子序列中的一个或几个记录记录“插入插入”到有序序列中，到有序序列中，从而增加记录的有序子序列的从而增加记录的有序子序列的长度，最终完全排序工作。长度，最终完全排序工作。9内排序的主要方法内排序的主要方法选择类选择类交换类交换类归并类归并类插入类插入类各种各种排序排序冒泡排序冒泡排序快速排序快速排序通过通过“交换交换”无序序列中的记无序序列中的记录从而得到其中关键字最小或录从而得到其中关键字最小或最大的记录，并将它加入到有最大的记录，并将它加入到有序子序列中，以此方法增加记序子序列中，以此方法增加记录的有序子序列的长度。录的有序子序列的长度。10内排序的主要方法内排序的主要方法选择类选择类交换类交换类归并类归并类插入类插入类各种各种排序排序从记录的无序子序列中从记录的无序子序列中“选择选择”关键字关键字最小或最大最小或最大的记录，的记录，并将它并将它加入到有序子序列加入到有序子序列中，中，以此方法增加记录的有序子序以此方法增加记录的有序子序列的长度。列的长度。简单简单选择选择树形树形选择选择堆排序堆排序11内排序的主要方法内排序的主要方法选择类选择类交换类交换类归并类归并类插入类插入类各种各种排序排序二路归并二路归并排序排序通过通过“归并归并”两个或两个以上两个或两个以上的记录有序子序列，逐步增加的记录有序子序列，逐步增加记录有序序列的长度。记录有序序列的长度。129.2 9.2 插入排序插入排序 直接插入排序直接插入排序1折半插入排序折半插入排序2表插入排序表插入排序3希尔排序希尔排序413算法思想算法思想仅有一个记录的表总是有序的，因此，仅有一个记录的表总是有序的，因此，对于对于n个记录的表，可从第二个记录开个记录的表，可从第二个记录开始直到第始直到第n个记录，逐个向有序表中进个记录，逐个向有序表中进行插入操作，从而得到行插入操作，从而得到n个记录按关键个记录按关键码有序的表。码有序的表。直接插入排序直接插入排序14直接插入排序直接插入排序操作步骤：操作步骤：Step1:选取选取L.key1 作为初始的有序序列作为初始的有序序列,i=2;Step2:将将L.keyi插入到前面的有序序列中，使插入到前面的有序序列中，使 其有序序列长度增加其有序序列长度增加1；Step3:i=i+1，若，若i的值小于表长，则重复的值小于表长，则重复Step2，否则排序结束。否则排序结束。15直接插入排序直接插入排序算法分析：算法分析：空间效率：仅用了一个辅助单元，空间效率：仅用了一个辅助单元，O(1)。时间效率：时间效率：最好情况下：初始序列是顺序的最好情况下：初始序列是顺序的最坏情况下：初始序列是逆序的最坏情况下：初始序列是逆序的平均情况下：初始序列是无序的平均情况下：初始序列是无序的稳定性：是一种稳定性：是一种稳定稳定的排序方法。的排序方法。16直接插入排序直接插入排序总比较次数=n-1 最好最好最坏最坏平均平均总移动次数=2(n-1)17折半插入排序折半插入排序算法思想算法思想设在顺序表中有一设在顺序表中有一个对象序列个对象序列V0,V1,Vn-1。其中。其中,V0,V1,Vi-1是已经排好序的对象。在插入是已经排好序的对象。在插入Vi时时,利用折半查找法寻找利用折半查找法寻找Vi的插的插入位置。入位置。18折半插入排序折半插入排序n操作步骤：操作步骤：Step1:顺序表中前顺序表中前j-1个记录有序，将第个记录有序，将第j个记录插入。个记录插入。令令low=1；high=j-1；r0=rj；Step2:若若lowhigh，得到插入位置，转，得到插入位置，转Step5;Step3:若若lowhigh，则取有序子表的中点，则取有序子表的中点m=(low+high)/2；Step4:若若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。23表插入排序表插入排序举例说明举例说明Play24表插入排序表插入排序算法分析：算法分析：时间复杂度：时间复杂度：设有序表长度为设有序表长度为i，则需要比较至，则需要比较至多多i+1次，修改指针两次。因此，总比较次数与次，修改指针两次。因此，总比较次数与直接插入排序相同，修改指针总次数为直接插入排序相同，修改指针总次数为2n次。所次。所以，时间复杂度仍为以，时间复杂度仍为O(n2)。空间复杂度：空间复杂度：表插入排序的空间复杂度为表插入排序的空间复杂度为O(1)。稳定性：稳定性：表插入排序是一种表插入排序是一种稳定稳定的排序方法。的排序方法。25希尔排序希尔排序算法思想算法思想先将整个待排记录分割成若干个子先将整个待排记录分割成若干个子序列，在子序列中分别进行直接插序列，在子序列中分别进行直接插入排序，待整个序列基本有序的时入排序，待整个序列基本有序的时候，再对全体序列进行一次直接插候，再对全体序列进行一次直接插入排序。入排序。26希尔排序希尔排序操作步骤：操作步骤：Step1:选择一个步长序列选择一个步长序列t1，t2，tk，其中，其中 titj，tk=1；Step2:按步长序列个数按步长序列个数k，对序列进行，对序列进行k趟排序；趟排序；Step3:每趟排序，根据对应的步长每趟排序，根据对应的步长ti，将待排序列分割，将待排序列分割 成若干长度为成若干长度为m的子序列，分别对各子表进行直的子序列，分别对各子表进行直 接插入排序。仅步长因子为接插入排序。仅步长因子为1时，整个序列作为时，整个序列作为 一个表来处理，表长度即为整个序列的长度。一个表来处理，表长度即为整个序列的长度。27希尔排序希尔排序举例说明：举例说明：Play28希尔排序希尔排序算法分析：算法分析：时间复杂度：时间复杂度：由于希尔排序是依赖于增量的选由于希尔排序是依赖于增量的选取，它的时间复杂度是在取，它的时间复杂度是在O(nlog2n)O(n2)之间。之间。空间复杂度：空间复杂度：在希尔排序的过程中只需要一个在希尔排序的过程中只需要一个辅助空间用于暂存当前待插入的记录，因此，辅助空间用于暂存当前待插入的记录，因此，希尔排序的空间复杂度为希尔排序的空间复杂度为O(1)。稳定性：稳定性：希尔排序方法是一种希尔排序方法是一种不稳定不稳定的排序方的排序方法。法。299.3 9.3 交换排序交换排序冒泡排序冒泡排序1快速排序快速排序230冒泡排序冒泡排序假设在排序过程中，记录序列假设在排序过程中，记录序列R1.n的状态为：的状态为：第第 i 趟冒泡排序趟冒泡排序无序序列无序序列R1.n-i+1有序序列有序序列 Rn-i+2.nn-i+1无序序列无序序列R1.n-i有序序列有序序列 Rn-i+1.n比较相邻记录，将关比较相邻记录，将关键字最大的记录键字最大的记录交换交换到到 n-i+1 的位置上的位置上31冒泡排序冒泡排序算法思想算法思想对对n个记录的表，第一趟冒泡得到一个记录的表，第一趟冒泡得到一个关键码最大的记录个关键码最大的记录rn，第二趟冒，第二趟冒泡对泡对n-1个记录的表，再得到一个关个记录的表，再得到一个关键码最大的记录键码最大的记录rn-1，如此重复，如此重复，直到直到n个记录按关键码有序的表。个记录按关键码有序的表。32冒泡排序冒泡排序一趟冒泡方法：一趟冒泡方法：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;33冒泡排序冒泡排序操作步骤：操作步骤：Step1:从从n记录的表尾开始，记录的表尾开始，j=n；Step2:若若jri+1.key时，时，将将ri与与ri+1交换交换;Step7:i=i+1；调整对下两个记录进行两两比较，调整对下两个记录进行两两比较，转转Step4;35冒泡排序冒泡排序语言描述语言描述:templatevoid BubbleSort(SqList&L)for(int i=1;iL.length;i+)/用用i控制比较趟数共控制比较趟数共n-1趟趟 type t;/辅助变量，作交换用辅助变量，作交换用for(int j=1;jL.keyj+1)t=L.keyj;L.keyj=L.keyj+1;L.keyj+1=t;/交换交换L.keyj和和L.keyj+1的值的值 36冒泡排序冒泡排序算法分析：算法分析：空间复杂度：空间复杂度：冒泡排序的空间复杂度为冒泡排序的空间复杂度为O(1)。时间复杂度：时间复杂度：总共要进行总共要进行n-1趟冒泡，对趟冒泡，对j个记录个记录的表进行一趟冒泡需要的表进行一趟冒泡需要j-1次关键码比较。次关键码比较。冒泡冒泡排序的时间复杂度为排序的时间复杂度为O(n2)。稳定性：稳定性：冒泡排序是一种冒泡排序是一种稳定稳定的排序方法。的排序方法。37快速排序快速排序算法思想：算法思想：找一个记录，以它的关键字作为找一个记录，以它的关键字作为“枢轴枢轴”，凡其，凡其关键字关键字小于枢轴小于枢轴的记录均移动至该的记录均移动至该记录之前记录之前，反，反之，凡关键字之，凡关键字大于枢轴大于枢轴的记录均移动至该的记录均移动至该记录之记录之后后。致使一趟排序之后，记录的无序序列。致使一趟排序之后，记录的无序序列Rs.t将分割成两部分：将分割成两部分：Rs.i-1和和Ri+1.t，且，且 Rj.key Ri.key Rj.key (sji-1)枢轴枢轴 (i+1jt)。38快速排序快速排序示例示例stlowhigh设设 Rs=52 为枢轴为枢轴high23low80high14low52R052lowhighhighhighlow39快速排序快速排序操作步骤：操作步骤：Step1:如果待排子序列中元素的个数大于如果待排子序列中元素的个数大于1，则，则以以L.rlow作为枢轴作为枢轴，进行一次划分；否则排序，进行一次划分；否则排序结束。结束。Step2:对枢轴对枢轴左左半子序列重复半子序列重复Step1;Step3:对枢轴对枢轴右右半子序列重复半子序列重复Step1;40快速排序快速排序算法分析：算法分析：空间复杂度：空间复杂度：快速排序是递归的，递归调用层快速排序是递归的，递归调用层次数与其二叉树的深度一致。因而，存储开销次数与其二叉树的深度一致。因而，存储开销在理想情况下为在理想情况下为O(log2n)；在最坏情况下，为；在最坏情况下，为O(n)。时间复杂度：时间复杂度：最好情况下为最好情况下为O(nlog2n)，最坏，最坏情况，快速排序蜕化为冒泡排序。情况，快速排序蜕化为冒泡排序。稳定性：稳定性：快速排序是一个快速排序是一个不稳定不稳定的排序方法。的排序方法。419.4 9.4 选择排序选择排序简单选择排序简单选择排序1树形选择排序树形选择排序2堆排序堆排序342简单选择排序简单选择排序假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列 Ri.n 第第 i 趟趟简单选择排序简单选择排序从中选出关键字最小的记录有序序列R1.i无序序列 Ri+1.n43简单选择排序简单选择排序算法思想算法思想:第一趟第一趟，从，从n个记录中找出关键码最小的记录个记录中找出关键码最小的记录与第一个记录交换；与第一个记录交换；第二趟第二趟，从第二个记录开，从第二个记录开始的始的n-1个记录中再选出关键码最小的记录与个记录中再选出关键码最小的记录与第二个记录交换；如此，第二个记录交换；如此，第第i趟趟，则从第，则从第i个记个记录开始的录开始的n-i+1个记录中选出关键码最小的记录个记录中选出关键码最小的记录与第与第i个记录交换，直到整个序列按关键码有序。个记录交换，直到整个序列按关键码有序。44简单选择排序简单选择排序操作步骤：操作步骤：Step1:从从L.keyi 从从L.keylength记录中记录中选择选择一个关键字值一个关键字值最小最小的记录，将其下标保存至的记录，将其下标保存至min中；中；Step2:若若L.keyiL.keymin;则交换这两个记则交换这两个记录录;否则转否则转Step3;Step3:i=i+1,若若iL.length，则转，则转Step1;否则排否则排序结束。序结束。45简单选择排序简单选择排序算法分析：算法分析：时间复杂度：时间复杂度：从算法中可看出，简单选择排序从算法中可看出，简单选择排序移动记录的次数较少，但关键码的比较次数依移动记录的次数较少，但关键码的比较次数依然是，算法的时间复杂度仍是然是，算法的时间复杂度仍是O(n2)。空间复杂度：空间复杂度：简单选择排序算法只需要一个辅简单选择排序算法只需要一个辅助空间来作为交换记录用的暂存单元。因此，助空间来作为交换记录用的暂存单元。因此，它的空间复杂度它的空间复杂度O(1)。稳定性：稳定性：简单选择排序是一种简单选择排序是一种稳定稳定的排序方法。的排序方法。46树形选择排序树形选择排序操作步骤操作步骤:Step1:从最底层叶子结点开始，按层一一进行从最底层叶子结点开始，按层一一进行兄弟间的比赛，关键字值较大者上升为子树兄弟间的比赛，关键字值较大者上升为子树根结点，直到树的顶层为止；根结点，直到树的顶层为止；Step2:将树的根结点输出，把底层叶子中值相将树的根结点输出，把底层叶子中值相同的结点值改为同的结点值改为0；如果输出的结点总数小于；如果输出的结点总数小于初始时树的叶子结点总数，则重复初始时树的叶子结点总数，则重复Step1;否否则结束排序。则结束排序。47树形选择排序树形选择排序算法分析：算法分析：时间复杂度：时间复杂度：除了最大关键字之外，每选择一除了最大关键字之外，每选择一个次大的关键字只需要进行个次大的关键字只需要进行log2n次比较，因此，次比较，因此，它的时间复杂度为它的时间复杂度为O(nlogn)。空间复杂度：空间复杂度：需要附加需要附加n个辅助空间用来保存排个辅助空间用来保存排序的结果，还要序的结果，还要n-1个辅助空间作为排序过程中个辅助空间作为排序过程中使用。因此，它的空间复杂度使用。因此，它的空间复杂度O(n)。稳定性：稳定性：树形选择排序是一种树形选择排序是一种不稳定不稳定的排序方的排序方法。这是因为在比较的过程中是跳跃式进行的。法。这是因为在比较的过程中是跳跃式进行的。48堆排序堆排序堆的定义：堆的定义：n第一种定义方式：第一种定义方式：设有设有n个元素的序列个元素的序列 k1，k2，kn，当且仅，当且仅当满足下述关系之一时，称之为堆。当满足下述关系之一时，称之为堆。n第二种定义方式：第二种定义方式：堆是具有下列性质的完全二叉树：每个结点的值堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆或都小于或等于其左右孩子结点的值（称为小根堆或小顶堆）；或者每个结点的值都大于或等于其左右小顶堆）；或者每个结点的值都大于或等于其左右孩子结点的值（称为大根堆或大顶堆）。孩子结点的值（称为大根堆或大顶堆）。iiiikkkk212+或 iiiikkkk212+（i=1,2,，n/2）49堆排序堆排序算法思想：算法思想：设有设有n个元素，将其按关键码排序。首先将这个元素，将其按关键码排序。首先将这n个元素按关键码个元素按关键码建成堆建成堆，将堆顶元素输出，得，将堆顶元素输出，得到到n个元素中个元素中关键码最小关键码最小(或最大或最大)的元素。然后，的元素。然后，再对剩下的再对剩下的n-1个元素建成堆，输出堆顶元素，个元素建成堆，输出堆顶元素，得到得到n个元素中关键码次小个元素中关键码次小(或次大或次大)的元素。如的元素。如此反复，便得到一个按关键码有序的序列。称此反复，便得到一个按关键码有序的序列。称这个过程为堆排序。这个过程为堆排序。50堆排序堆排序堆排序需解决的两个问题：堆排序需解决的两个问题：1.怎样建堆：怎样建堆：如何将如何将n个元素的序列按关键码个元素的序列按关键码建成堆；建成堆；2.怎样调整：怎样调整：输出堆顶元素后，怎样调整剩余输出堆顶元素后，怎样调整剩余n-1个元素，使其按关键码成为一个新堆。个元素，使其按关键码成为一个新堆。51堆排序堆排序建堆方法：建堆方法：先把待排序序列构造成一棵先把待排序序列构造成一棵完全二叉树完全二叉树;然后从下往上然后从下往上,自右而左进行筛选自右而左进行筛选,最终得到堆最终得到堆.36 30 91 47 24 12 5385 a.8a.8个结点的初始状态个结点的初始状态 例：例：52堆排序堆排序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个结点为根的子树已是堆个结点为根的子树已是堆53堆排序堆排序36 12 8585 4747 24 30 53 91 36 53 8585 4747 24 30 12 91 e.e.对整棵树进行筛选对整棵树进行筛选54堆排序堆排序操作步骤：操作步骤：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:合并结束。合并结束。58二路归并排序二路归并排序递归算法操作步骤：递归算法操作步骤：Step1:将待排序的记录序列分为将待排序的记录序列分为两个相等两个相等的子序列，分别将这两个子序列进行排的子序列，分别将这两个子序列进行排序；序；Step2:调用一次归并算法调用一次归并算法Merge，将这两，将这两个有序子序列合并成一个含有全部记录个有序子序列合并成一个含有全部记录的有序序列。的有序序列。59二路归并排序二路归并排序算法分析算法分析:时间复杂度：时间复杂度：归并过程对应由叶向根生成一棵二归并过程对应由叶向根生成一棵二叉树的过程，所以归并趟数约等于二叉树的高度叉树的过程，所以归并趟数约等于二叉树的高度-1，即，即log2n，每趟归并需移动记录，每趟归并需移动记录n次，故时间次，故时间复杂度为复杂度为O(nlog2n)。空间复杂度：空间复杂度：需要一个与表等长的辅助元素数组需要一个与表等长的辅助元素数组空间，所以空间复杂度为空间，所以空间复杂度为O(n)。稳定性：稳定性：由一次归并算法中的由一次归并算法中的if语句可知，二路语句可知，二路归并算法是一种归并算法是一种稳定稳定的算法。的算法。609.6 9.6 基数排序基数排序基数排序是一种借助基数排序是一种借助“多关键字排序多关键字排序”的思想来实现的思想来实现“单关键字排序单关键字排序”的的内部排序算法内部排序算法。多关键码排序多关键码排序1链式基数排序链式基数排序261多关键码排序多关键码排序定义：定义：n个记录的序列个记录的序列R1,R2,，Rn对关键字对关键字(Ki1,Ki2,Kid)有序是指：对于序列中任意两个有序是指：对于序列中任意两个记录记录Ri和和Rj(1ijn)都满足下列都满足下列(词典词典)有序关有序关系：系：(Ki1,Ki2,Kid)(Kj1,Kj2,Kjd)，其，其中中:K1被称为被称为“最主最主”位关键字，位关键字，Kd被称为被称为“最次最次”位关键字。位关键字。62多关键码排序多关键码排序两种方法两种方法最高位优先最高位优先MSD法法先对先对K1进行排序，并按进行排序，并按K1的不同值将记录的不同值将记录序列分成若干子序列之后，分别对序列分成若干子序列之后，分别对K2进行进行排序，排序，.，依次类推，直至最后对最次位依次类推，直至最后对最次位关键字排序完成为止。关键字排序完成为止。最低位优先最低位优先LSD法法先对先对Kd进行排序，然后对进行排序，然后对Kd-1进行排序，进行排序，依次类推，直至对最主位关键字依次类推，直至对最主位关键字K1排序完排序完成为止。成为止。63多关键码排序多关键码排序例如例如:学生记录含三个关键字学生记录含三个关键字:系别、班号和系别、班号和班内的序列号，其中以系别为最主位关键字。班内的序列号，其中以系别为最主位关键字。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,3064链式基数排序链式基数排序算法思想：算法思想：从最低位关键码起，按关键码的不同值将序列从最低位关键码起，按关键码的不同值将序列中的记录中的记录“分配分配”到到RADIX个队列中，然后再个队列中，然后再“收集收集”之。如此重复之。如此重复d次即可。链式基数排序次即可。链式基数排序是用是用RADIX个链队列作为分配队列，关键码相个链队列作为分配队列，关键码相同的记录存入同一个链队列中，收集则是将各同的记录存入同一个链队列中，收集则是将各链队列按关键码大小顺序链接起来。链队列按关键码大小顺序链接起来。65链式基数排序链式基数排序操作步骤：操作步骤：Step1:初始化，建立待排序列的静态链表初始化，建立待排序列的静态链表SL；Step2:从最低位关键码开始，按关键码值将从最低位关键码开始，按关键码值将SL中中记录分配到各个单链表中；记录分配到各个单链表中；Step3:按照关键码的值，从小到大将各个单链表按照关键码的值，从小到大将各个单链表进行收集，重复进行收集，重复Step2，直到排序完成。，直到排序完成。66链式基数排序链式基数排序例：例：初始状态：初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配930063083184505278008109589269一趟收集：一趟收集：67链式基数排序链式基数排序505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集：一趟收集：68链式基数排序链式基数排序008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集：二趟收集：69链式基数排序链式基数排序算法分析：算法分析：时间效率：时间效率：设待排序列为设待排序列为n个记录，个记录，d个关键码，个关键码，关键码的取值范围为关键码的取值范围为radix，则进行链式基数排，则进行链式基数排序的时间复杂度为序的时间复杂度为O(d(n+radix)。空间效率：空间效率：需要需要2*radix个指向队列的辅助空间，个指向队列的辅助空间，以及用于静态链表的以及用于静态链表的n个指针。个指针。稳定性：稳定性：在基数排序的过程中，并没有交换记在基数排序的过程中，并没有交换记录的前后位置，因此该排序方法是一种录的前后位置，因此该排序方法是一种稳定稳定的的排序方法。排序方法。709.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)71小小 结结排序技术排序技术插入排序插入排序交换排序交换排序选择排序选择排序归并排序归并排序直直接接插插入入排排序序希希尔尔排排序序改进改进冒冒泡泡排排序序快快速速排排序序改进改进其它排序其它排序简简单单选选择择排排序序堆堆排排序序改进改进二二路路归归并并排排序序基基排排序序721 1、名词解释：、名词解释：排序，内部排序，外部排序，堆排序，内部排序，外部排序，堆 2 2、对于给定的一组键值：、对于给定的一组键值：8383，4040，6363，1313，8484，3535，9696，5757，3939，7979，6161，1515，分别画出应用直接，分别画出应用直接插入排序、直接选择排序、快速排序、归并排序插入排序、直接选择排序、快速排序、归并排序对上述序列进行排序中各趟的结果。对上述序列进行排序中各趟的结果。3 3、举例说明本章介绍的各排序方法中哪些是不稳定、举例说明本章介绍的各排序方法中哪些是不稳定的？的？4 4、编写一个双向气泡排序的算法，即相邻两遍向相、编写一个双向气泡排序的算法，即相邻两遍向相反方向起泡。反方向起泡。习习 题题735 5、设计一个用链表表示的直接选择排序算法。、设计一个用链表表示的直接选择排序算法。6 6、插入排序中找插入位置的操作可以通过二分法查、插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的插入排找的方法来实现。试据此写一个改进后的插入排序方法。序方法。7 7、一个线性表中的元素为正整数或负整数。设计一、一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表前一个算法，将正整数和负整数分开，使线性表前一半为负整数，后一半为正整数。不要求对这些元半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换次数。素排序，但要求尽量减少交换次数。8 8、试比较直接插入排序、直接选择排序、快速排序、试比较直接插入排序、直接选择排序、快速排序、堆排序、归并排序的时、空性能。堆排序、归并排序的时、空性能。习习 题题749 9、全国有、全国有1000010000人参加物理竞赛，只录取成绩优异人参加物理竞赛，只录取成绩优异的前的前1010名，并将他们从高分到低分输出。而对落名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？用何种排序方法速度最快？为什么？1010、已知待排序的序列为（、已知待排序的序列为（503503，8787，512512，6161，908908，170170，897897，275275，653653，462462），试完成下列各题。），试完成下列各题。(1)(1)根据以上序列建立一个堆（画出第一步和最根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。后堆的结果图），希望先输出最小值。(2)(2)输出最小值后，如何得到次小值。（并画出输出最小值后，如何得到次小值。（并画出相应结果图）相应结果图）习习 题题75The End76此此课课件下件下载载可自行可自行编辑编辑修改，修改，仅仅供参考！供参考！感感谢谢您的支持，我您的支持，我们们努力做得更好！努力做得更好！谢谢谢谢