查找排序动画制课件

1、查找、排序动画制作查找、排序动画制作制作人：苑查找排序动画制课件一、查找一、查找 查找是指在一个给定的数据结构中查找某个指定的元素。对给定的值与数据集合中各记录的关键字进行比较或计算，若找到与该值匹配的关键字，则查找成功；否则，查找失败。 关键字指被用于查找的元素属性，通常它可以唯一标识一个元素。 若在查找过程中同时插入查找表中不存在的元素，或者从查找表中删除已存在的某个元素，则为动态查找；若在查找过程中不进行插入或删除操作，则为静态查找。 查找是指在一个给定的数据结构中查找某个指定这里主要讨论查找方法，并对他们作简要的性能分析。 这里主要讨论查找方法，并对他们作简要的性能分析。 1、顺序查找

2、 顺序查找的方法是从表的一端开始，逐一比较查找关键字key和表中数据元素x的值是否匹配，若两个数据一致则查找成功，同时给出该数据元素在表中的位置，否则查找失败。1、顺序查找 顺序查找的方法是从表的一端2、折半查找 折半查找又称二分法查找是对有序表进行查找的方法。将给定的数据与有序表中间位置的元素做比较，若两者相等则查找成功；若前者小于后者则在中间位置左边的元素中继续查找；若前者大于后者则在中间位置右边的元素中继续查找。不断重复这一过程直到查找成功，或者直到查找区间缩小为一个元素时却仍未找到目标，则查找失败。2、折半查找 折半查找又称二分法查找是对有序算法描述： 设置查找区间初值，设下界low

3、= 0，设上界high = length-1。 若lowhigh则计算中间位置mid = (low +high)/2。 若keydatamid，则设low = mid+1并继续执行步骤； 若key=datamid则查找成功，返回目标元素位置mid+1（位置从1计数）。 若当low=high时，key!=datamid则查找失败，返回0 算法描述：3、分块查找 分块查找又称索引顺序查找，是折半查找和顺序查找方法的综合运用。 该方法要求把数据表中的元素均匀的分成若干块，每块中的元素可以是任意排列的，但块与块之间必须是有序的，即第i块中所有的元素值都小于（或大于）第i+1块中所有元素的值。 分块查找

4、需分两步进行：先确定待查元素所在的块，然后在块中顺序查找。3、分块查找 分块查找又称索引顺序查找，是折二、排序二、排序 将一组数据按照一定的次序关系（如大小）排列就称为排序，它是计算机内经常进行的一种操作，其目的是将一组同类型的记录序列调整为按照元素关键字有序的记录序列。例如将学生记录按学号排序，将课程记录按课程编码排序。 由于排序要花费很多的计算机时间，所以，对于一个未排序的结点序列的排序是计算机应用科学的一个重要问题。 将一组数据按照一定的次序关系（如大小）排列排序方法按数据的数量和存储设备不同，可将排列分为内部排序和外部排序两大类。按排序方法实现特点可分为插入排序、选择排序、交换排序、归

5、并排序等。按排序方法的效率可分为简单的排序法、先进的排序法等。简单的排序法包括插入排序、选择排序、冒泡排序等。时间复杂度为O(n2)。先进的排序法包括快速排序、归并排序等。时间复杂度大约为O(nlog2n)。 排序方法按数据的数量和存储设备不同，可将排列分为内部排序和外直接插入排序 直接插入排序方法的基本思想是：将记录分为有序和无序两个序列，假定当插入第k个记录时，前面的R1，R2，Rk-1已经排好序，而后面的Rk，Rk+1，Rn仍然无序。 这时用Rk的关键字与Rk-1的关键字进行比较,若Rk小于Rk-1则将Rk-1向后移动一个单元；再用Rk与Rk-2比较，若Rk小于Rk-2则将Rk-2向后移

6、动一个单元，依次比较下去，直到找到插入位置即将Rk插入。初始状态可以认为有序序列为R1。 直接插入排序 直接插入排序方法的基本思想是： 显示在序列35，22，16，19，22上应用插入排序的过程，为了对序列中相同记录加以区别，使用了下划线。 初始状态： 35 22 16 19 22 第1趟 ： 2235161922 第2趟 ： 1622351922第3趟 ： 1619223522 第4趟 ： 16192235 22 直接插入排序执行过程 显示在序列35，22，16，19，22初始状态： 35 22 16 19 22初始状态： 35 22 16 19 第1趟 ： 2235161922第1趟 ：

7、2235161922第2趟 ： 1622351922第2趟 ： 1622351922第3趟 ： 1619223522第3趟 ： 1619223522第4趟 ： 16 192235 22 第4趟 ： 16 192235 22简单选择排序 简单选择排序的基本思想是：将记录分为有序和无序两个序列，假定第k趟排序时，前面的R1，R2，,Rk-1已经排好序，而后面的Rk，Rk+1，,Rn仍然无序。 则选择Rk到Rn中的关键字最小的记录与Rk交换，交换后有序序列增加了第k个记录。 当第n-1趟选择执行完,待排序记录只剩下1个,就不用再选了。 在初始状态时，可以认为有序序列为空。简单选择排序 在序列35，2

8、2，16，19，22上应用简单选择排序的过程。 初始状态： 35 22 16 19 第1趟 ： 16 22 35 19 第2趟 ： 16 19 35 22 第3趟 ： 16 19 22 35 第4趟 ： 16 19 22 35 在序列35，22，16，19，22上应用简单选择排序第1趟 ： 16 22 35 19第1趟 ： 16 22 35 19第2趟 ： 16 19 35 22第2趟 ： 16 19 35 22第3趟 ： 16 19 22 35第3趟 ： 16 19 22 35第4趟 ： 16 19 22 35第4趟 ： 16 19 22 35冒泡排序冒泡排序的基本思路： 第一趟排序对全部记

9、录R1，R2，Rn自左向右顺次两两比较，若Rk大于Rk+1则交换Rk和Rk+1( k=1, 2, n-1)。第一趟排序完成后Rn成为序列中最大记录。 第二趟排序对序列前n-1个记录采用同样的比较和交换方法，第二趟排序完成后Rn-1成为序列中仅比Rn小的次大的记录。 第三趟排序对序列前n-2个记录采用同样处理方法。如此做下去，最多做n-1趟排序，整个序列就排序完成。 冒泡排序下图显示了在序列35，22，16，19，22上应用冒泡排序的过程。 初始状态：35 22 16 19 第1趟 ： 22 16 19 35 第2趟 ： 16 19 22 35 第3趟 ： 16 19 22 35 第4趟 ： 16 19 22 35下图显示了在序列35，22，16，19，22上应用冒泡第1趟 ： 22 16 19 35第1趟 ： 22 16 19 35第2趟 ： 16 19 22 35第2趟 ： 16 19 22 35第3趟 ： 16 19 22 35第3趟 ： 16 19 22 35第4趟 ： 16 19 22 35第4趟 ： 16 19 22 35 快速排序 快速排序的基本思想是：任取待排序序列中某个记录S(例如取第一个记录)作为基准，经过一系列比