数据结构之排序算法.ppt

第二章?数据结构与算法 在此幻灯片插入公司的徽标 从“插入”菜单 选择图片 找到徽标文件 单击“确定” 重新设置徽标大小 单击徽标内任意位置。徽标外部出现的方框是“调整控点” 使用这些重新设置对象大小 如果在使用尺寸调整控点前按下 shift 键，则对象改变大小但维持原比例。 10 65 865 姓名 学号 成绩 班级 李红 9761059 95 机97.6 A B C D E F G 注意带以下内容： 图2-8-1 图2-8-2 图2-8-3 图2-8-4 图2-8-5 (续) 2.8 排 序 2.8.1 概 述 1、排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。 2、排序过程的组成步骤： 首先比较两个关键字的大小； 然后将记录从一个位置移动到另一个位置。 假设待排序的记录存放在地址连续的一组存储单元中，那么这种存储方式下的数据类型可描述为： MAX 0 1 2 3 4 ……… key info #define MAX 20 typedef struct { int key; float otherinfo; }RedType; 排序方法 插入排序 选择排序 交换排序 归并排序 直接插入排序 折半插入排序 简单选择排序 堆排序 起泡排序 快速排序 2.8.2 插入排序 直接插入、折半插入 1、直接插入排序: 基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。 举例：图8-2-1 2.8.2 插入排序 直接插入、折半插入 该算法适合于n 较小的情况，时间复杂度为O(n2). 1、直接插入排序: 基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上 待排元素序列：[53] 27 36 15 69 42 第一次排序： [27 53] 36 15 69 42 第二次排序： [27 36 53] 15 69 42 第三次排序： [15 27 36 53] 69 42 第四次排序： [15 27 36 53 69] 42 第五次排序： [15 27 36 42 53 69] 直接插入排序示例 对于有n个数据元素的待排序列，插入操作要进行n-1次 void insertSort(RedType L[ ],int n) { int i ,j; for(i=2; i=n; i++) if(L[i].keyL[i-1].key) { L[0]=L[i]; /* 作为监视哨*/ for( j=i-1; L[0].keyL[j].key; ? ?j ) L[j+1]=L[j]; /* 记录后移*/ L[j+1]=L[0]; /* 插入 */ } } 插入算法如下： 方法:Ki与Ki-1,K i-2,…K1依次比较,直到找到应插入的位置。 2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置 。待排序元素越多，改进效果越明显。 折半插入排序的条件： 在有序序列中插入一个关键字。 举例，图8-2-2 2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。 例：有6个记录，前5 个已排序的基础上，对第6个记录排序。 [ 15 27 36 53 69 ] 42 ? low ?mid ? high [ 15 27 36 53 69 ] 42 ?low ? high