《《查找与排序》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《查找与排序》PPT课件.ppt（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 查找与排序查找与排序在文件系统中，经常要对文件的记录进行各种各样的操作，在文件系统中，经常要对文件的记录进行各种各样的操作，主要包括：主要包括：文件的查找：对用户指定的文件中的记录进行查找，也称文件的查找：对用户指定的文件中的记录进行查找，也称为检索。为检索。插入记录：将一个新的记录插入到文件的指定位置。插入记录：将一个新的记录插入到文件的指定位置。记录的删除：从文件中删除指定的记录。记录的删除：从文件中删除指定的记录。文件的排序：对文件中的记录按指定的关键字的顺序进行文件的排序：对文件中的记录按指定的关键字的顺序进行排序。排序。修改文件的记录：修改文件中记录的内容，并更新。修改
2、文件的记录：修改文件中记录的内容，并更新。2.1 2.1 顺序查找顺序查找如果一个文件具有如果一个文件具有n个连续的记录，可将该文件读到个连续的记录，可将该文件读到内存中的一个顺序表中进行各种操作。顺序查找就是在文内存中的一个顺序表中进行各种操作。顺序查找就是在文件的关键字集合件的关键字集合key1,2,.,n中找出与给定的关键字中找出与给定的关键字key相相等的文件记录。如图等的文件记录。如图2-2所示，磁盘中有这样一个顺序文件。所示，磁盘中有这样一个顺序文件。对文件中记录的查找就是对其关键字的查找，找到了关键对文件中记录的查找就是对其关键字的查找，找到了关键字就找到了该关键字对应的那条记录
3、。字就找到了该关键字对应的那条记录。2.2 2.2 折半查找折半查找如果从文件中读取的数据记录的关键字是有序排列的，如果从文件中读取的数据记录的关键字是有序排列的，则可以用一种效率更高的查找方法来查找文件中的记录，这则可以用一种效率更高的查找方法来查找文件中的记录，这就是折半查找法，又称为二分搜索。就是折半查找法，又称为二分搜索。折半查找的基本思想是：减小查找序列的长度，分而治折半查找的基本思想是：减小查找序列的长度，分而治之地进行关键字的查找。它的查找过程是：先确定待查找记之地进行关键字的查找。它的查找过程是：先确定待查找记录的所在的范围，然后逐渐缩小查找的范围，直至找到该记录的所在的范围，
4、然后逐渐缩小查找的范围，直至找到该记录为止（也可能查找失败）。录为止（也可能查找失败）。2.3 2.3 排序的概述排序的概述对于文件而言，排序可以理解为：根据文件记录的关对于文件而言，排序可以理解为：根据文件记录的关键字的值的递增或者递减关系将文件的记录的次序进行重键字的值的递增或者递减关系将文件的记录的次序进行重新排列的过程。排序后的文件记录一定是按关键字值有序新排列的过程。排序后的文件记录一定是按关键字值有序排列的。例如最开始从磁盘中读出的文件如图排列的。例如最开始从磁盘中读出的文件如图2-5所示。所示。2.4 2.4 直接插入排序直接插入排序直接插入排序直接插入排序(Straight I
5、nsertion Sort)是一种最为简是一种最为简单的排序方法，因此也被称为简单插入排序。单的排序方法，因此也被称为简单插入排序。直接插入排序的基本思想是：第直接插入排序的基本思想是：第i趟排序将序列中的第趟排序将序列中的第i+1个元素个元素ki+1插入到一个已经按值有序的子序列插入到一个已经按值有序的子序列(k1,k2,.,ki)中的合适的位置，使得插入后的序列仍然保中的合适的位置，使得插入后的序列仍然保持按值有序。持按值有序。2.5 2.5 选择排序选择排序选择排序选择排序(selection sort)也是一种比较常见的排序方法。也是一种比较常见的排序方法。它的基本思想是：第它的基本思
6、想是：第i趟排序从序列的后趟排序从序列的后n-i+1（i=1,2,n-1）个元素中选择一个最小的元素，与该个元素中选择一个最小的元素，与该n-i+1个元素的最前面那个个元素的最前面那个元素进行位置交换，也就是与第元素进行位置交换，也就是与第i个位置上的元素进行交换，直个位置上的元素进行交换，直到到i=n-1。直观地讲，每一趟的选择排序就是从序列中未排好顺。直观地讲，每一趟的选择排序就是从序列中未排好顺序的元素中选择一个最小的元素，将该元素与这些未排好顺序序的元素中选择一个最小的元素，将该元素与这些未排好顺序的元素的第一个元素交换位置。的元素的第一个元素交换位置。2.6 2.6 冒泡排序冒泡排序
7、冒泡排序冒泡排序(bubble sort)是最为常用的一种排序方法。是最为常用的一种排序方法。它是一类具有它是一类具有“交换交换”性质的排序方法。冒泡排序的基本性质的排序方法。冒泡排序的基本思想可描述如下。思想可描述如下。将序列中的第将序列中的第1个元素与第个元素与第2个元素进行比较，若前者个元素进行比较，若前者大于后者，则将第大于后者，则将第1个元素与第个元素与第2个元素进行位置交换，否个元素进行位置交换，否则不交换。则不交换。再将第再将第2个元素与第个元素与第3个元素进行比较，同样若前者大个元素进行比较，同样若前者大于后者，则将第于后者，则将第2个元素与第个元素与第3个元素进行位置交换，否
8、则个元素进行位置交换，否则不交换。不交换。依此类推，直到将第依此类推，直到将第n-1个元素与第个元素与第n个元素进行比较个元素进行比较为止。为止。2.7 2.7 希尔排序希尔排序希尔排序希尔排序(Shells sort)又称为又称为“缩小增量排序缩小增量排序”(Diminishing Increment Sort)，是由希尔在，是由希尔在1959年提出的。年提出的。希尔排序是对插入排序的一种改进，在效率上较前面所讲的希尔排序是对插入排序的一种改进，在效率上较前面所讲的几种排序方法有较大改进。几种排序方法有较大改进。希尔排序的基本思想是：设定一个元素间隔增量希尔排序的基本思想是：设定一个元素间隔
9、增量gap，将，将参加排序的序列按这个间隔数参加排序的序列按这个间隔数gap从第从第1个元素开始依次分成个元素开始依次分成若干个子序列。若干个子序列。2.8 2.8 快速排序快速排序快速排序快速排序(quick sort)是由是由C.A.R Hoarse提出的一种排序提出的一种排序算法，它是冒泡排序的一种改进算法。由于快速排序算法元算法，它是冒泡排序的一种改进算法。由于快速排序算法元素之间的比较次数较少，速度较快，因而得名快速排序。在素之间的比较次数较少，速度较快，因而得名快速排序。在各种内部排序方法中，快速排序被认为是目前最好的一种排各种内部排序方法中，快速排序被认为是目前最好的一种排序方法。序方法。快速排序算法的基本思想是：在当前的排序序列快速排序算法的基本思想是：在当前的排序序列(k1,k2,kn)中任意选取一个元素，把该元素称为基准元素中任意选取一个元素，把该元素称为基准元素或支点，把小于等于基准元素的所有元素都移到基准元素的或支点，把小于等于基准元素的所有元素都移到基准元素的前面，把大于基准元素的所有元素都移到基准元素的后面，前面，把大于基准元素的所有元素都移到基准元素的后面，这样使得基准元素所处的位置恰好就是排序的最终位置，并这样使得基准元素所处的位置恰好就是排序的最终位置，并且把当前参加排序的序列划分为前后两个子序列。且把当前参加排序的序列划分为前后两个子序列。