[工学]软件技术基础课件5.ppt

第三章查找与排序(下) 第三章 查找与排序(下) *3.3 基本的排序技术 3.4 二叉排序树及其查找 3.4.1 二叉排序树及其构造 3.4.2 二叉排序树查找 *3.5 多层索引树(略) 3.5.1 B-树 3.6 拓扑分类 本节内容 通过本单元的学习，了解、掌握有关排序的： 基本概念： 排序、排序分类、算法稳定性 典型的排序算法: 插入排序、选择排序、交换排序 快速排序、归并排序 排序的基本概念 定义：将记录按关键字递增(递减)的次序排列起来，形成新的有序序列，称为排序。 描述： 设n个记录的序列为{R1,R2,…,Rn},其相应关键字序列为{K1,K2,…,Kn},需确定一种排序P1,P2,…,Pn,使其相应的关键字满足递增(升序),或递减(降序)的关系: Kp1 ? Kp2 ?... ?Kpn 或 Kp1 ? Kp2 ?…. ? Kpn 排序算法的数据结构 为简单起见，这里用顺序存储结构描述待排序的记录。 顺序存储结构（C语言描述）： #define N n struct record { int key ； /* 关键字项 */ int otherterm； /* 其它项 */ } ； typedef struct record RECORD； RECORD file[N+1]；/*RECORD型的N+1元数组*/ 典型排序算法 冒泡排序 快速排序 简单插入排序 希尔排序 简单选择排序 堆排序 归并排序 基数排序 一、冒泡排序 1.指导思想： 两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对元素，直到全部数列满足有序为止。 冒泡排序（Bubble sort）是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。 ? ? ? … ? a1 a2 a3 … an-1 an 2.冒泡排序算法 step1 从待排序队列的前端开始(a1)两两比较记录的关键字值，若aiai+1(i=1,2,…,n-1)，则交换ai和ai+1的位置，直到队列尾部。一趟冒泡处理，将序列中的最大值交换到an的位置。 step2 如法炮制，第k趟冒泡，从待排序队列的前端开始(a1)两两比较ai和ai+1（i=1 , 2 , …n-k)，并进行交换处理，选出序列中第k大的关键字值，放在有序队列的最前端。(思考：为什么i=1,…n-k?) Step3 最多执行n-1趟的冒泡处理，序列变为有序。 从小到大排序 3.冒泡排序实现 bubble(int *item,int count) { int a,b，t; for(a=1;acount; a++) /*n-1趟冒泡处理*/ for(b=1;b=count-a;b++)/*每趟n-i次的比较*/ if(item[b-1]item[b])/*若逆序，则交换*/ { t=item[b-1]; /* 它们的位置 */ item[b-1]=item[b]; item[b]=t; } } 4.改进的冒泡排序 从上述举例中可以看出，从第4趟冒泡起，序列已有序，结果是空跑了3趟。若两次冒泡处理过程中，没有进行交换，说明序列已有序，则停止交换。这就是改进的冒泡算法的处理思想。 用改进的冒泡算法进行处理，比较次数有所减少。 对于数列{ 65,97,76,13,27,49,58 } 比较次数 第1趟 {65，76，13，27，49，58}，{97} 6 第2趟 {65，13，27，49，58}，{76，97} 5 第3趟 {13，27，49，58}，{65，76，97} 4 第4趟 {13，27，49}，{58，65，76，97} 3 总计： 18 次 bubble_a(int *item,int count) { int a,b,t,c; for(a=1;acount;++a) /* n-1趟的循环 */ { c=1; /* 设置交换标志