插入排序解析.ppt

概要插入排序快速排序选择排序合并排序，第8章内部排序，8.1概要，排序：将数据元素的任意序列按关键字顺序排序。 数据表(datalist):是要排序的数据对象的有限集合。 主键：数据对象具有多个属性字段。 换句话说，它包含多个数据成员，其中包含用于将对象作为排序关键字区分开来的属性字段。 也称为排序代码。 相反，如果排序方法的稳定性：对象序列包含两个对象Ri和Rj，则这些排序代码Ki=Kj使得对象Ri排列在排序之前。 如果排序之后对象Ri仍然在对象Rj之前，则排序方法可以说是稳定的，否则排序方法可能是不稳定的。 内部排序和外部排序：内部排序是指在排序过程中数据对象全部存储在存储器中的排序。外部排序是指在排序期间内所有对象的数量过多，不能同时存储在存储器中，必须根据排序过程的要求在内部外部存储器之间移动此外，排序的时间开销：排序的时间开销是测量算法的好坏的最重要的指标。 排序时间的开销可以通过算法执行中的数据比较次数和数据移动次数来测量。内排序分类、按不同原则插入排序、交换排序、选择排序、合并排序、计数排序等。 根据需要的工作量简单排序-时间复杂度O(n2)先进排序方法-时间复杂度O(nlogn )基数排序-时间复杂度O(d.n )、8.2插入排序(InsertSorting )基本思想以其排序代码的大小先进行排序当基本思想插入第i(i1)个对象时，前面的V0、V1、Vi-1已经排名。 此时，将Vi的排序代码与Vi-1、Vi-2、的排序代码的顺序进行比较，找到插入位置时插入Vi，原来位置的对象向后移动。 将直接插入排序(StraightInsertSort )、voidInsertSort(SqList/插入正确位置)算法10.1、直接插入排序的算法、算法分析、排序对象个数设为n时，该算法的主程序排序代码的比较次数和对象移动次数与对象排序代码的初始排列有关。 在最佳情况下(正序)，排序前的对象按照排序代码从小到大的顺序排序，每次仅与前一顺序的对象的序列的最后的对象进行一次比较，仅移动0次对象，整体的排序代码的比较次数为n-1，对象的移动次数为0。 在最坏的情况下(逆序)，第I次将第I个记录和前面的第I个记录进行比较，每一次比较必须进行一次记录移动。 总排序代码比较次数KCN和记录移动次数RMN分别是平均的比较次数和记录移动次数约n2/4。 因此，直接插入排序的时间复杂度为O(n2 )。 直接插入排序是一种稳定的排序方法。半插入排序(BinaryInsertsort )、基本思想设定序列表中有记录序列V1、V2、Vn。 其中，V1、V2、Vi-1是已排序的记录。 插入Vi时，用折叠检索法查找Vi的插入位置。 另外，两个比较对象记录算法(省略)、8.3快速排序(QuickSort )和交换排序(exchangesort )以反向顺序(即排序顺序与排序后的顺序相反)交换，直到所有对象都被排序。 基本方法：还可以将要排序的序列中的对象的数目设置为n。第一次，将相邻的两个记录的关键字从1到n依次进行比较，按照相反的顺序进行更换的结果，在这n个记录中，关键字最大的记录被更换到第n个位置的第二次，将相邻的两个记录的关键字从1到n-1依次进行比较，反之亦然在该n-1记录中，关键字最大记录被调换到第n-1位置，一般而言，第I次的鼓泡排名按照从1到n-i 1的顺序比较相邻的两个记录的关键字，如果是逆顺序，则在该n-i 1记录中， 具有最大关键字的记录被替换为第n-i 1个位置，最多n-1次-到n-(n-1) 1=2，气泡排序，21，08，25，49，25，16，21，49，25，25，16，08，21，49，25，25，16， 08、初始关键字、第1次排序、第4次排序、第2次排序、第3次排序、第21、49、25、25、16、085次排序是泡沫排序的过程、泡沫排序的算法(教材page 16 )、void bubble _ sort (inta 、inta i=2/有交换，I次排序记录系列a1、a2、an-i 1的排序结果，将该系列中关键字最大的记录交换为系列的第n-i 1个位置，其他记录也移动到排序的最终位置。 最多可起泡n-1次，重新排列所有记录。 如果记录的初始排列是正序的，则算法只执行一次泡沫，进行n-1次关键字比较，不移动记录。 这是最好的情况。 在最坏情况下，第一个序列按逆序排列，该算法执行n-1次鼓泡，第I次进行第n-i次关键字比较，执行第n-i次记录交换。 合计关键词比较次数KCN和记录移动次数RMN为：最坏时间复杂度为O(n2)气泡排序是稳定的排序方法。 快速排序(QuickSort )、基本思想：以要排序的记录序列中的某个记录为基准，根据该记录的关键字大小，将记录序列整体分为左右子序列。 左侧子序列中所有记录的排序代码小于或等于基准记录的排序代码右侧子序列中所有记录的排序代码大于基准记录的排序代码基准记录位于这两个子序列之间(也是该记录最终应放置的位置)。 另外，对这两个子序列重复执行上述方法，直到所有记录都排列在相应的位置上。 基准记录也称为透视(或透视)记录。 QuickSort(List)if(List长度为1以上) 将序列List分为两个子序列LeftList和RightList，quick sort (left list ) quick sort (right list ) 将两个子序列LeftList和RightList合并为一个序列List )，编写快速排序算法，快速排序过程，21，08，25，49，25，*16，初始关键字，08，25，49，25，* 16，21，08，22 08、25、49、25、*16、08、25、49、25、*16、08、25、49、25、* 25、*16、25、49、25、*16、21、导频密钥二次交换、三次交换、四次交换、一次排序、I、j、I、08、25、49 21、一次排序，分别为高速排序，08、25、49、25 *、16、21，有序排序，08、25、49、25 *、16， 21快速排序算法void quick sort (与sqlist/右序列相同的处理算法10.7，intPartition(SqList ) )算法10.6(b )、算法Partition以序列中的第一个对象为基准算法将排序代码小于基准对象的排序代码的对象移动到序列的左侧，最后放置基准对象，执行函数返回其位置的循环。 另外，算法Quicksort是递归算法，递归树如图所示。 算法分析、快速排序的圈数取决于递归树的高度。 如果每次分割记录时，该记录的左侧子序列和右侧子序列的长度相同，则下一步最好对两个长度为一半的子序列进行排序。 在n个要素的系列中，定位一个记录所需的时间为O(n )。 假设t(n )是对n个元素的序列进行排序所需的时间，如果在每次正确定位一个记录时将该序列划分成长度正好相等的两个子序列，则总的计算时间为T(n)cn 2T(n/2)/c是常数cn2 (cn/22t (n/4 ) )=2n4t (n/4 ) 2n 42 t (n/8 ) )=3cn8t (n/8 )cn log2nt (1)=o(nlog2n )可以证明，函数quicksort的平均计算时间也是o (nlog2n )。实验结果表明，对于平均计算时间，高速排序是所有内部排序方法中最好的。 快速排序是递归的，需要存储每层递归调用时的指针和参数的堆栈。 最大递归呼叫层次数与递归树的高度一致，理想的是log2(n1)。 因此，要求存储开销为O(log2n )。 在最坏的情况下，即应该排名的数组的关键词是秩序(正序或反序)的情况下，该递归树成为单一枝树，每次分割只能得到比上次少一个对象的子序列。 如果整体关键字的比较次数增多，则算法的最差时间复杂度为O(n2)，改善了透视记录的选择，“三者进入”的快速排序是不稳定的排序方法。基本思想：在n-i 1(i=1、n-1 )记录中，将关键字最小的记录作为按顺序排列的第I个记录。 选择“8.4排序”(SelectionSort )，移动记录，然后简单地选择排序是一种简单的排序方法，其基本过程是选择组中第一个对象rirn-1中关键字最小的记录替换组中的第一个对象。从组中排除具有最小排序代码的对象。 对于剩馀的对象Vi 1Vn-1，重复、步骤，直到剩馀的对象只有一个为止。简单选择排序(SimpleSelectionSort )、简单选择排序的过程、不更换最小者25*、直接选择排序的算法voidselectsort(sqltist )算法10.9、关键字比较次数KCN是记录的初始分配在设定了n个记录的情况下，第I次具有最小的关键字记录所需的比较次数始终为n-i次。 在整体关键字比较次数中，记录的移动次数RMN与记录序列的初始排列相关联。 在第一个序列为正的情况下，RMN取最小值“0”而在最差的情况下每次进行交换，RMN取最大值3(n-1 )。 总的时间复杂度为O(n2)的简单选择排序是不稳定的排序方法。堆排序(Heapsort )、堆(Heap )的定义：有关键词集合，存储在以完全二叉树的顺序存储的一维数组中。 它们从根开始，从上到下，同一层从左到右从1开始连续编号。 如果满足kik2iki2i1或kik2iki2i2i1，则该关键字集合称为组成一个堆。 前者叫做小根(顶)炉，后者叫做萝卜(顶)炉。 堆叠顺序步骤(以小根峰为例)1.根据初始输入数据，调整初始峰的2 .输出炉顶要素(最小记录)3.剩馀元素，并重复步骤2和3，直到形成新堆的4 .剩馀要素的数量变为零。 累积排名：49，25，25，21，16，08，1，2，3，4，5，6，08，25，25，25，25，21，25，25，21，25，25，21，25，25，21，16，08，1 将第六种元素与位置互换，以取代第一个萝卜堆积、第一个萝卜堆积、第二个萝卜堆积、第三个萝卜堆积、第一个萝卜堆积、第一个萝卜堆积、第一个萝卜堆积、第二个萝卜堆积、第三个萝卜堆积、第二个萝卜堆积、第三个萝卜堆积、第五个萝卜堆积、第四个萝卜堆积1625*21082549，交换1号和5号元素，5号元素所在，从1号到5号在萝卜的山上重新调整，25，16，08，21，25，49，1，2，3，4，5，6，08，16，25，25，25 1，2，3，5，21，49，1，3，6，5，4，2，25 * 1620829，08162125*2549，交换1号位于4号元素，4号元素，从1号到4号再调整为萝卜的山，21，16，25，08，25，44 08，16，25，25，21，49，1，3，6，5，4，2，21160825 * 2549，08162125*2549，交换1号和3号元素，3号元素位于这里，从1号到3号重新调整为萝卜的山， 16、08、25*、21、25、49、1、2、3、4、5、6、08、16、25*、25、21、49、1、3、6、5、4、2、1608225*2549、08162125*2549、交换1号和2号元素、2号元素位于从1号到2号的萝卜堆中方法：从顶部向下“筛选”，堆调整(问题2 )，rc=38，s，j，s，voidHeapAdjust(HeapType/插入)算法10.10，萝卜堆“筛选”算法，初始堆构建(问题1 )如何从无序序列创建初始堆？ 如果对应于序列的完全二叉树的根节点的左右子树已经是堆，则可以使用“滤波”算法将整个二叉树调整为堆。 解决方法：按照子树的规模从小到大的顺序，从最初的完整二叉树的底部向上阶段性地调整(筛选)，直到二叉树整体成为堆栈！ 图标：第一个大堆的创建过程，初始关键字集合，i=3局部调整后，将、voidaheapsort (heap type/h.r 1.I-1 重新调整为萝卜堆算法10.11，堆的创建算法，堆排序的最差时间复杂度为O(nlog2n ) 算法的空间复杂度是O(1)。 堆积排序是一种不稳定的排序方法。 (为什么)排序算法分析，8.5合并排序，将两个以上的顺序表合并成新的顺序表。 2路合并(2路合并)原始序列initList中的两个规则表initListlinitListm和initListm 1initListn合并到一个规则表中，从而生成另一个记录序列ms 0812525 * 49627293，163754，leftmidmid 1right，initList，ij，086215*37