计算机软件技术基础课件-8(排序).ppt

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

1、1、选择排序2、插入排序3、交换排序排序1、选择排序简单选择排序基本操作：在当前无序区中选择一个关键字最小的记录，将它与无序区中最前端的记录进行交换。排序的通俗定义：整理文件中的记录，使得它按照关键字递增(减)的次序排列。排序有内部排序和外部排序之分，本课程只讨论内部排序。排序可按主关键字进行，此时排序结果唯一；若按次关键字排列，则结果不唯一。12412202731345675假设有含有7个记录的序列(以关键字表示)：{5，4，12，20，27，3，1}无序区范围有序区范围Min(Key)1、选择排序

2、简单选择排序基本操作：在当前无序区中选择一个关键字最小的记录，将它与无序区中最前端的记录进行交换。排序的通俗定义：整理文件中的记录，使得它按照关键字递增(减)的次序排列。排序有内部排序和外部排序之分，本课程只讨论内部排序。排序可按住关键字进行，此时排序结果唯一；若按次关键字排列，则结果不唯一。12342027125345671假设有含有7个记录的序列(以关键字表示)：{5，4，12，20，27，3，1}无序区范围有序区范围1、选择排序简单选择排序基本操作：在当前无序区中选择一个关键字最小的记录，将它与无序区中

3、最前端的记录进行交换。排序的通俗定义：整理文件中的记录，使得它按照关键字递增(减)的次序排列。排序有内部排序和外部排序之分，本课程只讨论内部排序。排序可按住关键字进行，此时排序结果唯一；若按次关键字排列，则结果不唯一。12345271220345671假设有含有7个记录的序列(以关键字表示)：{5，4，12，20，27，3，1}无序区范围有序区范围1、选择排序简单选择排序基本操作：在当前无序区中选择一个关键字最小的记录，将它与无序区中最前端的记录进行交换。排序的通俗定义：整理文件中的记录，使得它按照关键字递增

4、(减)的次序排列。排序有内部排序和外部排序之分，本课程只讨论内部排序。排序可按住关键字进行，此时排序结果唯一；若按次关键字排列，则结果不唯一。12345122720345671假设有含有7个记录的序列(以关键字表示)：{5，4，12，20，27，3，1}无序区范围有序区范围1、选择排序简单选择排序基本操作：在当前无序区中选择一个关键字最小的记录，将它与无序区中最前端的记录进行交换。排序的通俗定义：整理文件中的记录，使得它按照关键字递增(减)的次序排列。排序有内部排序和外部排序之分，本课程只讨论内部排序。排序可

5、按住关键字进行，此时排序结果唯一；若按次关键字排列，则结果不唯一。12345122027345671假设有含有7个记录的序列(以关键字表示)：{5，4，12，20，27，3，1}无序区范围有序区范围1、选择排序SelSort(r，n)//对含有n个记录的序列按递增排序1.Fori=1ton-12.j←i3.Fork=i+1ton4.Ifr[j]＞r[k]thenj←k5.end(k)6.Ifj＞ithen7.{temp←r[i];r[i]←r[i];r[j]←temp}8.end(i)简单选择排序算法描述：如

6、果j=i则无需交换，即无序区最前端的记录就是关键字最小的记录算法分析根据记录的比较次数及记录的移动次数两指标来评价算法的执行效率。比较次数：移动次数：当原始序列递增有序时，移动次数为0；当原始序列递减有序时，每趟排序都要进行记录的交换，而每次交换需进行3次移动，因此最大移动次数为3(n-1)。算法的时间复杂度为O(n2)。在无序区中找关键字最小的记录，并用j记下其所在位置。共进行n-1趟排序1241220273134567512272042、插入排序基本操作：将当前无序区中最前端的记录插入到有序区中。线性插入

7、排序无序区范围有序区范围待插入记录2、插入排序基本操作：将当前无序区中最前端的记录插入到有序区中。线性插入排序12512202731345674无序区范围有序区范围待插入记录32、插入排序基本操作：将当前无序区中最前端的记录插入到有序区中。线性插入排序122027134567无序区范围有序区范围待插入记录112543InsertSort(r，n)1.Fori=2ton2.r[0]←r[i];j←i-13.whiler[0]＜r[j]do4.r[j+1]←r[j];j←j-15.end(while)6.r[j+

8、1]←r[0]7.end(i)8.return线性插入排序算法：算法中引进一个附加记录r[0]有两个作用：保存r[i]的副本(即无序区中最前端的记录)，从而保证不因记录的后移而丢失r[i]的内容；在while循环中监视下标j是否越界，一旦越界(j<1)，则r[0]自动控制while循环结束，从而避免在while循环中每次都要检查j是否越界；算法分析每趟排序中，无需后移记录，但是在进入while循环之