插入排序解析课件.ppt
概述插入排序快速排序选择排序归并排序,第八章 内部排序,8.1 概 述,排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据表(datalist):它是待排序数据对象的有限集合。主关键字(key):数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据，称为关键字。也称为排序码。,排序方法的稳定性:如果在对象序列中有两 个对象Ri和Rj,它们的排序码 Ki=Kj,且在排序之前,对象Ri排在Rj前面。如果在排序之后,对象Ri仍在对象Rj的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。,排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。,内排序分类,依不同原则插入排序、交换排序、选择排序、归并排序、和计数排序等。依所需工作量简单排序-时间复杂度O(n2)先进排序方法-时间复杂度O(n logn)基数排序-时间复杂度O(d.n),8.2 插入排序(Insert Sorting),基本思想 每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。,基本思想 当插入第i(i 1)个对象时,前面的V0,V1,Vi-1已经排好序。这时,用Vi的排序码与Vi-1,Vi-2,的排序码顺序进行比较,找到插入位置即将Vi插入,原来位置上的对象向后顺移。,直接插入排序(Straight Insert Sort),void InsertSort(SqList/插入到正确位置 算法 10.1,直接插入排序的算法,算法分析,设待排序对象个数为 n,则该算法的主程序执行n-1趟。排序码比较次数和对象移动次数与对象排序码的初始排列有关。最好情况下(正序）,排序前对象已按排序码从小到大有序,每趟只需与前面有序对象序列的最后一个对象比较1次,移动0次对象,总的排序 码比较次数为 n-1,对象移动次数为 0。,最坏情况下(逆序）,第 i 趟时第 i 个记录必须与前面 i 个记录都做比较,并且每做1次比较就要做1次记录移动。则总排序码比较次数KCN和记录移动次数RMN分别为,在平均情况下的比较次数和记录移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 O(n2)。直接插入排序是一种稳定的排序方法。,折半插入排序(Binary Insertsort),基本思想 设在顺序表中有一 个记录序列 V1,V2,Vn。其中,V1,V2,Vi-1 是已经排好序的记录。在插入Vi 时,利用折半查找法寻找Vi 的插入位置。,算法(略）,8.3 快速排序(Quick Sort),交换排序(Exchange Sort)两两比较待排序的记录,如发生逆序(即排列顺序与排序后的次序正好相反)，则交换之,直到所有对象都排好序为止。,基本方法:设待排序对象序列中的对象个数为n。第1趟,从1到n依次比较相邻两个记录的关键字，若逆序则交换，其结果是这n个记录中，关键字最大的记录被交换到第n的位置上;第2趟,从1到n-1依次比较相邻两个记录的关键字，若逆序则交换，其结果是这n1个记录中，关键字最大的记录被交换到第n-1的位置上;一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录的关键字，若逆序则交换，其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上;最多做n-1趟-从1到 n-(n-1)+1=2,起泡排序(Bubble Sort),21,08,25,49,25,16,21,49,25,25,16,08,21,49,25,25,16,08,初始关键字,第一趟排序,第四趟排序,第二趟排序,第三趟排序,21,49,25,25,16,08,第五趟排序,起泡排序的过程,起泡排序的算法（教材 page 16)void bubble_Sort(int a,int n)for(i=n,change=TRUE;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)起泡排序是一个稳定的排序方法。,快速排序(Quick Sort),基本思想：任取待排序记录序列中的某个记录(例如取第一个记录)作为基准,按照该记录的关键字大小,将整个记录序列划分为左右两个子序列：左侧子序列中所有记录的排序码都小于或等于基准记录的排序码 右侧子序列中所有记录的排序码都大于基准记录的排序码基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。,分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。基准记录也称为枢轴（或支点）(pivot)记录。,QuickSort(List)if(List的长度大于1)将序列List划分为两个子序列 LeftList 和 Right List;QuickSort(LeftList);QuickSort(RightList);将两个子序列 LeftList 和 RightList 合并为一个序列List;,快速排序算法描述,快速排序的过程,21,08,25,49,25*,16,初始关键字,08,25,49,25*,16,21,08,25,49,25*,16,08,25,49,25*,16,08,25,49,25*,16,08,25,49,25*,16,21,pivotkey,一次交换,二次交换,三次交换,四次交换,完成一趟排序,i,j,i,j,j,i,08,25,49,25*,16,21,完成一趟排序,分别进行快速排序,08,25,49,25*,16,21,有序序列,08,25,49,25*,16,21,快速排序的算法void QuickSort(SqList/对右序列同样处理 算法 10.7,int Partition(SqList 算法 10.6(b),算法Partition利用序列第一个对象作为基准，将整个序列划分为左右两个子序列。算法中执行了一个循环,只要是排序码小于基准对象排序码的对象都移到序列左侧,最后基准对象安放到位,函数返回其位置。,算法Quicksort是一个递归的算法,其递归树如图所示。,算法分析,快速排序的趟数取决于递归树的高度。如果每次划分对一个记录定位后,该记录的左侧子序列与右侧子序列的长度相同,则下 一步将是对两个长度减半的子序列进行排序,这是最理想的情况。在 n个元素的序列中,对一个记录定位所需时间为 O(n)。若设 t(n)是对 n 个元素的序列进行排序所需的时间,而且每次对一个记录正确定位后,正好把序列划分为长度相等的两个子序列,此时,总的计算时间为：,T(n)cn+2T(n/2)/c 是一个常数 cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+2T(n/8)=3cn+8T(n/8)cn log2n+nT(1)=O(n log2n)可以证明,函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明:就平均计算时间而言,快速排序是所有内排序方法中最好的一个。快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。,最大递归调用层次数与递归树的高度一致,理想情况为 log2(n+1)。因此，要求存储开销为 O(log2n)。在最坏的情况,即待排记录序列关键字有序（正序或逆序）时,其递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列。总的关键字比较次数将达,此时得到算法的最坏时间复杂度为O(n2)改进枢轴记录的选取：“三者取中”快速排序是一种不稳定的排序方法。,基本思想：每一趟在 n-i+1(i=1,n-1)个记录中选出关键字最小的记录,作为有序序列中的第 i 个记录。,8.4 选择排序（Selection Sort),选准了再做记录移动,简单选择排序是一种简单的排序方法,它的基本步骤是：在一组对象 rirn-1 中选择具有最小关键字的记录；若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调;在这组对象中剔除这个具有最小排序码的对象。在剩下的对象Vi+1Vn-1中重复执行第、步,直到剩余对象只有一个为止。,简单选择排序(Simple Selection Sort),简单选择排序的过程,最小者 25*无交换,直接选择排序的算法void SelectSort(SqList 算法 10.9,关键字比较次数 KCN 与记录的初始排列无关。设有 n 个记录,则第 i 趟选择具有最小关键字记录所需的比较次数总是 n-i 次。总的关键字比较次数为,记录的移动次数RMN与记录序列的初始排列有关。当初始序列为正序时，RMN取最小值“0”；最坏情况是每一趟都要进行交换，RMN取最大值为 3(n-1)。总的时间复杂度为O(n2)简单选择排序是一种不稳定的排序方法。,堆排序(Heap sort),堆(Heap)的定义：设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从 1开始连续编号。若满足 Ki K2i&Ki K2i+1 或 Ki K2i&Ki K2i+1,则称该关键字集合构成一个堆。前者称为小根（顶）堆，后者称为大根（顶）堆。,堆排序的步骤（以小根堆为例）1.根据初始的输入数据，形成初始堆；2.输出堆顶元素（最小记录）；3.对剩余元素做调整，形成新的堆；4.重复步骤2,3，直到剩余元素个数为零。,堆排序,49,25,25*,21,16,08,1,2,3,4,5,6,08,25,25*,16,21,49,1,3,6,5,4,2,49 25 21 25*16 08,08 25 21 25*16 49,交换 1号与 6 号元素,6号元素就位,初始大根堆,堆排序过程(大根堆）,25,25*,08,21,16,49,1,2,3,4,5,6,16,25*,08,25,21,49,1,3,6,5,4,2,25 25*21 08 16 49,16 25*21 08 25 49,交换 1 号与 5 号元素,5号元素就位,从 1号到 5 号 重新调整为大根堆,25*,16,08,21,25,49,1,2,3,4,5,6,08,16,25*,25,21,49,1,3,6,5,4,2,25*16 21 08 25 49,08 16 21 25*25 49,交换 1 号与 4 号元素,4 号元素就位,从 1 号到4 号 重新调整为大根堆,21,16,25*,08,25,49,1,2,3,4,5,6,08,16,25*,25,21,49,1,3,6,5,4,2,21 16 08 25*25 49,08 16 21 25*25 49,交换 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,16 08 21 25*25 49,08 16 21 25*25 49,交换 1号与 2 号元素,2 号元素就位,从 1 号到 2 号 重新调整为大根堆,两个关键问题：1.如何由一个无序序列建成一个堆?2.如何在输出堆顶元素后，调整剩余元素成为一个新的堆？,方法：自顶向下地“筛选”,堆的调整（问题2）,rc=38,s,j,s,j,s,void HeapAdjust(HeapType/插入 算法 10.10,大根堆的“筛选”算法,初始堆的建立（问题1）,“筛选”算法可以将一个左右子树已经是堆的二叉树调整为堆。如何由无序序列建初始堆？若序列所对应的完全二叉树的根结点的左右子树已经是堆，则用“筛选”算法可以将整个二叉树调整为堆。解决方法：可以按子树规模从小到大的顺序，从初始完全二叉树的底部向上逐步调整（筛选），直至整个二叉树为堆！,图示：初始大顶堆的建立过程,初始关键字集合,i=3局部调整后,void HeapSort(HeapType/将H.r1.I-1重新调整为大根堆 算法 10.11,堆的建立算法,堆排序的最坏时间复杂度为O(nlog2n)，优于快速排序的最坏时间复杂度O(n2)。算法的空间复杂度为O(1)。堆排序是一个不稳定的排序方法。（为什么？）,堆排序的算法分析,8.5 归并排序（Merging Sort),归并 将两个或两个以上的有序表合并成一个新的有序表。2-路归并(2-way merging)原始序列initList 中两个有序表 initListl initListm和initListm+1 initListn，它们可归并成一个有序表,存于另一记录序列mergedList的 l n 中。,08 21 25 25*49 62 72 93,16 37 54,left mid mid+1 right,initList,i j,08 16 21 25 25*37 49 54 62 72 93,left right,k,mergeList,设变量 i 和 j 是表initListl m和initList m+1 n的当前检测指针。k 是存放指针。当 i 和 j 都在两个表的表长内变化时,根据对应项的关键字的大小,依次把关键字小的记录排放到新表 k 所指位置中；当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。,2路归并排序算法,算法思想 假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列(归并项)，先做两两归并，得到 n/2 个长度为 2 的归并项(如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两归并，如此重复，最后得到一个长度为 n 的有序序列。,2-路归并算法void Merge(RcdType SR,RcdType/将剩余的SRj.n复制到TR 算法 10.12,void Msort(RcdType SR,RcdType/将TR2s.m和TR2m+1.t归并到TR1m.t 算法 10.13,递归形式的2-路归并排序算法,Void MergeSort(SqList 算法10.14,特点：形式简洁，效率很低,迭代（非递归）的归并排序算法,一趟归并排序的情形,设initList0到initListn-1中 n 个对象已经分为一些长度为 h 的归并项,将这些归并项两两归并,归并成长度为 2h 的归并项,结果放到mergedList 中。如果n不是2h的整数倍,则一趟归并到最后,可能遇到两种情形：剩下一个长度为h的归并项和另一个长度不足len的归并项,可用merge算法将它们归并成一个长度小于 2h的归并项。只剩下一个归并项，其长度小于或等于h,将它直接抄到mergedList 中。,时间复杂度为O(nlog2n)：做一趟两路归并排序,要调用n/(2*h)O(n/h)次merge；整个归并过程需进行log2n 趟,所以算法总的时间复杂度为O(nlog2n)。空间复杂度为O(n)归并排序占用附加存储较多,需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。归并排序是一个稳定的排序方法。,迭代的归并排序算法性能分析,各种排序方法的比较,作业：习题集 9.21(page 57)hash查找 习题集 10.34(page 65)-堆排序课后阅读：DSDEMO课件中的相关排序算法,作 业 12,数据库原理部分王珊、陈红，数据库系统原理教程，清华大学出版社，1998,
