《数据结构C语言版》----第10章ppt课件.ppt

《《数据结构C语言版》----第10章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章排序排序的基本概念插入排序选择排序交换排序归并排序基数排序性能比较主要知识点10.1排序的基本概念排序是对数据元素序列建立某种有序排列的过程,是把一个数据元素序列整理成按关键字递增（或递减）排列的过程。关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。主关键字:数据元素值不同时该关键字的值也一定不同，是能够惟一区分各个不同数据元素的关键字;不满足主关键字定义的关键字称为次关键字。内部排序是把待排数据元素全部调入内存中进行的排序。外部排序是因数量太大，把数据元素分批导入内存，排好序后再分批导出到磁盘和磁带外存介质上的排序方法。比较排序算法优劣的标准:(

2、1)时间复杂度:它主要是分析记录关键字的比较次数和记录的移动次数(2)空间复杂度:算法中使用的内存辅助空间的多少(3)稳定性:若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的10.2插入排序插入排序的基本思想是：每步将一个待排序的数据元素，按其关键码大小，插入到前面已经排好序的一组数据元素的适当位置上，直到数据元素全部插入为止。1.直接插入排序常用的插入排序有直接插入排序和希尔排序两种。其基本思想是：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。算法如下：voidInsertSort(DataType

3、a[],intn)//用直接插入法对a[0]--a[n-1]排序{inti,j;DataTypetemp;for(i=0;i-1&&temp.key<=a[j].key){a[j+1]=a[j];j--;}a[j+1]=temp;}}算法分析:(1)时间效率：因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。其他情况下也要考虑移动元素的次数。故时间复杂度为O(n2)(2)空间效率：仅占用1个缓冲单元——O(1)(3)算法的稳定性：稳定{64}789624{564}89624{576

4、4}624{576489}24{5676489}{567246489}589624初始关键字序列:第一次排序:第二次排序:第三次排序:第四次排序:第五次排序:7直接插入排序过程2.希尔(shell)排序(又称缩小增量排序)(1)基本思想：把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束。(2)技巧：小组的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个小组,让增量dk逐趟缩短（例如依次取5,3,1），直到dk＝1为止。(3)优点：让关键字值小的元素能很快前移，

5、且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。算法如下：voidShellSort(DataTypea[],intn,intd[],intnumOfD)//用希尔排序法对元素a[0]--a[n-1]排序，d[0]--d[numOfD-1]为希尔增量值{inti,j,k,m,span;DataTypetemp;for(m=0;m

6、=i+span){temp=a[i+span];j=i;while(j>-1&&temp.key<=a[j].key){a[j+span]=a[j];j=j-span;}a[j+span]=temp;}}}}653425871238564614779223563414771223654625879238结果序列d=6563414771223654625879238561214653423774625879238结果序列d=3561214653423774625879238121423253438465665778792结果序列d=1(a)(b)(c)希尔排序的排序过程10.3

7、选择排序基本思想是：每次从待排序的数据元素集合中选取关键字最小（或最大）的数据元素放到数据元素集合的最前（或最后），数据元素集合不断缩小，当数据元素集合为空时选择排序结束。常用的选择排序算法：（1）直接选择排序（2）堆排序1.直接选择排序基本思想是：从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元