数据结构 - 程序员联合开发网(精品·公开课件).ppt

第三章 内部排序算法 分类： 内部排序：全部记录都可以同时调入内存进行的排序。 外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。 3.1 直接插入排序 直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序 typedef struct { int key; float info; }JD; void straisort(JD r[],int n) { int i,j; for(i=2;i=n;i++) { r[0]=r[i]; j=i-1; while(r[0].keyr[j].key) { r[j+1]=r[j]; j--; } r[j+1]=r[0]; } } 3.2 希尔排序(缩小增量法) 排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止 3.3冒泡排序 排序过程 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].keyr[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止 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;j=m;j++) if(r[j].keyr[j+1].key) { flag=1; x=r[j]; r[j]=r[j+1]; r[j+1]=x; } m--; } } 3.4快速排序 基本思想： 通过一趟排序，将某关键字通过比较直接到位，并将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序 排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key 初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止 void qksort(JD r[],int s,int t) { int i,j,k; JD x; if(s=t) return; i=s; j=t; x=r[i]; while(ij) { while((ij)(r[j].key=x.key)) j--; if(ij) { r[i]=r[j]; i++; } while((ij)(r[i].key=x.key)) i++; if(ij) { r[j]=r[i]; j--; } } r[i]=x; qksort(r,s,j-1); qksort(r,j+1,t); } 3.5 简单选择排序 排序过程 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换 重复上述操作，共进行n-1趟排序后，排序结束 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(r[j].keyr[k].key) k=j; if(i!=k) { x=r[i]; r[i]=r[k]; r[k]=x; } } } 3.6 归并排序 归并——将两个或两个以上的有序表组合成一个新的有序表，叫归并