[理学]第八章 排序与查找.ppt

第八章 排序与查找 数据结构（C描述） 8.1 排序的基本概念 排序（Sorting） 对于有n个结点的线性表 ,按照节点某些数据项的关键字按递增或者递减的次序,重新排列线性表结点的过程称为排序 简单地说，排序就是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。 排序码 : 作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。 有序表与无序表: 一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表。 内排序与外排序: 按照排序过程中使用内外存的不同将排序方法分为内排序和外排序。若排序过程全部在内存中进行，则称为内排序；若排序过程需要不断地进行内存和外存之间的数据交换，则称为外排序。内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序和分配排序。本章仅讨论内排序。 第二节 直接插入排序 直接插入排序（Straight Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。 直接插入排序的算法实现 void insertsort(ElemType R[],int n) //待排序元素用一个数组R表示，数组有n个元素 { for ( int i=1; in; i++) //i表示插入次数，共进行n-1次插入 { ElemType temp=R[i]; //把待排序元素赋给temp int j=i-1; while ((j=0) (tempR[j])) { R[j+1]=R[j]; j--; } // 顺序比较和移动 R[j+1]=temp;} } 第三节 二分插入排序 二分插入排序（Binary Insert Sort）的基本思想是：在有序表中采用二分查找的方法查找待排元素的插入位置。 其处理过程：先将第一个元素作为有序序列，进行n-1次插入，用二分查找的方法查找待排元素的插入位置，将待排元素插入。 第四节 希尔排序 希尔排序（Shell Sort）又称为“缩小增量排序”。是1959年由D.L.Shell提出来的。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。 第五节 冒泡排序 由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。例如，给定排序码3，4，2，2，则希尔排序的结果变成2，2，3，4 。 冒泡排序（Bubble Sorting）的基本思想是：是通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。 第九节 二路归并排序 二路归并排序的基本思想是：将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从1增加到n（元素个数）时，整个区间变为一个，则该区间中的有序序列即为我们所需的排序结果。 第十节 查找的基本概念 查找(searching) 就是在按某种数据结构形式存储的数据集合中,找出满足指定条件的节点 查找的分类 按查找的条件分类,可以分为按结点的关键码查找,关键码以外的其他数据项查找或其他数据项的组合查找等. 按查找的目的分类,可分为静态查找和动态查找. 静态查找 查找只是为了确定指定条件的结点存在与否 动态查找 查找是为了确定结点的插入位置或为了删除找到的结点 所谓关键字(key)是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。 例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。 但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中，姓名不能唯一标识一个数据元素(因有同名同姓