《内部排序》PPT课件

Chapter10排序,排序的基本概念直接插入排序起泡排序简单选择排序快速排序堆排序,6.1基本概念,排序,排序在计算机程序设计中有着非常重要的地位，许多具体应用要求对数据进行排序，而许多复杂的算法也要求以排序为基础。,排序,排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据表(datalist):它是待排序数据对象的有限集合。主关键字(key):数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据，称为关键字。也称为排序码。,排序,有关排序的几个基本问题稳定与不稳定内部排序与外部排序（本章只关注内部排序）性能的衡量,排序方法的分类,按照排序思想插入排序交换排序选择排序归并排序基数排序按照时间复杂度简单排序先进排序其他,6.2直接插入排序,直接插入排序,基本思想：如果要向一个已经排序的顺序表中插入元素且保持表的有序性，则只需先依次比较，找到该元素的位置，然后移动元素进行插入即可。时间复杂度是O(n).基于这一思想，如果要对一个表进行排序，则可以将表看作两个部分，前N个元素已经排好序，再将第N+1个元素插入到前N个元素中。从N=0开始重复这个过程，直到N=L。,直接插入排序,直接插入排序,直接插入排序,直接插入排序的算法typedefintSortData;voidInsertSort(SortDataV,intn)/按非递减顺序对表进行排序SortDatatemp;inti,j;for(i=1;i0;j-)/从后向前顺序比较if(tempVj)/逆序Swap(Vj-1,Vj);/交换exchange=1;/标志置为1,有交换i+;,起泡排序,扩展阅读：双冒泡排序。,链表上的起泡排序,思考：在链表上进行起泡排序，相比顺序表有哪些不同？1：从前向后的过程，需要借助两个指针来完成。2：需要用另外一个指针来指示已经被移动到最后的若干个元素。3：交换的过程有不同做法。实现起来比较繁琐，建议课下练习。,6.4简单选择排序,简单选择排序,在一组数据中选择具有最小排序关键字的一个。若它不是这组数据中的第一个,则将它与这组数据中的第一个对调;在剩下的N-1个数据中重复执行第、步,直到完成。,简单选择排序,简单选择排序的排序过程,简单选择排序,简单选择排序的基本算法typedefintSortData;voidSelectSort(SortDataV,intn)for(inti=0;in-1;i+)intk=i;/选择具有最小排序码的对象for(intj=i+1;jk1且kk2），则不进行操作，退出循环。如果不满足，则将其与叶子节点中较大的一个进行交换，并继续执行循环。,堆的建立,以一个小顶堆的建立过程为例,堆的建立,以一个小顶堆的建立过程为例,注意这一次调整有点麻烦,堆的建立,以一个小顶堆的建立过程为例,堆的建立,以一个小顶堆的建立过程为例,堆的建立,至此，小顶堆的建立就完成了。,堆排序,那么如何使用“堆”这种数据结构来排序呢？只需要如下的过程：将堆中最后一个节点与根节点交换，并且将调整之后的最后一个节点输出出来，就得到了目前堆中最小（最大）的元素。将剩余的N-1个元素重新调整成堆（这一步只需要针对根节点进行调整就可以）。重复以上过程直到全部元素都被输出了。,堆排序,以利用大顶堆进行排序的过程为例：,交换8与49，并输出49,堆排序,以利用大顶堆进行排序的过程为例：,重新调整为大顶堆，然后交换25与16，并输出25,堆排序,以利用大顶堆进行排序的过程为例：,重新调整为大顶堆，然后交换25与8，并输出25,堆排序,以利用大顶堆进行排序的过程为例：,重新调整为大顶堆，然后交换21与8，并输出21,堆排序,以利用大顶堆进行排序的过程为例：,重新调整为大顶堆，然后交换8与16，并输出16,堆排序,以利用大顶堆进行排序的过程为例：,现在堆中只剩下一个元素了，输出，完成排序。,堆排序,堆排序的过程很繁琐，这导致它在数据量很小的情况下性能不佳。但是它的时间复杂度是nlogn级别的，特别是即使在最坏情况下，它的时间复杂度仍然保持nlogn，这是它相对快速排序最大的优势。,堆排序的程序实现,堆有一个很好的性质（思考：哪一点？），利用这一点，可以在一个顺序结构上实现堆排序。“完全二叉树”这一性质还决定了在顺序存储时，如果从顺序表的