文档介绍：排序的基本概念(P200)排序算法的稳定性:假定在待排序的记录集中,存在多个具有相同键值的记录,若经过排序,这些记录的相对次序仍然保持不变,即在原序列中,ki=kj且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。:在排序的整个过程中,:由于待排序的记录个数太多,不能同时放置在内存,而需要将一部分记录放置在内存,另一部分记录放置在外存上,整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。:⑴比较:关键码之间的比较;⑵移动:记录从一个位置移动到另一个位置。:,排序是线性结构的一种操作,待排序记录可以用顺序存储结构或链接存储结构存储。假定1:采用顺序存储结构,关键码为整型,且记录只有关键码一个数据项。 intr[n+1]; //待排序记录存储在r[1]~r[n],r[0]留做他用假定2:将待排序的记录序列排序为升序序列。,其主要思想是:在待排序列中选两个记录,将它们的关键码相比较,如果反序(即排列顺序与排序后的次序正好相反),则交换它们的存储位置。冒泡排序的改进。(P202)冒泡排序的时间性能分析最好情况(正序):比较次数:n-1移动次数:0时间复杂度为O(n)。最坏情况(反序):54321时间复杂度为O(n2)。43215321452134512345比较次数:移动次数:2)1(1-=å=nn(n-i)n-1i2)1(1-=å=n3n3(n-i)n-1i平均情况:时间复杂度为O(n2)。冒泡排序的时间性能分析冒泡排序的性能分析在平均情况下,冒泡排序的时间复杂度与最坏情况同数量级。冒泡排序只需要一个记录的辅助空间,用来作为记录交换的暂存单元。冒泡排序是一种稳定的排序方法。选择排序的主要操作是选择,其主要思想是:每趟排序在当前待排序序列中选出关键码最小的记录,添加到有序序列中。:第i趟在n-i+1(i=1,2,…,n-1)个记录中选取关键码最小的记录作为有序序列中的第i个记录。需解决的关键问题?⑴如何在待排序序列中选出关键码最小的记录?⑵如何确定待排序序列中关键码最小的记录在有序序列中的位置?简单选择排序