资源预览内容
第1页 / 共18页
第2页 / 共18页
第3页 / 共18页
第4页 / 共18页
第5页 / 共18页
第6页 / 共18页
第7页 / 共18页
第8页 / 共18页
第9页 / 共18页
第10页 / 共18页
亲,该文档总共18页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
排序,排序定义将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列叫 排序分类 按待排序记录所在位置 内部排序:待排序记录存放在内存 外部排序:排序过程中需对外存进行访问的排序 按排序依据原则 插入排序:直接插入排序、折半插入排序、希尔排序 交换排序:冒泡排序、快速排序 选择排序:简单选择排序 其它排序: 堆排序等,排序基本操作 比较两个关键字大小 将记录从一个位置移动到另一个位置,1 插入排序 直接插入排序 排序过程:整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序,算法描述,例,49 38 65 97 76 13 27,i=2 38 (38 49) 65 97 76 13 27,i=3 65 (38 49 65) 97 76 13 27,i=4 97 (38 49 65 97) 76 13 27,i=5 76 (38 49 65 76 97) 13 27,i=6 13 (13 38 49 65 76 97) 27,i=1 ( ),i=7 (13 38 49 65 76 97) 27,27,97,76,65,49,38,27,算法评价 时间复杂度 若待排序记录按关键字从小到大排列(正序) 关键字比较次数:,记录移动次数:,若待排序记录按关键字从大到小排列(逆序) 关键字比较次数:,记录移动次数:,若待排序记录是随机的,取平均值 关键字比较次数:,记录移动次数:,T(n)=O(n),空间复杂度:S(n)=O(1),折半插入排序 排序过程:用折半查找方法确定插入位置的排序叫,例,i=1 (30) 13 70 85 39 42 6 20,i=2 13 (13 30) 70 85 39 42 6 20,i=7 6 (6 13 30 39 42 70 85 ) 20,.,i=8 20 (6 13 20 30 39 42 70 85 ),算法描述,算法评价 时间复杂度:T(n)=O(n) 空间复杂度:S(n)=O(1),希尔排序(缩小增量法) 排序过程:先取一个正整数d1n,把所有相隔d1的记录放一组,组内进行直接插入排序;然后取d2d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止,希尔排序特点 子序列的构成不是简单的“逐段分割”,而是将相隔某个增量的记录组成一个子序列 希尔排序可提高排序速度,因为 分组后n值减小,n更小,而T(n)=O(n),所以T(n)从总体上看是减小了 关键字较小的记录跳跃式前移,在进行最后一趟增量为1的插入排序时,序列已基本有序 增量序列取法 无除1以外的公因子 最后一个增量值必须为1,2 交换排序 冒泡排序 排序过程 将第一个记录的关键字与第二个记录的关键字进行比较,若为逆序r1.keyr2.key,则交换;然后比较第二个记录与第三个记录;依次类推,直至第n-1个记录和第n个记录比较为止第一趟冒泡排序,结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序,结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程,直到“在一趟排序过程中没有进行过交换记录的操作”为止,49 38 65 97 76 13 27 30,初始关键字,算法描述,算法评价 时间复杂度 最好情况(正序) 比较次数:n-1 移动次数:0 最坏情况(逆序) 比较次数:,移动次数:,空间复杂度:S(n)=O(1),T(n)=O(n),快速排序 基本思想:通过一趟排序,将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录进行排序,以达到整个序列有序 排序过程:对rst中记录进行一趟快速排序,附设两个指针i和j,设枢轴记录rp=rs,x=rp.key 初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录,并和rp交换 再从i所指位置起向后搜索,找到第一个关键字大于x的记录,和rp交换 重复上述两步,直至i=j为止 再分别对两个子序列进行快速排序,直到每个子序列只含有一个记录为止,完成一趟排序: ( 27 38 13) 49 (76 97 65 50),分别进行快速排序: ( 13) 27 (38) 49 (50 65) 76 (97),快速排序结束: 13 27 38 49 50 65 76 97,49,27,49,65,13,49,49,97,3 选择排序 简单选择排序 排序过程 首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换 再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换 重复上述操作,共进行n-1趟排序后,排序结束,例,初始: 49 38 65 97 76 13 27 ,i=1,13,49,一趟: 13 38 65 97 76 49 27 ,i=2,27,38,六趟: 13 27 38 49 65 76 97 ,排序结束: 13 27 38 49 65 76 97,算法描述,算法评价 时间复杂度 记录移动次数 最好情况:0 最坏情况:3(n-1) 比较次数:,空间复杂度:S(n)=O(1),T(n)=O(n),习题,以关键字序列(503,087,512,061,908,170,897,275,653,426)为例,手工执行以下排序算法,写出每一趟排序结束时的关键字状态。 (1)直接插入排序 (2)冒泡排序 (3)快速排序 (4)简单选择排序,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号