c语言完整版课件全套ppt教学教程最全整套电子教案电子讲义（必威体育精装版）.ppt

* 1、直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。 基本思想：在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。 13.2 排序 * 有序序列elem[0..i-1] elem[i] 无序序列 elem[i..n-1] 一趟直接插入排序的基本思想： 有序序列elem[0..i] 无序序列elem[i+1..n-1] 13.2 排序 * 实现“一趟插入排序”可分三步进行： 3．将elem[i] 插入(复制)到elem[j+1]的位置上。 2．将elem[j+1..i-1]中的所有记录均后移 一个位置； 1．在elem[0..i-1]中查找elem[i]的插入位置， elem[0..j] ? elem[i] elem[j+1..i-1] ； 13.2 排序 * （1）如何构造初始的有序序列？ （2）如何查找待插入记录的插入位置? 需解决的关键问题? 13.2 排序 * elem 0 1 2 3 4 5 21 18 25 22 10 25* 21 21 25 i = 1 18 22 10 25* 25 i = 2 18 22 10 25* 25 22 21 25 21 15 10 25* 25 21 15 10 25* 25 21 18 15 10 18 10 25* i = 3 18 i = 5 18 25* i = 4 13.2 排序 * 解决方法： 将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。 关键问题(1)如何构造初始的有序序列？ 算法描述： for (i=1; in; i++) { 插入第i个记录，即第i趟直接插入排序； } 13.2 排序 * 关键问题(2)如何查找待插入记录的插入位置? 解决方法： 在i个记录的有序区elem[0] ~ elem[i-1]中插入记录elem[i]，首先顺序查找elem[i]的正确插入位置，然后将elem[i]插入到相应位置。 算法描述： for(j=i-1; j=0 eelem[j]; j--) { elem[j+1]=elem[j]; } 13.2 排序 * 49 38 65 97 76 13 27 i=1 (38 49 ) 65 97 76 13 27 i=2 (38 49 65 ) 97 76 13 27 i=3 (38 49 65 97 ) 76 13 27 i=4 (38 49 65 76 97 ) 13 27 i=5 (13 38 49 65 76 97 ) 27 i=0 ( ) i=6 (13 38 49 65 76 97 ) 27 j j j j j j 97 76 65 49 38 27 (13 27 38 49 65 76 97) 结果： 0 1 2 3 4 5 6 13.2 排序 * void StraightInsertSort(ElemType elem[], int n) // 操作结果:对数组elem作直接插入排序序 { for ( int i = 1; i n; i++) { // 第i趟直接插入排序 ElemType e = elem[i]; // 暂存elem[i] int j; // 临时变量 for (j = i - 1; j = 0 e elem[j]; j--) { // 将比e大的计录都后移 elem[j + 1] = elem[j]; // 后移 } elem[j + 1] = e; // j+1为插入位置 } } 13.2 排序 */58 【定义】：由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2， ... ... ， an) 线性表的定义 ( Linear List ) 例1、26个英文字母组成的字母表 （A，B，C ，... ... ， Z）