数据结构6(4月28日).ppt

**直接插入排序 基本思想： 将n个待排序元素看成为一个有序表和一个无序表。开始有序表只有一个元素，无序表中则有n-1个元素。排序过程中每次从无序表中取出第一个元素，将其关键字与有序表的关键字比较，将其插入到适当位置，使之成为新的有序表。 插入步骤： （1）将无序表中的第一个元素存入辅助变量temp中。 （2）将temp和有序表中从最后一个元素开始进行比较，若小于有序表中的元素，则有序表中该元素后移一位，同时继续和前一元素比较。否则插入到该元素的后面。 一趟归并后，有序子文件长度为2，二趟归并后，有序子文件长度为4，因归并的结果在b中,故每次归并完将其复制到a中。重复此过程，直到有序子文件为n，具体算法描述如下 void mergeSort(int a[], int n) { int k=1,b[N];//N为已定义的符号常量,代表线性表的长度 while(kn) { merge(a,k,n,b); k=2*k; for(int i=0;iN;i++) a[i]=b[i]; } } 各种排序方法的比较 2.7.3 归并排序 采用二路归并技术，即每次将数组a中两个相邻的有序序列归并为一个有序序列。 排序步骤： （1）假设待排序文件含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1 （2）两两归并，得到[n/2]个长度为2或1的有序子序列 （3）再两两归并，直到得到一个长度为n的有序文件为止。 初始状态 [45] [21] [34] [19] [52] [60] [34] [24] ┕━━┙ ┕━━┙ ┕━━┙ ┕━━┙ 第一趟 [21 45] [19 34] [52 60] [24 34] ┕━━┙ ┕━━┙ 第二趟 [19 21 34 45] [24 34 52 60] ┕━━━━━━┙ 第三趟 19 21 24 34 34 45 52 60 二路归并排序过程示例 二路归并排序是稳定的排序 有序文件a[s..m]和a[m+1...t]归并为b[s..t]的算法: twoSort(int a[],int s,int m,int t,int b[]) { int i,j,k; i=s; //i是a[s..m] 的指示器 j=m+1; //j是a[m+1..t] 的指示器 k=s-1; // k是b[s..t] 的指示器 while( ) { k++; if(a[i]=a[j]) { ; i++; } else { ; j++; } } b[k]=a[i] b[k]=a[j] i=m j=t if(im) for(; ;j++) { k++; b[k]=a[j]; } else for(; ;i++) { k++; b[k]=a[i]; } } j=t i=m 假设文件长度为n,每个子文件的长度为k，归并结果存放在数组b中，则一趟归并描述如下: void merge(int a[],int k,int n,int b[]) { int i=0; while (n-i=2*k) { twosort(a,i,i+k-1,i+2*k-1,b); i=i+2*k; } if(n-ik) twosort(a,i,i+k-1,n-1,b); else for(;in;i++) b[i]=a[i]; } * 查找： 根据给定的关键字值，在一组数据元素中确定一个其关键字值等于给定值的数据元素的过程。若存在这样的数据元素，则称查找成功；若不存在这样的数据元素，则称查找失败。 关键字: 指数据元素中可以标识该数据元素的一组数据项。例如学生记录中的学号；公民记录中的身份证号码等。 查找表： 指一组待查数据元素的集