2022年数据结构笔记.pdf

《2022年数据结构笔记.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构笔记.pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构笔记数据结构笔记基础 : 数据结构与算法（一）数据结构基本概念数据 (data):就是对客观事物的符号表示,在计算机科学中就是指所有能输入到计算机中并被计算机程序处理的符号总称数据元素 (data element): 就是数据的基本单位,在计算机中通常被当做一个整体进行考虑与处理数据对象 (data object): 性质相同的数据元素的集合,就是数据的一个子集数据结构 (data structure): 相互之间存在一种或多种特定关系的数据元素的集合4 类基本结构 :集合、线性结构、树形结构、图形(网状 )结构数据结构的形式定义为数据结构就是一个二元组Data Structure =

2、 (D,S),其中 D 就是数据元素的有限集 ,S就是 D 上关系的有限集数据结构定义中的“关系”描述的就是数据元素之间的逻辑关系,因此又称为数据的逻辑结构数据结构在计算机中的表示(映像 )称为物理结构 (存储结构 ) 计算机中表示信息的最小单位就是二进制中的一位,叫做位 (bit), 一到若干位组成一个位串表示一个数据元素,这个位串称为元素或结点数据结构之间关系在计算机中的表示有两种:顺序映像、非顺序映像,并由此得到两种存储结构:顺序存储、链式存储,前者运用相对位置表示数据元素间的逻辑结构,后者借助指针任何一个算法的设计取决于数据(逻辑 )结构 ,而实现依赖于存储结构数据类型就是一个值的集合

3、与定义在这个值集上的一组操作的总称数据类型分两种:原子类型、结构类型,前者不可分解 (例如 int、char、 float 、void ),后者结构类型由若干成分按某种结构组成,可分解 ,成分既可以就是非结构的也可以就是结构的(例:数组) 抽象数据类型 (Abstract Data Type ):就是指一个数学模型及定义在该模型上的一组操作(P8) 抽象数据类型格式如下: ADT 抽象数据类型名 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 24 页 - - - - - - - - - -

4、数据结构笔记数据对象 : 数据关系 : 数据操作 : ADT抽象数据类型名基本操作格式如下: 基本操作名 (参数表 ) 初始条件 : 操作结果 : 多形数据类型 (polymorphic data type): 就是指其值得成分不确定的数据类型(P9) 抽象数据类型可由固有数据类型来表示与实现（二）算法 ( 概念) 与算法分析 ( 时、空性能 ) 算法 (algorithm): 对特定问题求解步骤的一种描述算法 5 特性 :有穷、确定、可行、输入、输出1、有穷性 :算法必须在可接受的时间内执行有穷步后结束2、确定性 :每条指令必须要有确切含义,无二义性 ,并且只有唯一执行路径,即对相同的输入只

5、能得相同输出3、可行性 :算法中的操作都可通过已实现的基本运算执行有限次来完成4、输入 :一个算法有一到多个输入,并取自某个特定对象合集5、输出 :一个算法有一到多个输出,这些输出与输入有着某些特定关系的量算法设计要求 (好算法 ):正确性、可读性、健壮性、效率与低存储需求健壮性就是指对于规范要求以外的输入能够判断出这个输入不符合规范要求,并能有合理的处理方式。算法效率的度量: （1）事后统计 :程序运行结束后借助计算机内部计时功能,缺点一就是必须先运行依据算法编制的程序 ,二就是受限于计算机软硬件,导致掩盖了算法本身的优劣（2）事前分析估计: 精品资料 - - - 欢迎下载 - - - -

