数据结构-程序员联合开发网.ppt

第三章 内部排序算法,3.1 直接插入排序 3.2 希尔排序 3.3 冒泡排序 3.4 快速排序 3.5 简单选择排序 3.6 归并排序,分类：内部排序：全部记录都可以同时调入内存进行的排序。外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。,内 部 排 序,插入排序,交换排序,选择排序,归并排序,基数排序,有序表中插入元素，并保持其有序,将表中关键字比较，位置不对交换,先查找关键字，再交换。,将两个有序的关键字序列进行归并,不比较，按多关键字排序方法,直接,折半,2-路,表,希尔,冒泡,快速,简单,树型,堆,3.1 直接插入排序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序,例,49 38 65 97 76 13 27,i=2 38(38 49)65 97 76 13 27,i=3 65(38 49 65)97 76 13 27,i=4 97(38 49 65 97)76 13 27,i=5 76(38 49 65 76 97)13 27,i=6 13(13 38 49 65 76 97)27,i=1(),i=7(13 38 49 65 76 97)27,27,97,76,65,49,38,27,typedef struct int key;float info;JD;void straisort(JD r,int n)int i,j;for(i=2;i=n;i+)r0=ri;j=i-1;while(r0.keyrj.key)rj+1=rj;j-;rj+1=r0;,3.2 希尔排序(缩小增量法)排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止,思考:算法的代码实现?,3.3冒泡排序排序过程将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止,例,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,1 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),注:冒泡排序等价与沉底算法,3.4快速排序基本思想：通过一趟排序，将某关键字通过比较直接到位，并将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序,排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，x=rp.key初始时令i=s,j=t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换重复上述两步，直至i=j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止,完成一趟排序：(27 38 13)49(76 97 65 50),分别进行快速排序：(13)27(38)49(50 65)76(97),快速排序结束：13 27 38 49 50 65 76 97,49,27,49,65,13,49,49,97,x.key=49,完成一趟排序：(27 38 13)49(76 97 65 50),27,65,13,49,97,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(i=x.key)j-;if(ij)ri=rj;i+;while(ij),3.5 简单选择排序排序过程首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束,例,初始：49 38 65 97 76 13 27,i=1,13,49,一趟：13 38 65 97 76 49 27,i=2,27,38,六趟：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 归并排序归并将两个或两个以上的有序表组合成一个新的有序表，叫归并2-路归并排序排序过程设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1两两合并，得到n/2个长度为2或1的有序子序列再两两合并，如此重复，直至得到一个长度为n的有序序列为止,将下属两个已排序的顺序表合并成一个有序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,i,j,k,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,i,j,k,7,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,至此 B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可。,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,至此 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)int i,j,k;i=h;j=m+1;k=h-1;while(im)while(j=w)t+k=rj+;else while(i=m)t+k=ri+;,