《数据结构排序》PPT课件

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

1、第9章排序1目录9.1基本概念9.2插入排序9.3交换排序9.5归并排序退出9.4选择排序29．1基本概念排序:是计算机程序设计中的一项重要操作，其功能是指一个数据元素集合或序列重新排列成一个按数据元素某个数据项值有序的序列。排序码(关键码):排序依据的数据项。稳定排序:排序前与排序后相同关键码元素间的位置关系，保持一致的排序方法。不稳定排序:排序前与排序后相同关键码元素间的相对位置发生改变的排序方法。排序分为两类：（1）内排序:指待排序列完全存放在内存中所进行的排序。内排序大致可分为五类：插入排序、交换排序

2、、选择排序、归并排序和分配排序。本章主要讨论内排序。（2）外排序：指排序过程中还需访问外存储器的排序。为了以后讨论方便，我们直接将排序码写成一个一维数组的形式，并且在没有声明的情形下，所有排序都按排序码的值递增排列。39.2插入排序基本思想：每次将一个待排序的元素，按其关键字的大小插入到前面已经排好序的子文件的适当位置，直到全部记录插入完成为止。9.2.1直接插入排序直接插入排序的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每

3、次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。4例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如下：直接插入排序举例5voidD-InsertSort(datatypeR[],intn)/*待排序的n个元素放在数组R中，用直接插入法进行排序*/{for(i=2;i<=n;i++)/*i控制第i-1次插入,最多进行n-1次插入*/if(R[i].key

4、时,需将R[i]插入有序表*/{R[0]=R[i];/*为统一算法设置监视哨*/for(j=i-1;R[0].key

5、(i=2,3,…,n)。因此，直接插入排序的时间复杂度为O（n2）。直接插入算法的元素移动是顺序的，该方法是稳定的。79.2.2希尔排序(缩小增量排序)希尔排序的基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上有较大提高。8八个元素的关键码分别为：91，67，35，62，29，72，4

6、6，57，希尔排序算法的执行过程为：希尔排序过程举例9希尔排序算法voidShellSort(datatypeR[],intd[],intt)/*按增量序列d[0]、d[1]、d[2]、…、d[t-1]对顺序表R[1]、R[2]、…、R[n]作希尔排序，注意d[0]、d[1]、d[2]、…、d[t-1]除1之外不能有公因子，且d[t-1]必须为1*/{for(k=0;k

7、]、R[2]、…、R[n]进行一趟插入排序，dk为增量、步长*/{for(i=dk+1;i<=n;i++)if(R[i].key0)&&(R[0].key

8、量级，因为当分组较多时，组内元素较少；此循环次数少；当分组较少时，组内元素增多，但已接近有序，循环次数并不增加。因此，希尔排序的时间复杂性在O（nlog2n）和O（n2）之间，大致为O（n1.3）。由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。119.3交换排序主要是通过排序表中两个记录关键码的比较，若与排序要求相逆（不符合升序或