6、- - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 24 页 - - - - - - - - - - 数据结构笔记消耗时间影响因素:算法策略、问题规模、编程语言、编译程序产生的机器码质量、机器执行指令的速度撇开各种影响因素只考虑问题的规模(通常用整数量n 表示 ),记为问题规模的函数算法时间取决于控制结构(顺序 ,分支 ,循环 )与固有数据类型操作的综合效果书写格式 :T(n)= O(f(n) f(n) 为 n 的某个函数时间复杂度 :算法的渐近时间复杂度(asymptotic time complexity),它表示随问题规模的增大,算法执行

7、时间的增长率与f(n)的增长率相同以循环最深层原操作为度量基准频度 :该语句重复执行的次数算法的存储空间需求: 空间复杂度 (space complexity):算法所需存储空间度量,记作S(n)= O(f(n),其中 n 为问题规模的大小一、线性表（一）线性表基本概念线性表 (linear_list):n个数据元素的有限序列结构特点 :存在唯一的被称作“第一个”、“最后一个”的数据元素,且除了第一个以外每个元素都有唯一前驱,除最后一个以外都有唯一后继精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页

8、，共 24 页 - - - - - - - - - - 数据结构笔记在复杂线性表中存在:数据项 -记录 -文件 ,例如每个学生情况为一个记录,它由学号、性别、数据项组成,多个学生记录组成一个文件在形如 (a1, 、,ai-1,ai,ai+1, 、,an) 中,ai-1 领先于 ai,ai 领先于 ai+1, 且形成直接前驱元素,直接后继元素关系元素个数 n 定义为线性表长度,n=0 为空表相关操作算法见书(P20) （二）线性表顺序存储结构与链式存储结构(1) 线性表顺序表示与实现线性表顺序存储在一组连续的存储单元中,链式存储则不要求;顺序结构可以随机访问,链式结构可以无限扩容确定存储位置 (

9、计算公式 ): 第 i 个元素 :LOC(ai)= LOC(a1)+(i-1)*L L 就是偏移量 ,即每个元素占用存储单元第 ai+1 个元素 :LOC(ai+1)= LOC(ai)+L a1( 起始地址或基地址) C 语言下标从“ 0”开始 ,则表中第i 个元素就是L、elem i-1 当对线性表进行操作时,被操作元素后面的元素角标会相应变化(前移、后移 ),算法 (P24) (2) 线性表链式表示与实现特点 :用一组任意的存储单元存储线性表的数据元素(存储单元不一定连续) 结点存储数据元素及直接后继的存储位置信息,两个域 :数据域与指针域,指针域中存储的信息称为指针或链,仅含有一个指针域

10、故又称线性链表或单链表链表的插入 :先增加一条指针再修改原指针头指针指向第一个数据元素的存储位置,最后一个结点的指针为空(NULL) 链表表示方法及算法(P28) 单链表第一个结点前加一个头结点Head, 其数据域可为空也可存储一些附加信息(链长等 ) 假设 p 就是指向线性表中i 个元素 (ai) 的指针 ,则 p-next 就是指向i+1 个数据元素在单链表中 ,取得第 i 个元素必须从头指针开始寻找,因此单链表就是非随机的存储结构线性表指逻辑结构,从抽象数据层面来说顺序表与链表指物理存储结构精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 -

11、 - - - - - - - - -第 4 页，共 24 页 - - - - - - - - - - 数据结构笔记逻辑结构 :离散、线性、层次、网状应用见书算法二、栈与队列（一）栈的基本概念栈(stack) 就是限定仅在表尾进行插入或删除操作的线性表表尾为栈顶 ,表头为栈底 ,遵循后进先出原理(last in first on,LIFO),不含元素则为空栈操作 :在栈顶插入 (入栈 )与删除 (出栈),栈初始化、判空、取栈顶元素(算法 P45) （二）栈的顺序存储与链式存储顺序栈 ,即栈的顺序存储结构就是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素 ,同时附设指针top 指示栈顶元素在

12、顺序栈中的位置初始栈时不应限定栈的最大容量,基本做法就是先为栈分配一个基本容量,然后在应用过程中 ,不够用再逐段扩大(算法 P46) （三）递归栈与递归的实现:一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称为递归函数阶乘函数、 2 阶 Fibonacci 数列、 Ackerman函数、 3 阶 Hanoi 问题 (多阶呢？ )(P54) 函数调用函数执行过程笔记(P56)（四）队列队列先进先出 (first in first out,FIFO),队尾一端插入,队首一端删除元素(日常排队 ) 队列与栈均有八种基本操作(P59), 队列一般用链表实现,栈用顺序表实现双端队列 (限定

13、操作的队列)(P60) （五）栈与队列的应用链队列、循环队列(P60), 离散事件模拟 (银行接待工作(P65) （六）特殊矩阵的压缩存储如何存储矩阵的元,使矩阵的运算有效进行。高级语言常用二维数组存储阵元面对如高阶矩阵,多值相同矩阵与多零元素矩阵进行压缩存储节省空间精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 24 页 - - - - - - - - - - 数据结构笔记压缩存储 :为多个值相同的元只分配一个空间,对零元不分配值相同元素或零元素具有分布规律则称为特殊矩阵,反之为稀疏矩阵具体

14、应用与算法(P95) 三、树与二叉树（一）树的基本概念树就是非线性数据结构,以分支关系定义的层次结构树就是 n(n=0) 个结点的有限集详见 (P118), 基本术语 (P120) （二）二叉树1. 二叉树的定义及其主要特征: 二叉树就是每个结点最多有两个子树的树结构。通常子树被称作 “左子树” (left subtree)与“右子树” (right subtree) 。性质 : 1、2、3、满二叉树 : 完全二叉树 : 4、5、2. 二叉树的顺序存储结构与链式存储结构顺序存储 ,用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素 ,即将完全二叉树上编号为i 的结点依次存

15、储在如上定义的一位数组下标为i-1 的分量中。1 2 3 4 5 6 7 8 9 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 24 页 - - - - - - - - - - 数据结构笔记链式存储 ,每个结点中至少包含三个域,左指针 ,数据 ,右指针 ,称作“二叉链表”增加一个双亲指针域,则称作“三叉链表”详见 P126-127 3. 二叉树的遍历遍历二叉树 ,每个结点均被访问一次,且仅有一次。 在限定先左后右的访问序列后,有三种遍历方式 :先序 (DLR), 中序 (LDR), 后续(L

16、RD) P129 算法 6、1(波兰式 ) 层次遍历 ,无论那种遍历方式,对含 n 个结点的二叉树,时间复杂度都为O(n), 空间复杂度也为 O(n) 。4. 线索二叉树的基本概念与构造摘要 :对于 n 个结点的二叉树,在二叉链存储结构中有n+1(2n-(n-1)个空链域 ,利用这些空链域存放在某种遍历次序下该结点的前驱结点与后继结点的指针,这些指针称为线索概念 :加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree) 。构造方法 : （三）树与森林1. 树的存储结构链表结构 :1、双亲表示法2、孩子表示法3、孩子兄弟表示法详见 P135 2.

17、森林与二叉树转换左孩子右兄弟3. 树与森林的遍历先序、中序遍历,详见 P139 当以二叉链表做树的存储结构时,树的先序= 二叉树先序、树的后序= 二叉树中序（四）树与二叉树的应用1. 二叉排序树二叉排序树 (Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。定义 :二叉排序树或者就是一棵空树,或者就是具有下列性质的二叉树: 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 24 页 - - - - - - - - - - 数据结构笔记(1

18、)若左子树不空 ,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空 ,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树; (4)没有键值相等的节点。查找 : 步骤 :若根结点的关键字值等于查找的关键字,成功。否则 ,若小于根结点的关键字值,递归查左子树。若大于根结点的关键字值,递归查右子树。若子树为空 ,查找不成功。2. 平衡二叉树 (AVL) 定义:它或者就是一颗空树,或者具有以下性质的二叉树:它的左子树与右子树的深度之差 (平衡因子 )的绝对值不超过1,且它的左子树与右子树都就是一颗平衡二叉树。平衡因子 (bf): 结点的左子树的深度减去右子

19、树的深度,那么显然 -1=bf=1 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 24 页 - - - - - - - - - - 数据结构笔记图一 ,图二都就是BST, 但只有图一就是AVL tree 3. 哈夫曼 (Huffman) 树与哈夫曼编码哈夫曼树就是一类带权路径长度最短的树,又称最优树。路径与路径长度概念:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 ,路径上的分支数目称为路径长度。树的路径长度就是从树根到每一结点的路径长度之与。推广到一般情况,考虑带权结点 :

20、 结点的带权路径长度为从该结点到树根之间的路径长度与结点上的权值的乘积,树的带权路径长度为树中所有叶子结点的带权路径长度之与,记作 WPL= 带权路径长度WPL 最小的二叉树称为最优二叉树或哈夫曼树哈夫曼算法构造哈夫曼树(P145) 哈夫曼编码前缀编码 :设计长短不等的编码,任一字符的编码都不就是另一个字符的编码的前缀利用二叉树来设计前缀编码约定左分支表示字符“0”右分支表示字符“1”精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 24 页 - - - - - - - - - - 数据结构笔记

21、则从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。一般情况 ,当带有权值时 ,本质上就就是设计一棵哈夫曼树,得到二进制前缀编码=哈夫曼编码 - 算法详见 P147 四、图（一）图的基本概念图就是一种数据结构,加上一组基本操作,构成的一种抽象数据类型详见 (P156) 途中数据元素通常称为顶点,V 就是顶点的有穷非空集合;VR 就是两个顶点的关系集合,若属于 VR,则 表示从 v 到 w 的弧,称 v 为弧尾 (初始点 ),w 尾弧头 (终结点 ) 此时图就是有向图,若 属于 VR 必有 属于 VR,则以无序对 , 表示 v 与 w 的一条边 ,此时称图为无向图完全图有向

22、完全图边或弧很少 (e终点迪杰斯特拉算法: 3、拓扑排序由某个集合上的偏序得到该集合的全序偏序 :若集合 X 上的关系 R 就是自反的、反对称的与传递的,则称 R 就是集合X 上的偏序关系 ;设 R 就是集合上的偏序,如果对每个x,y 属于 X 必有 xRy 或 yRx, 则称 R 就是集合 X 上的全序关系。详见 (P180) 4、关键路径 (最长路径 )(P183) 五、查找（一）查找的基本概念在一些 (有序的 /无序的 )数据元素中 ,通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。也就就是根据给定的某个值,在查找表中确定一个关键字等于给定值的记录或数据元素。（二）顺序查找法

23、精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 24 页 - - - - - - - - - - 数据结构笔记1. 顺序查找 :核心 :从数据的第一个元素开始,依次比较 ,直到找到目标数据或查找失败。1、从表中的第一个元素开始,依次与关键字比较。2、若某个元素匹配关键字,则 查找成功。3、若查找到最后一个元素还未匹配关键字,则 查找失败。2. 时间复杂度 :顺序查找平均关键字匹配次数为表长的一半,其时间复杂度为O(n) 。3、顺序查找的评估:顺序查找的优点就是对表无要求,插入数据可在O(1)

24、 内完成。缺点就是时间复杂度较大,数据规模较大时,效率较低。（三）折半查找法算法要求 :折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。查找过程 :首先 ,假设表中元素就是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等 ,则查找成功否则 利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字 ,则进一步查找前一子表,否则进一步查找后一子表。重复 以上过程 ,直到找到满足条件的记录,使查找成功 ,或直到子表不存在为止,此时查找不成功。（四）散列 (Hash) 表哈希表定义 :就是根据关键码值(Key value) 而直接进行访问的

25、数据结构。也就就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数 ,存放记录的数组叫做散列表。给定表 M, 存在函数 f(key), 对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表 M 为哈希 (Hash) 表,函数 f(key) 为哈希 (Hash) 函数。基本概念 :若关键字为k,则其值存放在f(k) 的存储位置上。 由此 ,不需比较便可直接取得所查记录。称这个对应关系f 为散列函数 ,按这个思想建立的表为散列表。对不同的关键字可能得到同一散列地址,即 k1k2,而 f(k1)=f(k2),这种现象称为冲突

26、(英语:Collision) 。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数f(k) 与处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间 )上,并以关键字在地址集中的“ 像” 作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 24 页 - - - - - - - - - - 数据结构笔记若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一

27、个地址的概率就是相等的 ,则称此类散列函数为均匀散列函数(Uniform Hash function),这就就是使关键字经过散列函数得到一个“ 随机的地址 ”,从而减少冲突。（五）字符串模式匹配子串的定位操作就是要在主串S 中找出一个与子串T 相同的子串 ,通常把主串S 称为目标,把子串 T 称为模式 ,把从目标 S 中查找模式为T 的子串的过程称为“ 模式匹配 ” 。1. Brute-Force算法的设计思想Brute-Force就是普通的模式匹配算法。将主串 S 的第 1 个字符与模式T 的第 1 个字符比较 ,若相等 ,继续逐个比较后续字符;若不等 ,从主串的下一字符起,重新与模式的第一

28、个字符比较 ,直到主串的一个连续子串字符序列与模式相等,返回值为 S 中与 T 匹配的子序列第一个字符的序号,即匹配成功 ;否则,匹配失败 ,返回值0。2. Brute-Force算法的特点 : 每次遇到匹配不成功的情况,指针 i都要移到本次匹配的开始位置的下一位,称这样的指针移动为回溯。指针的回溯越多,简单模式匹配的执行次数越多Brute-Force匹配算法的最坏时间复杂度为O(n*m), 一般情况下BF 算法的时间复杂度为 O(n+m) 3、KMP 算法的改进每当一趟匹配过程中出现字符比较不等时,不需回溯指针i,而就是利用已经得到的“ 部分匹配 ” 的结果将模式向右“ 滑动 ” 尽可能远的

29、一段距离后,继续比较KMP 算法的时间复杂度可以达到O(m+n) 4、KMP 算法的设计思想假设以指针i 与 j 分别指示主串与模式中正待比较的字符,令 i 的初值为 0,j 的初值为 0 若在匹配过程中,Si=Pj, 则 i 与 j 分别增 1,否则 i 不变 ,而 j 退到 nextj 的位置再比较,若相等,则指针各自增1,否则 j 再退到下一个next 值的位置 ,依次类推若令 nextj=k, 则 nextj 表明当模式中第j 个字符与主串中相应字符失配时,在模式中需重新与主串中该字符进行比较的字符的位置模式串的 next 函数定义为精品资料 - - - 欢迎下载 - - - - -

30、- - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 24 页 - - - - - - - - - - 数据结构笔记（六）查找算法的分析及应用六、排序（一）排序的基本概念将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。分内部排序与外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。 反之 ,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程就是一个逐步扩大记录的有序序列长度的过程。（二）插入排序直接插入排序基本思想就是每一步将一个待排序的记录,插入到

31、前面已经排好序的有序序列中去 ,直到插完所有元素为止。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 24 页 - - - - - - - - - - 数据结构笔记（三）气泡排序冒泡排序的基本思想就是,对相邻的元素进行两两比较,顺序相反则进行交换,这样 ,每一趟会将最小或最大的元素“ 浮” 到顶端 ,最终达到完全有序精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 24 页 - - - -

32、- - - - - - 数据结构笔记（四）简单选择排序简单选择排序就是最简单直观的一种算法,基本思想为每一趟从待排序的数据元素中选择最小 (或最大 )的一个元素作为首元素,直到所有元素排完为止,简单选择排序就是不稳定排序。在算法实现时 ,每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小 ,交换就是个比较耗时的操作。其实我们很容易发现,在还未完全确定当前最小元素之前,这些交换都就是无意义的。我们可以通过设置一个变量min,每一次比较仅存储较小元素的数组下标 ,当轮循环结束之后,那这个变量存储的就就是当前最小元素的下标,此时再执行交换操作即可。代码实现很简单,一起来瞧下。（五）希

33、尔排序希尔排序就是基于插入排序的,首先回顾一下插入排序,假设插入就是从左向右执行的,待插入元素的左边就是有序的,且假如待插入元素比左边的都小,就需要挪动左边的所有元素,如下图所示 : 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 16 页，共 24 页 - - - - - - - - - - 数据结构笔记精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 17 页，共 24 页 - - - - - - - - - -

34、数据结构笔记精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 18 页，共 24 页 - - - - - - - - - - 数据结构笔记相比简单插入排序,大间隔地做插入排序有两个好处: 一、大间隔直接导致需要挪动的数据稀少,且数据挪动的效率高,图 5 中一次挪动可以跨越 40 个位置 ; 二、经过前一步大间隔的插入排序后,整个数组从整体上粗略地瞧已经有了明显的顺序,后一步小间隔的插入排序时,一部分操作就是不需要挪动数据的,再次减少了挪动数据的次数。间隔的序列 :间隔的常用序列,通过递归表示 :h=3*h+

35、1 。(1,4,13,40,121 、 ) 希尔排序的效率: “没有理论上分析希尔排序的效率的结论,各种基于实验的评估,估计它的时间级从 O(N(3/2)到 O(N(7/6)”-1。（六）快速排序快速排序算法的策略就是这样的:首先把数组用某个值分为两个子数组,且称这个值为分组值,一个子数组中的元素均小于分组值,另一子数组则均大于等于分组值,这里的子组内并不排序;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 19 页，共 24 页 - - - - - - - - - - 数据结构笔记然后 ,再分别对两个子

36、组进行再分组,重复递归这个过程,直到最后每两个元素作为一组进行再分组 ,整个数组就排好序了。分组过程具体如下:同时从左往右与从右往左扫描数组,记扫描标记位为LP与 RP。在 LP一边 ,若发现元素小于分组值则跳过(即向右移动一位检查下一个元素),否则等待RP 的扫描;RP 若发现元素大于等于分组值跳过,直到找到小于分组值的元素,然后 LP 与 RP 位置的元素交换 ,重复这个过程 ,直到 LP与 RP相遇。如图 7,8 所示 ,以 11 号元素为分组值,LP 停在 0 号位置 ,RP 跳过 10 号,停在图 7 中的9 号位置 (粉色柱 ), 然后 0 号与 9 号交换 ,后续重复这个过程。精

37、品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 20 页，共 24 页 - - - - - - - - - - 数据结构笔记分组值的选择,可以想见 ,理想的分组值应该就是待分组元素的中值,这样分组后子组在数量少几乎就是一半对一半,不过找中值无疑增加了算法的工作量。图7 中采用了更简单的方式 ,直接选数组最右边的元素为分组值,分组结束后 ,再把这个值交换到LP与 RP相遇的位置 ,假如初始数组就是从大到小排序的,这种情况下 ,选择最右边的元素作为分组值,其区分度就很差了。更好用的方法就是所谓的取首尾中三项数据

38、的中值或者平均值。通过对算法过程的描述可知,其时间复杂度应该为:O(N*logN), 比简单排序与希尔排序都要快。（七）堆排序堆排序就是利用堆这种数据结构而设计的一种排序算法,堆排序就是一种选择排序,它的最坏 ,最好 ,平均时间复杂度均为O(nlogn),它也就是不稳定排序。首先简单了解下堆结构。堆就是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆 ;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图: 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 21

39、 页，共 24 页 - - - - - - - - - - 数据结构笔记同时 ,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就就是下面这个样子该数组从逻辑上讲就就是一个堆结构,我们用简单的公式来描述一下堆的定义就就是: 大顶堆 :arri = arr2i+1 & arri = arr2i+2 小顶堆 :arri = arr2i+1 & arri = arr2i+2 堆排序的基本思想就是:将待排序序列构造成一个大顶堆,此时 ,整个序列的最大值就就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1 个元素重新构造成一个堆,这样会得到n 个元素的次小值。如此反复

40、执行,便能得到一个有序序列了（八）基数排序基数排序 (Radix Sort)基本思想就是 :将整数按位数切割成不同的数字,然后按每个位数分别比较。具体做法就是 :将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后 ,从最低位开始 ,依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 22 页，共 24 页 - - - - - - - - - - 数据结构笔记在上图中 ,首先将所有待比较树脂统一为统一位数长度,

41、接着从最低位开始,依次进行排序。1、 按照个位数进行排序。2、 按照十位数进行排序。3、 按照百位数进行排序。排序后 ,数列就变成了一个有序序列。（九）各种内部排序算法的比较比较排序与非比较排序常见的排序算法都就是比较排序,非比较排序包括计数排序、桶排序与基数排序,非比较排序对数据有要求,因为数据本身包含了定位特征,所有才能不通过比较来确定元素的位置。比较排序的时间复杂度通常为O(n2)或者 O(nlogn),比较排序的时间复杂度下界就就是 O(nlogn),而非比较排序的时间复杂度可以达到O(n),但就是都需要额外的空间开销。排序的稳定性与复杂度不稳定 : 选择排序 (selection s

42、ort) O(n2) 快速排序 (quicksort) O(nlogn) 平均时间 , O(n2) 最坏情况 ; 对于大的、乱序串列一般认为就是最快的已知排序堆排序(heapsort) O(nlogn) 希尔排序(shell sort) O(nlogn) 基数排序 (radix sort) O(nk); 需要O(n) 额外存储空间(K为特征个数 ) 稳定: 插入排序 (insertion sort) O(n2) 冒泡排序 (bubble sort) O(n2) 归并排序(merge sort) O(n log n); 需要 O(n) 额外存储空间二叉树排序 (Binary tree sort)

43、 O(nlogn); 需要 O(n) 额外存储空间精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 23 页，共 24 页 - - - - - - - - - - 数据结构笔记计数排序(counting sort) O(n+k); 需要O(n+k) 额外存储空间,k 为序列中Max-Min+1 桶排序(bucket sort) O(n); 需要O(k) 额外存储空间（十）排序算法的应用精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 24 页，共 24 页 - - - - - - - - - -