软件技术基础第03章排序课件.ppt

《软件技术基础第03章排序课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学目标了解有关排序的基本概念排序的典型算法二叉排序树1排序(Sorting)将一个无序序列整理成按值非递减（或非递增）顺序排列的有序序列。排序可以在不同的存储结构上实现。基本排序是在顺序存储的线性表中实现的；二叉排序树利用二叉树的链式存储结构实现无序表的有序化。三种基本排序方法：交换排序（如冒泡排序和快速排序）；插入排序（如简单插入排序和希尔排序）；选择排序（如简单选择排序和堆排序）；2顺序存储结构（C语言描述）：#defineNnstructrecord{intkey；/*关键字项*/intotherterm；/*其它项*

2、/}；typedefstructrecordRECORD；RECORDfile[N+1]；排序算法的数据结构3二、典型排序算法冒泡排序快速排序简单插入排序希尔排序简单选择排序堆排序4交换排序的基本思想：两两比较待排序记录的关键值，若发生逆序则交换之，直至所有记录都排好序。交换排序的两种形式冒泡排序快速排序交换排序5冒泡排序冒泡排序（Bubblesort）是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最

3、后（或最前）位置。直到全部元素有序为止。…a1a2a3…an-1an最大值6冒泡排序算法举例设有数列{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第5趟{13，27}，{49，58，65，76，97}2第6趟{13}，{27，49，58，65，76，97}1总计：21次7冒泡排序算法bubbl

4、e(int*item,intcount){inta,b，t;for(a=1;aitem[b])/*若逆序,则交换*/{t=item[b-1];/*它们的位置*/item[b-1]=item[b];item[b]=t;}}8冒泡排序算法主程序#defineN7#include"stdio.h"main(){ints[]={65,97,76,13,27,49,58},i;bubble(s,N

5、);/*调用选择排序函数*/printf("Thesortedstringis:");for(k=0;k

6、}，{76，97}5第3趟{13，27，49，58}，{65，76，97}4第4趟{13，27，49}，{58，65，76，97}3总计：18次10改进的冒泡排序算法bubble_a(int*item,intcount){inta,b,t,c;for(a=1;aitem[b])/*若逆序，则*/{t=item[b-1];/*交换位置*/item[b-1]=ite

7、m[b];item[b]=t;c=0;}/*若有交换，则*/}/*改变交换标志*/if(c)break;/*若没有交换，则*/}/*退出处理*/}11算法讨论若待排序列有序(递增或递减),则只需进行一趟冒泡处理即可;若反序，则需进行n-1趟的冒泡处理。在最坏的情况下,冒泡算法的时间复杂度是O(n2)。当待排序列基本有序时，采用冒泡排序法效果较好。冒泡排序算法是稳定的。12快速排序快速排序法是一位计算机科学家C.A.R.Hoare推出并命名的。曾被认为是最好的一种排序方法。快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一

8、种算法。因此，被称为“分区交换排序”。13快速排序基本思想在待排序序列中按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成{左子序列}K{右子序列}再分别对左、右两部分实施上述分解过程，直到各子序列长度为1，即有序为止