内部排序37396.pptVIP

1、概述 10.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]; } } 折半插入排序 排序过程：用折半查找方法确定插入位置的排序叫~ 算法描述 希尔排序(缩小增量法) 排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止 算法描述 10.2 交换排序 冒泡排序 排序过程 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].keyr[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止 算法描述 快速排序 基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序 void qksort(JD r[],int start,int end){ //对r[start..end]作快速排序 if (startend){ zx=Patition(r,start,end); //一趟排序取得轴位置 qksort(r,start,zx-1); //左子列快速排序 qksort(r,zx+1,end); //右子列快序排序 } } void partition(JD r[],int low,int high) { //交换表r[low,high]中的记录，找到轴记录位置，到位并使之左边小，右边大 JD x; if(low=high) return; //出口 x=r[low]; //保存轴元素， while(lowhigh) //从表两端交替向中间扫描找轴位置 { while((lowhigh)(r[high].key=x.key)) --high; //从后向前扫描 r[low]=r[high]; //遇到第一个比x小的移到左边low处 while((lowhigh)(r[low].key=x.key)) low++; //从前向后扫描小则过 lowr[high]=r[low]； //遇第一个比x大的移到右边high } //low 即是轴的位置 r[low]=x; //放轴元素 return low } 10.3 选择排序 简单选择排序 排序过程 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换 重复上述操作，共进行n-1趟排序后，排序结束 堆排序 堆的定义：n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆 堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫~ 堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法——筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选” 10.4 归并排序 归并——将两个或两个以上的有序表组合成一个新的有序表，叫~ 2-路归并排序 排序过程 设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1 两两合并，得到?n/2?个长度