数据结构 第八章 排序.ppt

第八章 排序1本章要点本章要点n排序的基本概念、排序方法分类、稳定性及效率排序的基本概念、排序方法分类、稳定性及效率评价；评价；n插入排序插入排序-直接插入、折半插入、希尔排序；直接插入、折半插入、希尔排序；n交换排序交换排序-冒泡排序、快速排序的；冒泡排序、快速排序的；n 选择排序选择排序-简单选择、树形选择、堆排序；简单选择、树形选择、堆排序；n归并排序；归并排序；n基数排序；基数排序；n外部排序。外部排序。2排序是计算机程序设计中的一种重要操作排序是计算机程序设计中的一种重要操作。在数在数值计算或数据处理过程中，都会直接或间接用到数据值计算或数据处理过程中，都会直接或间接用到数据的排序问题。的排序问题。排序的功能：是将一个数据元素排序的功能：是将一个数据元素(或称为记录或称为记录)的无的无序序列，按数据元素的某个数据项值的大小，排列成序序列，按数据元素的某个数据项值的大小，排列成一个递增或递减的有序的记录序列。一个递增或递减的有序的记录序列。作为排序依据的数据项为关键字，关键字分主关作为排序依据的数据项为关键字，关键字分主关键字和次关键字两种。键字和次关键字两种。3n排序(Sorting)(Sorting)：假设含假设含n n 个记录的序列为个记录的序列为:R Rl l,R,R2 2,R,Rn n 其相应的关键字序列为其相应的关键字序列为:K:Kl l,K,K2 2,K,Kn n 需需确确定定1,2,1,2,n,n的的一一种种排排列列p pl l,p,p2 2,p,pn n,使使其其相相应应的的关关键字满足如下的非递减键字满足如下的非递减(或非递增关系或非递增关系)：K Kp1 p1 K Kp2 p2 K Kpnpn 使记录序列成按关键字有序的序列：使记录序列成按关键字有序的序列：R Rp1p1,R,Rp2p2,R,Rpnpn 这样一种操作称为这样一种操作称为排序排序。n排序结果：排序结果：当当K Ki i是主关键字：是主关键字：唯一唯一当当K Ki i是次关键字：是次关键字：不唯一不唯一8.1 8.1 概概 述述4n若若K Ki i=K=Kj j，(1(1 i i j j n),n),且且排排序序前前,R,Ri i在在R Rj j前前面面，若若排排序序后后，R Ri i仍仍在在R Rj j前前面面，则则称称该该排排序序算算法法是是稳定的，否否则则是是不稳定的。n所所谓谓内部排序，是是指指待待排排序序列列完完全全存存放放在在内内存存中中，排序过程中也不需要访问外存储器。排序过程中也不需要访问外存储器。所所谓谓外部排序，是是指指排排序序过过程程中中还还需需访访问问外外存存储储器器的的排序过程。排序过程。n内内部部排排序序的的过过程程是是一一个个逐逐步步扩扩大大记记录录的的有有序序序序列列长长度度的的过过程程。将将一一个个或或多多个个记记录录置置于于合合适适的的位位置置上上的的一一个个完完整过程称为整过程称为一趟。基基于于不不同同的的“扩扩大大”有有序序序序列列长长度度的的方方法法，内内部部排排序序方方法法大大致致可可分分下下列列几几种种类类型型：插插入入排排序序、交交换换排排序序、选选择择排排序序、归并排序、基数排序等。归并排序、基数排序等。5n在排序的过程中需进行的两种基本操作：在排序的过程中需进行的两种基本操作：1)比较两个关键字的大小；比较两个关键字的大小；2)将记录从一个位置移动至另一个位置。将记录从一个位置移动至另一个位置。n待排序数据元素的存储方式：待排序数据元素的存储方式：顺顺序序存存储储方方式式，即即将将一一组组待待排排序序数数据据元元素素存存放放在在一一组组地地址址连续的存储单元中，排序过程中需要元素的比较和移动；连续的存储单元中，排序过程中需要元素的比较和移动；链链式式存存储储方方式式，即即将将一一组组待待排排序序数数据据元元素素存存放放在在动动态态链链表表或或静静态态链链表表中中，排排序序过过程程无无须须移移动动元元素素的的位位置置，只只需需修修改改指针即可；指针即可；数数据据元元素素本本身身按按顺顺序序方方式式存存储储，但但又又不不宜宜移移动动元元素素位位置置的的，则则可可通通过过建建立立一一个个指指示示各各个个数数据据元元素素存存储储位位置置的的辅辅助助表表来来实现实现n按内部排序过程中所需的工作量来区分按内部排序过程中所需的工作量来区分:简单的排序方法，其时间复杂度为简单的排序方法，其时间复杂度为O(n2)先进的排序方法，其时间复杂度为先进的排序方法，其时间复杂度为O(nlogn)基数排序，其时间复杂度为基数排序，其时间复杂度为O(dn)6待排序的数据元素的类型定义如下：待排序的数据元素的类型定义如下：#define MAXSIZE 20#define MAXSIZE 20 /顺序表的最大长度顺序表的最大长度typedef int KeyType;/typedef int KeyType;/定义关键字类型为整数类型定义关键字类型为整数类型typedef struct typedef struct KeyType key;KeyType key;/关键字关键字 char *otherinfo;char *otherinfo;/其它数据项其它数据项ElemType;ElemType;/数据元素类型数据元素类型typedef struct typedef struct ElemType*elem;ElemType*elem;/数据元素基地址数据元素基地址 int length;int length;/数据元素个数数据元素个数 int listsize;/int listsize;/存储空间大小存储空间大小SqList;SqList;/顺序表类型顺序表类型本章约定：7对于对于链式基数排序，我们假定记录序列是基于链表存储的链式基数排序，我们假定记录序列是基于链表存储的。待排序的数据元素的类型定义为：待排序的数据元素的类型定义为：typedef structtypedef struct KeyType keysMAX_KEY_NUMKeyType keysMAX_KEY_NUM；/关键字字段关键字字段 char info40;char info40;/记录的其他信息记录的其他信息 int nextint next；/指针字段指针字段NodeTypeNodeType；/表结点类型表结点类型typedef structtypedef struct NodeTypeNodeTyperMAX_SPACErMAX_SPACE；/静态链表，静态链表，r0r0为头结点为头结点 int int keynumkeynum；/关键字个数关键字个数 int int lengthlength；/当前表中记录数当前表中记录数L_TBLL_TBL；/链表类型链表类型8n插入排序（Insertion SortInsertion Sort）：假定记录序列中前面：假定记录序列中前面的一部分记录已经有序，把后面的一个记录插入已排序的一部分记录已经有序，把后面的一个记录插入已排序的有序子序列中去的有序子序列中去,使得插入这个记录之后使得插入这个记录之后,得到的仍然得到的仍然是有序序列是有序序列,从而逐步的扩大有序子序列的长度从而逐步的扩大有序子序列的长度,直到所直到所有记录都有序为止。有记录都有序为止。n假定记录序列的前面假定记录序列的前面i-1i-1个记录已经有序个记录已经有序,从无序序列从无序序列中取第中取第i i个记录个记录,将它插入到前面将它插入到前面i-1i-1个有序子序列中并个有序子序列中并且保持有序状态。且保持有序状态。如图如图所示。所示。8.8.2 2 插入排序插入排序n按照不同的查找插入位置和按照不同的查找插入位置和记录移动方法，插入排序可以记录移动方法，插入排序可以分为以下几类：直接插入排序、分为以下几类：直接插入排序、折半插入排序、希尔排序、折半插入排序、希尔排序、2-2-路插入排序、表插入等路插入排序、表插入等.9n直接插入排序思路：直接插入排序思路：第第1 1趟将初始序列中的记录趟将初始序列中的记录R R1 1看做有序子序列，若看做有序子序列，若R R2 2的关键字的关键字小于小于R R1 1的关键字，则的关键字，则R R2 2插在插在R R1 1的前面，否则的前面，否则R R2 2插在插在R R1 1的后面。的后面。第第2 2趟将趟将R R3 3插入前面的两个记录的有序子序列中，得到插入前面的两个记录的有序子序列中，得到3 3个记个记录的有序子文件。录的有序子文件。以此类推，继续进行下去，直到将以此类推，继续进行下去，直到将R Rn n插入前面的插入前面的n n1 1个记录个记录的有序子序列中，最后得到的有序子序列中，最后得到n n个记录的有序文件。个记录的有序文件。n具体实现时，在记录具体实现时，在记录R R1 1的前面增设记录的前面增设记录R R0 0，它既是中间变量，又，它既是中间变量，又是监视哨是监视哨:设设(R(R1 1，R R2 2，R Ri i1 1)是已排序的有序子序列，则插入是已排序的有序子序列，则插入R Ri i的的步骤是：首先将步骤是：首先将R Ri i存放到存放到R R0 0中，然后将中，然后将K K0 0(即原即原R Ri i的关键字的关键字K Ki i)依次与依次与K Ki i1 1，K Ki i2 2，比较，若比较，若K K0 0KKj j(j=i(j=i1 1，i i2 2，1)1)，则，则R Rj j后移一个位置，否则停止比较和移动，最后，将后移一个位置，否则停止比较和移动，最后，将R R0 0(即即原来待插入的记录原来待插入的记录R Ri i)移到移到j+1j+1的位置上。由于的位置上。由于R Ri i的前面有监视的前面有监视哨哨R R0 0，因此，因此不必每次判断下标不必每次判断下标j j是否出界是否出界 一、直接插入排序(Straight Insertion Sort)10n例：例：4242，2121，8989，1515，4343，28 28 排序过程为：排序过程为：k0 k1 k2 k3 k4 k5 k6k0 k1 k2 k3 k4 k5 k6初始关键字初始关键字:42 21 89 15 43 28 42 21 89 15 43 28 第一趟开始前第一趟开始前:(42)(42)21 89 15 43 2821 89 15 43 28第一趟排序后第一趟排序后:21:21 (2121 42)89 15 43 28 42)89 15 43 28 第二趟排序后第二趟排序后:89 (21 42:89 (21 42 8989)15 43 28)15 43 28 第三趟排序后第三趟排序后:15 (:15 (1515 21 42 89)43 28 21 42 89)43 28 第四趟排序后第四趟排序后:43:43 (15 21 42 (15 21 42 4343 89)89)28 28 第五趟排序后第五趟排序后:28 (15 21 :28 (15 21 2828 42 43 89)42 43 89)11void InsertionSort(SqList&L)void InsertionSort(SqList&L)for(i=2;i=L.length;i+)for(i=2;i=L.length;i+)if(L.elemi.keyL.elemi-1.key)if(L.elemi.keyL.elemi-1.key)L.elem0=L.elemi;/L.elem0=L.elemi;/复制为监视哨复制为监视哨 for(j=i-1;L.elem0.keyL.elemj.key;j-)for(j=i-1;L.elem0.keyL.elemj.key;j-)L.elemj+1=L.elemj;/L.elemj+1=L.elemj;/记录后移记录后移 L.elemj+1=L.elem0;/L.elemj+1=L.elem0;/插入到正确位置插入到正确位置 效率分析：效率分析：1)1)空间空间:仅用了一个辅助单元。空间复杂度为仅用了一个辅助单元。空间复杂度为O(1)O(1)2)2)时时间间：n-1n-1趟趟.比比较较的的次次数数和和移移动动记记录录的的次次数数取取决决于于待待排排序序列列按按关键字的初始排列。关键字的初始排列。(最好、最坏、平均最好、最坏、平均)若待排序记录是随机的若待排序记录是随机的,则可取上述最小值和最大值的平均值则可取上述最小值和最大值的平均值,作为直接作为直接插入排序时所需进行关键字间的比较次数和移动记录的次数插入排序时所需进行关键字间的比较次数和移动记录的次数,约为约为n n2 2/4/4。由此由此,直接插入排序的时间复杂度为直接插入排序的时间复杂度为O(nO(n2 2)。3)3)稳定性：稳定稳定性：稳定直接插入排序算法实现如下：12用折半查找的方法找到插入位置用折半查找的方法找到插入位置例：在序列例：在序列13,27,35,48,65,7213,27,35,48,65,72中插入中插入2020或或6060void BInsertSort(SqList&L)void BInsertSort(SqList&L)/对顺序表对顺序表L L做折半插入排序做折半插入排序 for(i=2;i=L.length;+i)for(i=2;i=L.length;+i)L.r0=L.ri;L.r0=L.ri;/将将L.riL.ri暂存到暂存到L.r0L.r0 low=1;hight=i-1;low=1;hight=i-1;while(lowhight)/while(low=hight+1;-j)for(j=i-1;j=hight+1;-j)L.rj+1=L.rj;/L.rj+1=L.rj;/记录后移记录后移 L.rhight+1=L.r0;L.rhight+1=L.r0;/插入到正确位置插入到正确位置 /for/for/BInsertSort/BInsertSort二、折半插入排序 13折半插入排序效率分析：折半插入排序效率分析：1)1)空间效率：仅用了一个辅助单元。空间复杂度为空间效率：仅用了一个辅助单元。空间复杂度为O(1)O(1)。2)2)时间效率：确定插入位置所进行的折半查找，关键时间效率：确定插入位置所进行的折半查找，关键字的比较次数至多为字的比较次数至多为loglog2 2n+1n+1次，移动记录的次数和次，移动记录的次数和直接插入排序相同，故时间复杂度仍为直接插入排序相同，故时间复杂度仍为O(nO(n2 2)。3)3)稳定性：折半插入排序是一个稳定的排序方法。稳定性：折半插入排序是一个稳定的排序方法。14n希希尔尔排排序序又又称称为为缩缩小小增增量量排排序序。是是对对直直接接插插入入排排序序的的一种改进一种改进，其方法：其方法：按按增增量量序序列列将将整整个个待待排排记记录录分分割割成成若若干干个个序序列列,分分别别进进行行直直接接插插入入排排序序,等等整整个个序序列列基基本本有有序序后后再再对对全全体体记记录录进进行行一一次次直接插入排序直接插入排序当原序列基本有序当原序列基本有序,即序列中满足以下特性的记录较少时即序列中满足以下特性的记录较少时 直接插入排序的效率可大大提高直接插入排序的效率可大大提高;同时当同时当n很小时效率也较高很小时效率也较高,希尔排序正是从这两点分析出发对直接排序进行的改进。希尔排序正是从这两点分析出发对直接排序进行的改进。n例：例：假设待排序列为假设待排序列为3939,8080,7676,4141,1313,2929,5050,7878,3030,1111,100100,7 7,4141,8686。分别取步长因子。分别取步长因子5 5、3 3、1 1，则排序过，则排序过程如下程如下:三、希尔排序15初始序列：初始序列：39 80 76 41 13 29 50 78 30 11 100 7 39 80 76 41 13 29 50 78 30 11 100 7 41 8641 86d=5d=5排序后：排序后：2 29 7 9 7 41 30 11 39 50 76 41 13 100 80 78 8641 30 11 39 50 76 41 13 100 80 78 86第一趟第一趟d=3d=3排序后：排序后：13 7 13 7 39 29 11 41 30 76 41 50 86 80 78 10039 29 11 41 30 76 41 50 86 80 78 100第二趟第二趟d=1d=1排序后：排序后：7 11 13 29 30 39 41 41 50 76 78 80 86 1007 11 13 29 30 39 41 41 50 76 78 80 86 100第三趟（即直接插入排序）第三趟（即直接插入排序）16希尔排序算法描述如下：1)1)选择一个步长序列选择一个步长序列t t1 1，t t2 2，t tk k，其中，其中t ti ittj j，t tk k=1=1；2)2)按步长序列个数按步长序列个数k k，对序列进行，对序列进行k k趟排序；趟排序；3)3)每趟排序，根据对应的步长每趟排序，根据对应的步长t ti i，将待排序列分割成，将待排序列分割成t ti i个长个长度为度为m m的子序列，分别对各子序列进行直接插入排序。例如，的子序列，分别对各子序列进行直接插入排序。例如，步长为步长为d d时，将时，将 n n 个记录分成个记录分成 d d 个子序列：个子序列：R R1 1，R R1+d1+d，R R1+2d1+2d，R R1+kd1+kd R R2 2，R R2+d2+d，R R2+2d2+2d，R R2+kd2+kd R Rd d，R R2d2d，R R3d3d，R Rkdkd，R R(k+1)d(k+1)d其中，其中，d d称为增量，它的值在排序过程中从大到小逐渐缩小，称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为直至最后一趟排序减为1 1。17void ShellInsert(SqList&L,int dk)void ShellInsert(SqList&L,int dk)/一趟增量为一趟增量为dkdk的插入排序，的插入排序，dkdk为步长因子为步长因子 for(i=dk+1for(i=dk+1；i=L.lengthi=L.length；i+)i+)if(L.elemi.key L.elemi-dk.key)if(L.elemi.key 0&L.elem0.key0&L.elem0.keyL.elemj.key;j=j-dk)j=j-dk)L.elemj+dk=L.elemjL.elemj+dk=L.elemj；/记录后移记录后移 L.elemj+dk=L.elem0L.elemj+dk=L.elem0；/插入到正确位置插入到正确位置 void ShellSort(SqList&Lvoid ShellSort(SqList&L,int dltaint dlta,int t)int t)/按增量序列按增量序列dlta0dlta0,1 1,t-1t-1对顺序表对顺序表L L作希尔排序作希尔排序 for(k=0for(k=0；ktk1)while(i1)lastExchangeIndex=1;lastExchangeIndex=1;for(j=1;ji;j+)for(j=1;ji;j+)if(L.elemj+1.key L.elemj.key)if(L.elemj+1.key L.elemj.key)Swap(L.elemj,L.elemj+1);Swap(L.elemj,L.elemj+1);lastExchangeIndex=j;/lastExchangeIndex=j;/记下进行交换的记录位置记下进行交换的记录位置 /if/if i=lastExchangeIndex;/i=lastExchangeIndex;/本趟进行过交换的记录位置本趟进行过交换的记录位置 /BubbleSort /BubbleSort 强调：强调：1)1)冒泡排序的结束条件为，冒泡排序的结束条件为，“最后一趟没有进行交换记录最后一趟没有进行交换记录”;2)2)一般情况下，每经过一趟一般情况下，每经过一趟“冒泡冒泡”，“i i减减1 1”，但并不是，但并不是每趟都如此。每趟都如此。22冒泡排序的效率分析：1)1)空间效率空间效率:仅用了一个辅助单元。空间复杂度为仅用了一个辅助单元。空间复杂度为O(1)O(1)。2)2)时间效率：冒泡排序总共要进行时间效率：冒泡排序总共要进行n-1n-1趟，对趟，对j j个记录进个记录进行一趟冒泡需要行一趟冒泡需要j-1j-1次关键字比较。次关键字比较。最好的情况：关键字在记录序列中顺序有序，只需进行一最好的情况：关键字在记录序列中顺序有序，只需进行一趟起泡。其中比较的次数为趟起泡。其中比较的次数为n-1n-1，移动的次数为，移动的次数为0 0。最坏的情况：关键字在记录序列中逆序有序，需进行最坏的情况：关键字在记录序列中逆序有序，需进行n-1n-1趟趟起泡。比较的次数为起泡。比较的次数为n*(n-1)/2n*(n-1)/2，移动的次数为，移动的次数为3n*(n-1)/23n*(n-1)/2 (3)(3)稳定性：稳定。稳定性：稳定。思考：思考：若初始序列为若初始序列为“正序正序”序列序列时，时空效率？时，时空效率？若初始序列为若初始序列为“逆序逆序”序列序列时，时空效率？时，时空效率？23n快速排序(Quick Quick SortSort)对对起起泡泡排排序序的的一一种种改改进进。其其基本思想基本思想是是：通通过过比比较较关关键键字字、交交换换记记录录，以以某某个个记记录录为为“枢枢轴轴”，将将待待排排序序列列分分成成两两部部分分。其其中中，一一部部分分所所有有记记录录的的关关键键字字大大于于等等于于“枢枢轴轴”记记录录的的关关键键字字，另另一一部部分分所所有有记记录录的的关关键键字字小小于于“枢轴枢轴”记录的关键字。记录的关键字。将将待待排排序序列列按按关关键键字字以以“枢枢轴轴”记记录录分分成成两两部部分分的的过过程程，称称为为一次划分。快快速速排排序序通通过过对对各各部部分分不不断断划划分分，直直到到整整个个序序列按关键字有序列按关键字有序。二、快速排序24n设序列设序列L.rs,L.rs+1,L.rs,L.rs+1,L.rt,L.rt，low=s;high=t;low=s;high=t;假定假定枢轴枢轴pivotkey=L.rlow.keypivotkey=L.rlow.key，排序过程如下：，排序过程如下：1)1)从从highhigh开开始始往往前前找找第第一一个个关关键键字字小小于于pivotkeypivotkey的的记记录录与与枢枢轴轴记记录交换；录交换；2)2)从从lowlow开开始始往往后后找找第第一一个个关关键键字字大大于于pivotkeypivotkey的的记记录录与与枢枢轴轴记记录交换；录交换；3)3)重复重复1)2)1)2)直到直到low=highlow=high为止为止此时枢轴记录所在的位置此时枢轴记录所在的位置i=low=high i=low=high n设设有有序序列列4242，2121，8989，1515，4343，2828，以以第第1 1条条记记录录为为枢枢轴轴，进进行一次划分。行一次划分。25n设有设有序列序列4242，2121，8989，1515，4343，2828，以第，以第1 1条记录为枢轴，条记录为枢轴，进行一次划分进行一次划分过程：过程：1 1)首先，以第首先，以第1 1条记录条记录4242为枢轴，将该记录保存在为枢轴，将该记录保存在R R0 0中，设置中，设置两个指针，两个指针，lowlow指向第指向第1 1条记录条记录R R1 1，highhigh指向最后指向最后1 1条记录条记录R R6 62)2)比较比较highhigh指向的记录的关键字指向的记录的关键字2828，发现枢轴记录比枢轴小，发现枢轴记录比枢轴小，这时，将该记录交换到这时，将该记录交换到lowlow指向的位置指向的位置R1R1。3)3)比较比较lowlow指向的记录的关键字指向的记录的关键字2828，发现比枢轴小，增大，发现比枢轴小，增大lowlow，直到，直到lowlow指向记录指向记录R R3 3，这时，这时R R3 3的关键字的关键字8989比枢轴大，将该记比枢轴大，将该记录交换到录交换到highhigh指向的位置指向的位置R R6 6。4)4)重复上述步骤重复上述步骤2)2)、3)3)。减小。减小highhigh到到R R4 4，它的关键字，它的关键字1515比枢比枢轴小，将该记录交换到轴小，将该记录交换到lowlow指向的位置指向的位置R R3 3。5)5)增大增大lowlow，直到，直到low=highlow=high，没有再发现比枢轴大的记录，这，没有再发现比枢轴大的记录，这时将保存的枢轴记录，交换到该位置时将保存的枢轴记录，交换到该位置R R4 4=R=R0 0n快速排序就是不断对大于快速排序就是不断对大于1 1个记录的序列进行划分个记录的序列进行划分!26n演示：设有序列演示：设有序列 4949,3838,6565,9797,7676,1313,2727,4949 各趟排序的结果各趟排序的结果如下如下：第一趟第一趟 27 38 13 49 76 97 65 27 38 13 49 76 97 65 4949 第二趟第二趟 13 27 38 49 76 97 65 13 27 38 49 76 97 65 4949 第三趟第三趟 13 27 38 49 13 27 38 49 4949,65 76 97,65 76 97 第四趟第四趟 13 27 38 49 13 27 38 49 4949 65 76 97 65 76 9749 49 38 65 97 76 13 27 38 65 97 76 13 27 4949i ij jpivotkey=49pivotkey=49初始状态初始状态27 38 65 97 76 13 27 38 65 97 76 13 4949 4949i ij j进行第一进行第一次交换后次交换后j ji i27 38 27 38 4949 97 76 13 65 97 76 13 65 4949i ij j进行第二进行第二次交换后次交换后j j进行第三进行第三次交换后次交换后27 27 38 13 97 76 38 13 97 76 4949 65 65 4949i ij ji i进行第四进行第四次交换后次交换后27 38 13 27 38 13 4949 76 97 65 76 97 65 4949i ij jj jj j27int partition(SqList&L,int low,int high)int partition(SqList&L,int low,int high)/将将L.L.elemelemlow.highlow.high的记录的记录按按枢轴枢轴划分为两个子表划分为两个子表 piovtpiovt.key=L.key=L.elemelemlow.key;/low.key;/第一个记录作枢轴记录第一个记录作枢轴记录 while(lowhigh)while(lowhigh)/从表的两端交替地向中间扫描从表的两端交替地向中间扫描 while(lowhigh&L.while(low=priotkey)high.key=priotkey)-high;-high;L.L.elemelemlowlowL.L.elemelemhigh;/high;/比枢轴小的记录交换到低端比枢轴小的记录交换到低端 while(lowhigh&L.while(lowhigh&L.elemelemlow.key=priotlow.key=priot.key)key)+low;+low;L.L.elemelemlowlowL.L.elemelemhigh;/high;/比枢轴大的记录交换到高端比枢轴大的记录交换到高端 return low;return low;/返回枢轴所在的位置返回枢轴所在的位置/Partition/Partition注注意意：每每交交换换一一对对记记录录需需进进行行三三次次记记录录移移动动(赋赋值值)的的操操作作，而而实实际际上上,在在排排序序过过程程中中对对枢枢轴轴记记录录的的赋赋值值是是多多余余的的,只只有有在在一一趟趟排排序序结结束时束时,即即1ow=high1ow=high的位置才是枢轴记录的最后位置。的位置才是枢轴记录的最后位置。28int Partition(SqList&L,int low,int high)int Partition(SqList&L,int low,int high)pivot.key=L.elemlow.key;pivot.key=L.elemlow.key;while(lowhigh)while(lowhigh)while(low=pivot.key)while(low=pivot.key)-high;-high;L.elemlow.key=L.elemhigh.key;L.elemlow.key=L.elemhigh.key;while(lowhigh&L.elemlow.key=pivot.key)while(lowhigh&L.elemlow.key=pivot.key)+low;+low;L.elemhigh.key=L.elemlow.key;L.elemhigh.key=L.elemlow.key;L.elemlow.key=pivot.key;L.elemlow.key=pivot.key;return low;return low;注：如果交换时有其他相关信息需要交换，应一起交换。注：如果交换时有其他相关信息需要交换，应一起交换。29void Qsort(SqList&L,int void Qsort(SqList&L,int s s,int,int t t)/对顺序表对顺序表L L中中区间区间子表子表L.rL.rs s.t t 作快速排序作快速排序 if(if(t-st-s=1=1)return;return;/长度长度小小于于1 1,直接返回直接返回 pivotlocpivotloc =Partition(L,Partition(L,s s,t t);/);/将将L.rL.rs s.t t 一分为二一分为二 Qsort(L,low,pivotloc-1);/Qsort(L,low,pivotloc-1);/对对前半区间前半区间递归排序递归排序 Qsort(L,pivotloc+1,high);/Qsort(L,pivotloc+1,high);/对对后半区间后半区间递归排序递归排序/Qsort/Qsortvoid QuickSort(SqList&L)void QuickSort(SqList&L)/对顺序表对顺序表L L作快速排序作快速排序 QSort(L,1,L.length);QSort(L,1,L.length);/QuickSort/QuickSort复杂度分析：复杂度分析：平均时间为平均时间为T Tavgavg(n)=(n)=knknlnlnn n,其中其中n n记录的个数记录的个数,k,k为某个常数。为某个常数。30快速排序的效率分析：1)1)空间效率：快速排序是递归的，递归调用层次数与上述二空间效率：快速排序是递归的，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为叉树的深度一致。因而，存储开销在理想情况下为O(logO(log2 2n)n)；在最坏情况下，为；在最坏情况下，为O(n)O(n)。2)2)时间效率：在时间效率：在n n个记录的待排序列中，一次划分需要约个记录的待排序列中，一次划分需要约n n次关次关键字比较，时效为键字比较，时效为O(n)O(n)。整个排序的时间效率与划分时子表。整个排序的时间效率与划分时子表的大小有关。的大小有关。如果每次划分均匀，则如果每次划分均匀，则快速排序所需时间复杂度为快速排序所需时间复杂度为O(nlogO(nlog2 2n)n)。在所有同数量级的排序方法中，从时间上看，。在所有同数量级的排序方法中，从时间上看，快速排序的平均性能最好。快速排序的平均性能最好。在最坏情况下：每次划分，只得到一个子序列，比如待在最坏情况下：每次划分，只得到一个子序列，比如待排记录的初始状态为按关键字有序时，快速排序将蜕化为起排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，时间效率为泡排序，时间效率为O(nO(n2 2)。3)3)稳定性：快速排序是不稳定的排序。稳定性：快速排序是不稳定的排序。31n选选择择排排序序(Selection(Selection Sort)Sort)。一一个个记记录录最最多多只只需需进进行行一一次交换就可以直接到达它的排序位置。次交换就可以直接到达它的排序位置。选选择择排排序序主主要要思思想想是是每每一一趟趟从从待待排排序序列列中中选选取取一一个个关关键键字字最最小小的记录，并置于适当的位置上。的记录，并置于适当的位置上。第一趟从第一趟从n n个记录中选取关键字最小的记录个记录中选取关键字最小的记录，置于合适位置；，置于合适位置；第第二二趟趟从从剩剩下下的的n-1n-1个个记记录录中中选选取取当当前前关关键键字字最最小小的的记记录录，置置于合适位置上；于合适位置上；以此类推，以此类推，直到整个序列的记录选完。直到整个序列的记录选完。n假假设设待待排排序序的的序序列列为为R R1 1，R R2 2，R Rn n，进进行行选选择择排排序序的的基本步骤如下：基本步骤如下：1)1)置置i i为为1 1；2)2)当当inin时时，重重复复下下列列步步骤骤：在在R R1 1，R Rn n中中选选出出一一个个关关键键字字最最小小的的记记录录R Rminmin，若若R Rminmin不不是是R Ri i，即即R RminminRRi i，则则交交换换R Ri i和和R Rminmin的的位置；否则，不进行交换。位置；否则，不进行交换。8.8.4 4 选择排序选择排序32 第第一一趟趟，将将选选出出的的记记录录置置于于第第1 1个个位位置置，第第二二趟趟将将选选出出的的记记录录置于第置于第2 2个位置上，个位置上，.共进行共进行n-1n-1趟排序趟排序,n(n-1)/2,n(n-1)/2次比较次比较。void SelectSort(SqList&L)void SelectSort(SqList&L)for(i=1for(i=1；iL.lengthiL.length；i+)i+)for(j=i+1for(j=i+1，t=it=i；j=L.lengthjL.elemj.key)if(L.elemt.keyL.elemj.key)t=jt=j；/if/if if(t!=i)if(t!=i)/交换交换 temp=L.elemt;temp=L.elemt;L.elemt=L.elemiL.elemt=L.elemi；L.elemi=temp;L.elemi=temp;/if/if /for/for/SelectSortSelectSort一、简单选择排序33简单选择排序的效率分析：简单选择排序的效率分析：1)1)空间效率：仅用了一个辅助单元。空间复杂度为空间效率：仅用了一个辅助单元。空间复杂度为O(1)O(1)。2)2)时间效率：对时间效率：对 n n 个记录进行简单选择排序，关键个记录进行简单选择排序，关键字间的比较次数总计为：字间的比较次数总计为：移动记录的次数：最小值为移动记录的次数：最小值为 0,0,最大值为最大值为3(n-1)3(n-1)，这是一种简单排序方法。这是一种简单排序方法。3)3)稳定性：稳定的排序方法。稳定性：稳定的排序方法。34n树选择排序(Tree(Tree Selection Selection Sort)Sort)思思想想：通通过过类类似似与与“淘淘汰汰赛赛”的的想想法法，让让序序列列中中的的关关