数据结构-外部排序
- 格式:ppt
- 大小:549.50 KB
- 文档页数:35
【数据结构】常见排序算法复杂度相关概念1、稳定排序(stable sort)和⾮稳定排序稳定排序是指所有相等的数经过某种排序算法操作后仍然能保持它们在排序之前的相对次序。
反之就是⾮稳定排序。
2、内排序(internal sorting)和外排序(external sorting)在排序过程中,所有需要排序的数都在内存,并在内存中调整它们的存储顺序,称为内排序;在排序过程中,只有部分数被调⼊内存,并借助内存调整数在外存中的存放顺序排序⽅法称为外排序。
排序算法【冒泡排序】(Bubble Sort)冒泡排序⽅法是最简单的排序⽅法。
这种⽅法的基本思想是,将待排序的元素看作是竖着排列的“⽓泡”,较⼩的元素⽐较轻,从⽽要往上浮。
在冒泡排序算法中我们要对这个“⽓泡”序列处理若⼲遍。
所谓⼀遍处理,就是⾃底向上检查⼀遍这个序列,并时刻注意两个相邻的元素的顺序是否正确。
如果发现两个相邻元素的顺序不对,即“轻”的元素在下⾯,就交换它们的位置。
显然,处理⼀遍之后,“最轻”的元素就浮到了最⾼位置;处理⼆遍之后,“次轻”的元素就浮到了次⾼位置。
在作第⼆遍处理时,由于最⾼位置上的元素已是“最轻”元素,所以不必检查。
⼀般地,第i遍处理时,不必检查第i⾼位置以上的元素,因为经过前⾯i-1遍的处理,它们已正确地排好序。
冒泡排序是稳定的。
算法时间复杂度是O(n2)。
【选择排序】(Selection Sort)选择排序的基本思想是对待排序的记录序列进⾏n-1遍的处理,第 i 遍处理是将[i..n]中最⼩者与位置 i 交换位置。
这样,经过 i 遍处理之后,前 i 个记录的位置已经是正确的了。
选择排序是不稳定的。
算法复杂度是O(n2 )。
【插⼊排序】(Insertion Sort)插⼊排序的基本思想是,经过i-1遍处理后,L[1..i-1]⼰排好序。
第i遍处理仅将L插⼊L[1..i-1]的适当位置,使得L[1..i]⼜是排好序的序列。
要达到这个⽬的,我们可以⽤顺序⽐较的⽅法。
数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科.数据: 所有能输入到计算机中并被计算机程序处理的符号的总称.数据元素: 在计算机上程序中通常作为一个整体进行考虑和处理.数据对象: 是性质相同的数据元素的集合,是数据的一个子集.数据类型: 一个值的集合和定义在这个值集上的一组操作的总称.线性表: 最常用却最简单的一种数据结构.栈:限定仅在表尾进行插入或删除操作的线性表. 栈顶:线性表尾端(表尾端)栈底:线性表头端(表头端)空栈:不含元素的空表. 队列:一种先进先出的线性表.队尾:在队列中,允许插入的一端.队头:在队列中.允许删除的一端.根的结点:在任意一棵非空树中,有且仅有一个特定的.结点的度:结点拥有的子树数.叶子: 度为0的结点.树的度: 树内各结点的度的最大值.非终端结点:度不为零的结点.孩子:结点的子树的根.双亲:该结点称为孩子的双亲.兄弟:同一个双亲的孩子之间.堂兄弟:双亲在同一层的结点.祖先:从根到该结点所经分支上的所有结点.孙子:以某结点为根的子树中的任一结点都称为该结点的孙子.树的深度:树中结点的最大层次.结点的层次:从根开始定义起,根为第一层,根的孩子为第二层.有序树:如果将树中结点的各子树看成从左到右是有次序的,就.....(即不能互换).无序树:(见有序树),否则称为无序树.森林:是m棵互不相交的树的集合.二叉树:是结点的有限集合,它可以为空,也可以是由一根结点和称为根的左右子树的两棵子树组成.满二叉树:一棵深度为k具有2k-1(应该是2的k次方再减1)结点的二叉树.完全二叉树:深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时.图:是一种较线性表和树更为复杂的数据结构.有向图/无向图:设VR是两个顶点之间的关系的集合,若<v,w>∈VR,则<v,w>表示从v到w的一条弧,此时的图称为有向图,/若<v,w>∈VR必有<w,v>∈VR,即VR是对称的,表示v和w之间的一条边,此时的图称为无向图.子图:假设有两个图G=(V,{E})和G'=(V',{E'}),如果V'包含于V且E'包含于E,则称G'为G的子图.完全图:有n(n-1)/2条边的无向图.邻接结点:孤立点:孤点的度:入度:对于有向图,以某顶点为弧头的弧的数目为该顶点的入度出度:以某顶点为弧尾的弧的数目为该顶点的出度路径:从树中一个结点到另一个结点之间的分支就构成这两个结点之间的路径路径长度:路径上经过的边或弧的数目叫路径长度回路:若一条路径上开始点和终止点相同则称此路径为回路。
第11章 外部排序一、选择题1.下列排序算法中,其中()是稳定的。
A.堆排序,起泡排序B.快速排序,堆排序C.直接选择排序,归并排序D.归并排序,起泡排序【答案】D2.若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是()。
A.快速排序B.堆排序C.归并排序D.直接插入排序【答案】C【解析】稳定排序有:插入排序、起泡排序、归并排序、基数排序。
不稳定排序有:快速排序、堆排序、shell排序。
时间复杂度平均为O(nlog2n)的有:归并排序、堆排序、shell排序、快速排序。
3.在下面的排序方法中,辅助空间为O(n)的是()。
A.希尔排序B.堆排序C.选择排序D.归并排序【答案】D4.下列排序算法中,占用辅助空间最多的是()。
A.归并排序B.快速排序C.希尔排序D.堆排序【解析】归并排序的辅助空间为O(n),快速排序所占用的辅助空间为O(logn),堆排序所占用的辅助空间为O(1)。
5.将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是()。
A.N B.2N-1 C.2N D.N-1【答案】A【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。
最简单的归并是直接将两个有序的子表合并成一个有序的表。
归并排序最好情况下的复杂度为O(n)。
6.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为()排序法。
A.插入B.选择C.希尔D.二路归并【答案】A【解析】解此题需要熟知各种排序方法的基本思想。
插入排序的基本思想是:假设待排序的记录存放在数组R[0..n-1]中,排序过程的某一中间时刻,R被划分成两个子区间R[0..i-1]和R[i..n-1],其中:前一个子区间是已排好序的有序区,后一个子区间则是当前未排序的部分,不妨称其为无序区。
将当前无序区的第1个记录R[i]插入到有序区R[0..i-1]中适当的位置上。