第八章 排序与查找.ppt

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

1、第八章排序与查找数据结构（C描述）8.1排序的基本概念排序（Sorting）对于有n个结点的线性表,按照节点某些数据项的关键字按递增或者递减的次序,重新排列线性表结点的过程称为排序简单地说，排序就是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。排序码:作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。有序表与无序表:一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表。内排序与外排序:按照排序过程中使用内外存的不同将排序方法

2、分为内排序和外排序。若排序过程全部在内存中进行，则称为内排序；若排序过程需要不断地进行内存和外存之间的数据交换，则称为外排序。内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序和分配排序。本章仅讨论内排序。为了以后讨论方便，我们直接将排序码写成一个一维数组的形式，具体类型设为Elemtype，并且在没有声明的情形下，所有排序都按排序码的值递增排列。排序插入排序（直插排序、二分排序、希尔排序）交换排序（冒泡排序、快速排序）选择排序（直选排序、树型排序、堆排序）归并排序（二路归并排序、多路归并排序）分配排序（多关键字排序、基数排序）第二节直接插入排序直接插入排序（St

3、raightInsertionSorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。直接插入排序的算法实现voidinsertsort(ElemTypeR[],intn)//待排序元素用一个数组R表示，数组有n个元素{for(inti=1;i

4、ntj=i-1;while((j>=0)&&(temp

5、yInsertSort）的基本思想是：在有序表中采用二分查找的方法查找待排元素的插入位置。其处理过程：先将第一个元素作为有序序列，进行n-1次插入，用二分查找的方法查找待排元素的插入位置，将待排元素插入。2．二分插入排序的算法实现其算法如下：voidBinaryInsertSort(ElemTypeR[],intn){for(inti=1;i

6、ddle])right=middle-1;//取左区间elseleft=middle+1;}//取右区间for(intj=i-1;j>=left;j--)R[j+1]=R[j];//元素后移空出插入位R[left]=temp;}}第四节希尔排序希尔排序（ShellSort）又称为“缩小增量排序”。是1959年由D.L.Shell提出来的。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好

7、情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。例如，n=8，数组R的八个元素分别为：17，3，30，25，14，17，20，9。下面用图9-2给出希尔排序算法的执行过程。17330251417209初始状态，I=414317920173025第二趟结果，I=139141717202530第三趟结果14320917173025第一趟结果，I=2图9-2希尔排序算法的执行过程第五节冒泡排序由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不