数据结构-程序员联合开发网.ppt
第三章第三章 内部排序算法内部排序算法F 3.1 3.1 3.1 3.1 直接插入排序直接插入排序直接插入排序直接插入排序 3.2 3.2 3.2 3.2 希尔排序希尔排序 3.3 3.3 3.3 3.3 冒泡排序冒泡排序F 3.4 3.4 3.4 3.4 快速排序快速排序F 3.5 3.5 3.5 3.5 简单选择排序简单选择排序F 3.6 3.6 3.6 3.6 归并排序归并排序归并排序归并排序第六章首页上页下页退出分类：分类：内部排序：全部记录都可以同时调入内存进内部排序：全部记录都可以同时调入内存进行的排序。行的排序。外部排序：文件中的记录太大，无法全部将外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。其同时调入内存进行的排序。第六章首页上页下页退出 内内 部部 排排 序序 插入排序插入排序插入排序插入排序 交换排序交换排序交换排序交换排序 选择排序选择排序选择排序选择排序 归并排序归并排序归并排序归并排序 基数排序基数排序基数排序基数排序有序表中插入元素，并保持其有序有序表中插入元素，并保持其有序将表中关键字比较，位置不对交换将表中关键字比较，位置不对交换先查找关键字，再交换。先查找关键字，再交换。将两个有序的关键字序列进行归并将两个有序的关键字序列进行归并不比较，按多关键字排序方法不比较，按多关键字排序方法直接直接折半折半2-路路表表希尔希尔冒泡冒泡快速快速简单简单树型树型堆堆第六章首页上页下页退出3.1 3.1 3.1 3.1 直接插入排序直接插入排序直接插入排序直接插入排序直接插入排序直接插入排序排序过程：整个排序过程为排序过程：整个排序过程为n-1n-1趟插入，即先将序趟插入，即先将序列中第列中第1 1个记录看成是一个有序子序列，然后从第个记录看成是一个有序子序列，然后从第2 2个记录开始，逐个进行插入，直至整个序列有序个记录开始，逐个进行插入，直至整个序列有序第六章首页上页下页退出例49 38 65 97 76 13 27i=2 38 (38 49)65 97 76 13 27i=3 65 (38 49 65)97 76 13 27i=4 97 (38 49 65 97)76 13 27i=5 76 (38 49 65 76 97)13 27i=6 13 (13 38 49 65 76 97)27i=1 ()i=7 (13 38 49 65 76 97)2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：第六章首页上页下页退出typedef structtypedef struct int key;int key;float info;float info;JD;JD;void straisort(JD r,int n)void straisort(JD r,int n)int i,j;int i,j;for(i=2;i=n;i+)for(i=2;i=n;i+)r0=ri;r0=ri;j=i-1;j=i-1;while(r0.keyrj.key)while(r0.keyrj.key)rj+1=rj;rj+1=rj;j-;j-;rj+1=r0;rj+1=r0;第六章首页上页下页退出3.2 3.2 希尔排序希尔排序(缩小增量法缩小增量法)排序过程：先取一个正整数排序过程：先取一个正整数d1nd1n，把所有把所有相隔相隔d1d1的记录放一组，组内进行直接插入的记录放一组，组内进行直接插入排序；然后取排序；然后取d2d1d2r2.keyr1.keyr2.key，则交换；然后比较第二个记录与第三个记录；则交换；然后比较第二个记录与第三个记录；依次类推，直至第依次类推，直至第n-1n-1个记录和第个记录和第n n个记录比个记录比较为止较为止第一趟冒泡排序第一趟冒泡排序，结果关键字最，结果关键字最大的记录被安置在最后一个记录上大的记录被安置在最后一个记录上对前对前n-1n-1个记录进行第二趟冒泡排序，结果个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第使关键字次大的记录被安置在第n-1n-1个记录位个记录位置置重复上述过程，直到重复上述过程，直到“在一趟排序过程中没在一趟排序过程中没有进行过交换记录的操作有进行过交换记录的操作”为止为止第六章首页上页下页退出 例例49 38 65 97 76 13 27 30 初初始始关关键键字字38 49 65 76 13 27 30 97 第第一一趟趟38 49 65 13 27 30 76 第第二二趟趟38 49 13 27 30 65 第第三三趟趟38 13 27 30 49 第第四四趟趟13 27 30 38 第第五五趟趟384976971397279730971376767627301365276530651313494930492738273830381 2 3 4 5 6 7 8第六章首页上页下页退出void bubble_sort(JD r,int n)int m,i,j,flag=1;JD x;m=n-1;while(m0)&(flag=1)flag=0;for(j=1;jrj+1.key)flag=1;x=rj;rj=rj+1;rj+1=x;m-;注注:冒泡排序等价与沉底算法冒泡排序等价与沉底算法第六章首页上页下页退出 3.43.4快速排序快速排序基本思想：基本思想：通过一趟排序，将某关键字通过比较直通过一趟排序，将某关键字通过比较直接到位，并将待排序记录分割成独立的接到位，并将待排序记录分割成独立的两部分，其中一部分记录的关键字均比两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序这两部分记录进行排序，以达到整个序列有序列有序第六章首页上页下页退出排序过程：对排序过程：对rstrst中记录进行一趟快速排中记录进行一趟快速排序，附设两个指针序，附设两个指针i i和和j j，设枢轴记录设枢轴记录rp=rsrp=rs，x=rp.keyx=rp.key初始时令初始时令i=s,j=ti=s,j=t首先从首先从j j所指位置向所指位置向前前搜索第一个关键字小搜索第一个关键字小于于x x的记录，并和的记录，并和rprp交换交换再从再从i i所指位置起向所指位置起向后后搜索，找到第一个关搜索，找到第一个关键字大于键字大于x x的记录，和的记录，和rprp交换交换重复上述两步，直至重复上述两步，直至i=ji=j为止为止再分别对两个子序列进行快速排序，直到每再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止个子序列只含有一个记录为止第六章首页上页下页退出例例初始关键字：初始关键字：49 38 65 97 76 13 27 50 ijxji 完成一趟排序：完成一趟排序：(27 38 13)49 (76 97 65 50)分别进行快速排序：分别进行快速排序：(13)27 (38)49 (50 65)76 (97)快速排序结束：快速排序结束：13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij第六章首页上页下页退出例例初始关键字：初始关键字：49 38 65 97 76 13 27 50 ijx.key=49ji 完成一趟排序：完成一趟排序：(27 38 13)49 (76 97 65 50)27ijijij65ji13ij4997ij第六章首页上页下页退出void qksort(JD r,int s,int t)int i,j,k;JD x;if(s=t)return;i=s;j=t;x=ri;while(ij)while(i=x.key)j-;if(ij)ri=rj;i+;while(ij)&(ri.key=x.key)i+;if(ij)rj=ri;j-;ri=x;qksort(r,s,j-1);qksort(r,j+1,t);第六章首页上页下页退出3.5 简单选择排序简单选择排序排序过程排序过程首先通过首先通过n-1n-1次关键字比较，从次关键字比较，从n n个记个记录中找出关键字最小的记录，将它与录中找出关键字最小的记录，将它与第一个记录交换第一个记录交换再通过再通过n-2n-2次比较，从剩余的次比较，从剩余的n-1n-1个记个记录中找出关键字次小的记录，将它与录中找出关键字次小的记录，将它与第二个记录交换第二个记录交换重复上述操作，共进行重复上述操作，共进行n-1n-1趟排序后，趟排序后，排序结束排序结束第六章首页上页下页退出例例初始：初始：49 38 65 97 76 13 27 jjjjjji=11349一趟：一趟：13 38 65 97 76 49 27 i=2kkjjjjj2738二趟：二趟：13 27 65 97 76 49 38 三趟：三趟：13 27 38 97 76 49 65 四趟：四趟：13 27 38 49 76 97 65 五趟：五趟：13 27 38 49 65 97 76 六趟：六趟：13 27 38 49 65 76 97 排序结束：排序结束：13 27 38 49 65 76 97第六章首页上页下页退出void smp_selesort(JD r,int n)int i,j,k;JD x;for(i=1;in;i+)k=i;for(j=i+1;j=n;j+)if(rj.keyrk.key)k=j;if(i!=k)x=ri;ri=rk;rk=x;第六章首页上页下页退出3.6 3.6 归并排序归并排序归并归并将两个或两个以上的有序表组合成将两个或两个以上的有序表组合成一个新的有序表，叫归并一个新的有序表，叫归并2-2-路归并排序路归并排序排序过程排序过程设初始序列含有设初始序列含有n n个记录，则可看成个记录，则可看成n n个有序的子序列，每个子序列长度为个有序的子序列，每个子序列长度为1 1两两合并，得到两两合并，得到 n/2n/2 个长度为个长度为2 2或或1 1的的有序子序列有序子序列再两两合并，再两两合并，如此重复，直至得如此重复，直至得到一个长度为到一个长度为n n的有序序列为止的有序序列为止第六章首页上页下页退出将下属两个将下属两个已排序的顺序表合并成一个有序表。已排序的顺序表合并成一个有序表。顺序比较两者的相应元素，小者移入另一表中，反顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。复如此，直至其中任一表都移入另一表为止。0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680至此至此 B 表的元素都已表的元素都已移入移入 C 表，只需将表，只需将 A 表的剩余部分移入表的剩余部分移入 C 表即可。表即可。第六章首页上页下页退出0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680至此至此 B 表的元素都已表的元素都已移入移入 C 表，只需将表，只需将 A 表的剩余部分移入表的剩余部分移入 C 表即可。表即可。97第六章首页上页下页退出例初始关键字：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第六章首页上页下页退出void mergeSort(Comparable a,int left,int right)if(leftright)/至少有至少有2个元素个元素 int i=(left+right)/2;/取中点取中点 mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);/合并到数组合并到数组b copy(a,b,left,right);/复制回数组复制回数组a 第六章首页上页下页退出void merge(JD r,JD tint h,int m,int w)void merge(JD r,JD tint h,int m,int w)int i,j,k;int i,j,k;i=h;j=m+1;k=h-1;i=h;j=m+1;k=h-1;while(i=m)&(j=w)while(i=m)&(j=w)k+;k+;if(ri.key=rj.key)if(ri.keym)if(im)while(j=w)t+k=rj+;while(j=w)t+k=rj+;else else while(i=m)t+k=ri+;while(i=m)t+k=ri+;
