第8章 内部排序.ppt

《第8章 内部排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章内部排序8.1排序的基本概念8.2简单排序8.3高级排序本章要点排序的定义和各种排序方法的特点各种方法的排序过程各种排序方法的的时间复杂度本章难点希尔排序关键路径快速排序堆排序归并排序学习目标掌握排序的定义和各种排序方法的特点掌握各种方法的排序过程及其依据的原则掌握各种排序方法的的时间复杂度8.1排序的基本概念——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问8.1排序的基本概念按排序依据原则插入排序：直接插入排序、折半插入排序、

2、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序8.1排序的基本概念排序的分类1.按照待排序数据是否在内存：内部排序和外部排序2.按照排序算法理解、编写的难易：简单排序和高级排序3.按照排序后得到的结果是否惟一：稳定排序和不稳定排序的按排序所需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(logn)基数排序：T(n)=O(d.n)排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置8.2简单排序简单排序的概念算法编写简单，容易理解和实现的排序算法。简单排序的时间复杂度

3、O(n2)简单排序种类直接插入排序、冒泡排序、简单选择排序。8.2简单排序1、直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。8.2简单排序直接插入排序voidInsertSort(LineListR[],intn){inti,j;LineListtmp;for(i=1;i=0&&tmp.key

4、R[j+1]=tmp;}}8.2简单排序2、冒泡排序又称简单交换排序。将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。8.2冒泡排序过程示例冒泡排序voidBubbleSort(LineListR[],intn

5、){inti,j,exchange;LineListtmp;for(i=0;ii;j--)if(R[j].key

6、趟排序后，排序结束例初始：[49386597761327]kjjjjjjkki=11349一趟：13[386597764927]i=2kkjjjjj2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序结束：132738496576978.2选择排序过程示例选择排序voidSelectSort(LineListR[],intn){inti,j,k;LineListtmp;for(i=0;i

7、{k=i;for(j=i+1;j

8、序为止。取d3=1三趟分组：1327485544938659776三趟排序：413273848