《数据结构》PPT课件(I)

《《数据结构》PPT课件(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章内部排序算法3.1直接插入排序3.2希尔排序3.3冒泡排序3.4快速排序3.5简单选择排序3.6归并排序分类：内部排序：全部记录都可以同时调入内存进行的排序。外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。内部排序插入排序交换排序选择排序归并排序基数排序有序表中插入元素，并保持其有序将表中关键字比较，位置不对交换先查找关键字，再交换。将两个有序的关键字序列进行归并不比较，按多关键字排序方法直接折半2-路表希尔冒泡快速简单树型堆3.1直接插入排序直接插入排序排序过程：整个排序过程为

2、n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：typedefstruct{i

3、ntkey;floatinfo;}JD;voidstraisort(JDr[],intn){inti,j;for(i=2;i<=n;i++){r[0]=r[i];j=i-1;while(r[0].key

4、3=1三趟分组：1327485544938659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：1327485544938659776二趟排序：1344838274955659776取d1=5一趟分组：4938659776132748554取d2=3二趟分组：13274855449386597763.3冒泡排序排序过程将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个

5、记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止例4938659776132730初始关键字3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟3849769713972797309713767

6、676273013652765306513134949304927382738303812345678voidbubble_sort(JDr[],intn){intm,i,j,flag=1;JDx;m=n-1;while((m>0)&&(flag==1)){flag=0;for(j=1;j<=m;j++)if(r[j].key>r[j+1].key){flag=1;x=r[j];r[j]=r[j+1];r[j+1]=x;}m--;}}注:冒泡排序等价与沉底算法3.4快速排序基本思想：通过一趟排序，将某关键

7、字通过比较直接到位，并将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key初始时令i=s,j=t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换重复上述两步，直至i==j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止

8、例初始关键字：4938659776132750ijxji完成一趟排序：(273813)49(76976550)分别进行快速排序：(13)27(38)49(5065)76(97)快速排序结束：13273849506576974927ijijij4965ji1349ij4997ij例初始关键字：4938659776132750ijx.key=49ji完成一趟排序：(273813)49(76976550)27ijijij65ji13