网站建设邮,如何做网站推广 求指点,深圳产品设计招聘信息,临漳seo整站排名数据结构考题1.4
更新了时间复杂度理论和计算方法#xff08;简单快速#xff09;
1.基本概念
范围#xff1a;数据项(最小单位)数据元素(基本单位)数据对象(性质相同的数据元素集合) 举例#xff1a;数据对象#xff1a;学生群体#xff1b;数据元素#xf…数据结构考题1.4
更新了时间复杂度理论和计算方法简单快速
1.基本概念
范围数据项(最小单位)数据元素(基本单位)数据对象(性质相同的数据元素集合) 举例数据对象学生群体数据元素某个学生数据项这个学生的姓名、年龄、年级等 数据结构存在“关系”的数据元素集合包括物理结构与逻辑结构 逻辑结构与数据存储无关独立于计算机。有四个“集合、线性、树、图”结构分为线性结构和非线性 线性线性表、队列和栈、字符串、数组和广义表 非线性数和二叉树、有向图和无向图 存储结构要存储数据和逻辑关系分为顺序存储结构和链式存储结构 顺序存储结构存储地址相连接的整块存储存储密度高但插入删除运算效率低 链式存储结构地址不一定连续但是需要存储指针指向与之相关的结点存储密度顺序存储100%插入删除效率高 抽象数据类型用户定义的、表示应用问题的数学模型以及定义在这个模型上的一组操作的总成。包括数据对象、数据对象的关系、对数据对象的操作 算法五大特性有穷性、可行性、确定性、输入、输出 算法评价四个标准正确性、可读性、健壮性、高效性(低时间空间复杂度) 算法设计五大要求正确性、可读性、健壮性、零个以上的输入、一个以上的输出 算法分析的目的分析算法的效率以求改进 Extra-时间复杂度计算方法 引入时间复杂度主定律 设T[n]为问题规模f(n)为n的函数 T[n] a*T[n/b] f(n)不可直接求出T(n)与f(n)的关系 令k logb(a)b为底a为真数
f(n) O(nk): T(n) O(nk)f(n) O(nk): T(n) O(nk * logn)f(n) O(nk): T(n) O(f(n))
这里的,,是指n的幂即f(n)中幂最大的n和O(nk)的比较 若不是a*T(n/b)的形式为T(n-1)型 可求出T(n)与f(n)关系式 用高中学的等比数列求递推式的方式
例题
hanio问题T(n) 2T(n-1) 1其中T(1) 1 类型2 2T(n-1) 22T(n-2) 21 22T(n-2) 23T(n-3) 22 … 2n-1T(2) 2nT(1) 2n-1 求和得 T(n) 2n 2n - 1 O(n) 2nT(n) 2*T(n/2) n/2 类型2 k log2(2) 1 f(n) O(nk): T(n) O(nlogn)
2. 线性表
简述线性表元素间的关系是一对一特点是存在唯一的“第一个”和“最后一个”元素除第一个的元素都有唯一前驱除最后一个的元素都有唯一后继
2.1. 顺序线性表
用一组连续的地址存储线性表的数据元素特点是逻辑上连续的元素在物理结构也相邻
// 循序表
typedef struct
{DataType *sqlist;int length;
}SqList;查找第i个元素对比i次查表ASL(1n)/2 插入到第i个元素前移动n-i1次插入ASLn/2 删除第i个元素移动n-i次ASL(n-1)/2
2.2. 链表
单链表 用一组任意的存储单元存储为了表示元素与前驱后继的关系用指针域表示其地址
// 单链表
typedef struct Node
{DataType data;struct Node *next;
}Node *LinkedList;
// 一般建立单链表都会设立一个头结点查找
pL-next;
while(p)
{// 遍历链表结点用p表示pp-next;
}插入
// 头插法把s插入p结点后
Node *s (*Node)malloc(sizeof(Node))
s-next p-next;
p-next s;删除
// 删除p的后继单链表中只能删后继所以记得保存一个前驱结点pre
s p-next;
p-next s-next;
free(s);建立
void createList(LinkedList L, DataType array[], int length)
// 头插法
pL
for (i0; ilength; i)
{Node* s (*Node)malloc(sizeof(Node))s-dataarray[i];s-next p-next;p-next s;
}
// 尾插法
rL;
for (i0; ilength; i)
{Node* s (*Node)malloc(sizeof(Node))s-dataarray[i];s-next NULL;r-next s;rs;
}循环链表 与单链表的区别是最后一个元素的next指向L(头结点) 判空区别单链表L-next NULL; 循环链表L-next L; 应用两个设立尾结点的循环的合并 A、B为两个循环链表的尾结点。
pB-next-next;
B-nextA-next;
A-nextp;双向链表 在循环链表的基础上每个结点增加前驱指针 考的很少
2.3. 应用
有序链表的合并
void combine(List a, List b, List c) // a和b合并到c链表且不占用新内存空间
{p1a-next, p2b-next;ca; // 让c用a的头结点pcc;while (p1 p2){// 选择a和b的结点中小的一个插入c表后面if (p1-data p2-data) {pc-nextp1;pcp1;p1p1-next;}else{pc-nextp2;pcp2;p2p2-next;}}if (!p1) pc-nextp2;if (!p2) pc-nextp1;free(b);
}链表原地反向
void reverse_list(List L)
{ // 同时记录三个指针pre, p, pNext每次先保存pNext把p指向prepL-next; preL;while (p){pNextp-next;p-nextpre;prep;ppNext;}
}持续更新
3. 栈和队列
栈和队列都是操作受限的线性表只能在表的两端进行操作栈只能在一端操作受容量限制虽可以重新分配空间但工作量较大
3.1. 顺序栈
用顺序表实现栈有两个指针base和topbase指向栈底元素top指向栈顶的下一个
typedef struct
{SDataType *base; // 栈底指针若NULL则栈不存在SDataType *top; // 栈顶指针初始时topbasetopbase: 栈空int stack_size;
}SqStack// 创建顺序栈
bool create_stack(SqStack s)
{s.base (SDataType*)malloc(MAX_SIZE * sizeof(SDataType));if (!s.base) return false;s.tops.base;s.stack_size MAX_SIZE;return true;
}入栈
bool push(SqStack s, SDataType e)
{if (s.top-s.bases.stack_size) return false; // 满栈*s.top e;return true;
}出栈
bool pop(SqStack s, SDataType x)
{if (s.tops.base) return false; // 栈空x *--s.top;return true;
}取顶
bool top(SqStack s, SDataType x)
{if (s.tops.base) return false; // 栈空x *(s.top-1);return true;
}3.2. 链栈
用链表形式实现栈
typedef StackNode
{DataType data;struct StackNode *next;
}StackNode, *LinkStack;void initStack(LinkStack s) // 初始化置空指针
{sNULL;
}入栈
bool push(LinkStack s, DataType e) // 插入后部并栈顶指针后移
{StackNode *p (*StackNode)malloc(sizeof(StackNode));if (!p) return false; // 分配空间失败p-datae;p-nextssp;return true;
}出栈
bool pop(LinkStack s, DataType x)
{if (sNULL) return false;StackNode* qs; xq-data;ss-next;free(q);return true;
}3.3. 栈的应用
n个元素的出栈顺序有几种 我们设F函数为解则当n0,1,2,3时F(0)F(1)1, F(2)2, F(3)5 F(n)C(2n, n) / (n 1) C(2n, n) - C(2n, n-1) [n个结点的二叉树有几种] 数值转换
// 十进制转八进制
void conversion()
{initStack(s);scanf(%d, n);while(n){push(s, n%8); // 可转为任意(10以下)进制n/8;}while (!empty(s)){pop(s, e);printf(%d, e);}
}括号检测
bool valid(char str[], int length)
{bool flagtrue;for (i0; ilength; i){char cstr[i];switch(c){case [||(: push(s, c); break;case ): top(s, e); if (!empty(s) e() pop(s, e);else flagfalse; break;case ]: top(s, e); if (!empty(s) e[) pop(s, e);else flagfalse; break;}if (!flag) break;}if (!empty(s) flag) return true;else return false;
}表达式求值尚不知考与否 递归问题与非递归 递归会占用空间递归n次空间复杂度O(n) 递归函数调用次数内部次数外部次数(通常1次外调)
// 求斐波那契数列
int feb(int n) // 递归
{if (n1 || n2) return 1;else return feb(n-1) feb(n-2);
}int feb(int n) // 循环消除递归
{if (n1 || n2) return 1;t11; t22;for (i3; in; i){t3t1t2;t1t2; t2t3;}return t3;
}3.4 队列
一般顺序队列会出现“假溢出”所以顺序表用循环队列 循环队列
typedef struct
{QDataType *base; // 初始化分配空间int front; // 队首元素int rear; // 队尾的下一个元素
}SqQueue;bool InitQueue(SqQueue q)
{q.base(*QDataType)malloc(MAX_SIZE * sizeof(QDataType));if (!q.base) return false;q.front q.rear 0;return true;
}判空rearfront 判满(rear1) % MAX_SIZE front 队列长度(rear - front MAX_SIZE) % MAX_SIZE 入队
bool EnQueue(SqQueue q, QDataType e)
{if ((q.rear1) % MAX_SIZE q.front) return false;q.base[q.rear] e;q.rear (q.rear1) % MAX_SIZE;return true;
}出队
bool DeQueue(SqQueue q, QDataType x)
{if (q.rear q.front) return false;x q.base[q.front];q.front (q.front 1) % MAX_SIZE;return true;
}缺点和所有顺序表一样固定长度修改成本大 链队
typedef struct QNode
{DataType data;struct QNode *next;
}QNode, *QPtr;
typedef struct
{QPtr front;QPtr rear;
}LinkQueue;bool InitQueue(LinkQueue q) // 建立头指针的链队
{p(*QNode)malloc(sizeof(QNode));if (!p) return false;p-next NULL;q.front q.rear p;return true;
}入队
bool EnQueue(LinkQueue q, DataType d)
{p (*QNode)malloc(sizeof(QNode));if (!p) return false;p-data d;p-next NULL;q.rear-next p;q.rear p;return true;
}出队
bool DeQueue(LinkQueue q, DataType d)
{if (q.rear q.front) return false;p q.front-next;d p-data;q.front-next p-next;if (p q.rear) q.rear q.front; // 最后一个元素出队后要手动把rearfrontfree(p);return true;
}4.串、数组和广义表
typedef struct
{char *str;int length;
}String;4.1 模式匹配算法
KMP next数组计算方法(教材的值)
s串第0个字符的next[0]0对于第i个字符(0in)next[i]str(0到i-1的字串)最长前后缀重合部分 1 例Sabaabcac next[0, 1, 1, 2, 2, 3, 1, 2]此next值适用于第一个字符元素下标为1的字符串教材是从1开始S[0]表示字符串长度
// 更适合通用的方法下标从0开始即next值为教材的 -1
void get_next(String S, int next[])
{i0; j-1;next[0]-1;while (iS.length){if (j -1 || S.str[i] S.str[j]){i; j; next[i] j; }else j next[j]; }
}int kmp(String T, String S, int next[])
{i0; j-1;while (iT.length jS.length){if (j-1 || T.str[i] S.str[j]){i; j;}else j next[j];}if (j S.length) return i-j; // S子串在T的匹配位置else return -1; // 匹配失败
}4.2 数组和矩阵
三角矩阵 sa[k]和mat[i][j]的关系是(下标均从0开始) 上三角(i j) k 从0行加到i-1行, n(n-1)…(n-i1) (j - i) (2n - i 1)i / 2 (j - i) 下三角(j i) k (123…i) j i(i 1) / 2 j
对称矩阵的压缩 mat[i][j] mat[j][i]下标从0开始若从1开始则i i 1, j j 1 和三角矩阵差不多一般以行为主序存储在下三角 (i j) k i (i 1) / 2 j (i j) k j (j 1) / 2 i
4.3 广义表
LS (a1, a2, …, an) 取表头getHead(LS) a1只取头部元素可以是原子也可以是子表 取表尾getTail(LS) (a2, …, an)一定要带括号一定是子表 L (a, b); getTail(L) (b); 表长原子和子表个数之和 表深括弧重度也等于最大子表深度1若无子表则为1递归
5. 树和二叉树
对于非空树仅有一个没有入度的根其他点最多有m个互不相交的有限集m称为树的度。m2二叉树
5.1. 二叉树性质
第i层最多有2i-1个结点深度为k的树最多有2k-1个结点n0 n2 1完全二叉树的叶子结点只存在最大和次大两层右孩子的深度为L则左孩子深度为L或L1n个结点的完全二叉树深度为: floor(log2(n)) 1结点i的父结点是i/2结点i的左孩子是2i右孩子是2i 1. 若大于结点总数n则无左孩子or右孩子N个结点可以组成C(2n, n) / (n 1) 或 C(n, 2n) - C(n-1, 2n)个不同的二叉树[n个元素出栈顺序数]某二叉树先序后续正好相反则为空树或每个结点只有一个孩子则只有一个叶结点
5.2 二叉树存储
一般采用链式存储
typedef struct BiTNode
{TDataType data;struct BiTNode *left, *right;
}BiTNode, *BiTree;5.3 二叉树的操作
遍历
void preOrder(BiTree T) // 先序遍历
{if (T NULL) return;d T-data;preOrder(T-left);preOrder(T-right);/** 中序inOrder(T-left);d T-data;inOrder(T-right);*//** 后序postOrder(T-left);postOrder(T-right);d T-data;*/
}void levelTravel(BiTree T)
{Queue q;initQueue(q);enQueue(q, T);while (!empty(q)){BiTNode node;deQueue(q, node);printf(%d, node-data); // 若数据为整型if (T-left ! NULL) enQueue(q, T-left);if (T-right ! NULL) enQueue(q, T-right);}
}复制二叉树
void copy(BiTree T, BiTree newT)
{if (T NULL){newT NULL;return;}newT (*BiTNode)malloc(sizeof(BiTNode));newT-data T-data;copy(T-left, newT-left);copy(T-right, newT-right);
}计算深度
int depth(BiTree T)
{if (T NULL) return 0;else return max(depth(T-left), depth(T-right)) 1;
}计算最大宽度
void getWidth(BiTree T, int count[], int level) // 用count数组存储每层的数量最大宽度是Max(count)
{if (T NULL) return 0;else{count[level];getWidth(T-left, count, level 1);getWidth(T-right, count, level 1);}
}5.4 线索二叉树
考的少 线索化是指对二叉树的遍历结果中体现出前驱后继的关系。 建立线索化先进行X序遍历先、中、后、层次得到序列在原树的结点加入Ltag和Rtag若0则left, right指针指向左右孩子若1则指向直接前驱和后继。
5.5 森林、树和二叉树
参考树、二叉树和森林的转换
森林转二叉树一棵树中每一层中靠右的兄弟变成靠左兄弟的右孩子最左的兄弟成为父结点的左孩子。对每棵树之间靠右的树根成为靠左的树根的右孩子最左的树根成为二叉树的根。二叉树转森林把根与右孩子分开成若干单独的二叉树单独树没有右孩子对于每棵二叉树右孩子变兄弟连接到最左的兄弟的父结点左孩子依然是孩子。
遍历 树的遍历 先根遍历先访问根结点后访问孩子(从左至右) 后根遍历先访问孩子后访问根结点 森林的遍历 先序遍历先访问第一棵树的根结点再访问根的子树最后访问剩下的树 中序遍历先中序遍历第一棵树的子树从左至右从叶到根的顺序在访问根节点最后访问剩下的树
5.6 霍夫曼树
会手动操作就行 主要思路每次选择最小的两个值组成新结点并加入到结点列表中重复。 霍夫曼编码过程则是在建立树之后按左为1右为0的方式。直到叶结点。 HT表的构建参考电子书P129
5.7 其他应用
通过先序、中序中序、后序而得到一棵唯一的树简单题目先序、后序不能得到一棵唯一的树
6. 图
6.1 图的建立
邻接矩阵
typedef VexType char;
typedef ArcType int;
typedef struct
{VexType vexs[MAX_NUM]; // 顶点表用来映射顶点名称(一般char)和数字下标(int)ArcType arcs[MAX_NUM][MAX_NUM]; // 邻接矩阵int vex_num, arc_num;
}AMGraph;特点
对于无向图第i行元素之和表示顶点i的度。对于有向图第i行元素之和表示顶点i的出度第i列表示顶点i的入度。mat[i][j]1表示i和j之间有边不利于增加删除顶点不利于统计边数空间复杂度高n个顶点需要O(n2)的空间
邻接表 默认为邻接出表即指向顶点的出度
typedef struct ArcNode // 边结点
{int adjvex;struct ArcNode* nextarc;InfoType info;
}ArcNode;
typedef struct VNode // 顶点结点
{VexType vex;struct ArcNode *firstarc;
}VNode, AdjList[MAX_NUM];
typedef struct
{AdjList vertices; // 邻接表int vex_num, arc_num;
}ALGraph;插入新边有向图
void insert(ALGraph G, VexType v1, VexType v2, InfoType info)
{i locate(G, v1); j locate(G, v2); // 确定v1和v2在G的位置struct ArcNode* p (ArcNode*) malloc(sizeof(ArcNode));p-adjvex j;p-info info;p-next G.vertices[i]-firstarc;G.vertices[i]-firstarc p;// 若为无向图则把i和j反过来再插入一次即可
}特点
利于增加删除结点统计边数方便时复O(ne)空间效率高空复O(ne)不利于判断v1和v2是否存在边需要扫描v1和v2的边表最差O(n)不利于统计顶点的度出表可以计算出度但是计算入度需要遍历整个表。逆邻接表计算入度方便却计算出度困难
6.2 图的遍历
深度优先搜索和广度优先搜索 题目中可能考察深度优先生成树和广度优先生成树 两个遍历方法中用邻接矩阵的时间复杂度是O(n2), 用邻接表复杂度为O(ne)
6.3 图的应用
最小生成树
Prim算法先随机确定一点再每次选连通分量周围最小的边复杂度O(n2)适合稠密图Kruskal算法每次选不构成回路的最小边复杂度O(eloge)其中包含排序适合稀疏图
最短路径 Dijskra算法从源点到其他点最小距离注意题目中可能要求完成距离变化表电子书P157 思路 (1) 用d数组记录距离起点为0其他点为正无穷。从起点开始运算 (2) 对当前点所有邻边进行访问若当前点的d值 其邻边代价 邻边的d值则更新邻边的d值和其父结点 (3) 找到更新后的最小d值的点放入“已完成”集合中并把此边作为下一个运算的顶点 (4) 若“已完成”集合包含了所有顶点则d值更新完成 (5) 终点的d值则为全局最小代价。从终点开始循环访问其父结点可找到起点这就是最短路径 Floyd算法每个点之间最小距离只适合邻接矩阵
拓扑排序 一定是有向无环图所以可以检测有向图中是否有环无解则有环 过程选一个无入度的顶点并输出再删除这个顶点以它为尾的弧重复。
关键路径 题目中主要是完成关键路径表 注意影响关键活动的因素有很多若子工程的时间有变化则要重新计算关键路径所以单提高一条关键路径上的关键活动速度还不能导致工程缩短工期必须同时提高几条关键路劲上的活动速度
6.4 十字链表
十字链表是有向图的另外一种存储方式通常可视为把邻接表和逆邻接表结合的方式。 定义 弧结点tailvex, headvex, headLink, tailLink, info(信息位) tailvex和headvex分别表示弧尾和弧头链接的顶点在图中的位置 headLink和tailLink分别表示弧尾和弧头指向的顶点相同的下一条弧 也就是说如果tailvex相同则用tailLink连接headvex相同用headLink连接 顶点结点data(信息位), firstIn, firstOut firstIn表示第一个入度的边 firstOut表示第一个出度的边
稀疏矩阵压缩也可以用十字链表方式 通常也分为两个 元素结点: 行标、列标、元素值、指针A、指针B 其中前三个行标、列标、元素值一般也是三元组的组成后面两个指针A指向同行的下一个B指向同列的下一个 表头chead, rhead 数组chead存储所有的列表头数组rhead存储所有行表头
7. 查找
7.1 顺序表
顺序查找ASL(n1)/2。可为顺序结构也可为链式结构 折半查找比较次数最多floor(log2(n)) 1ASLlog2(n 1) - 1。只能为可随机存储的顺序结构
int biSearch(SqList list, DataType e)
{low 0; high list.length - 1;while (low high){mid (low high) / 2;if (list.array[mid] e) return mid;else if (list.array[mid] e) high mid - 1;else low mid 1;}return -1;
}折半查找虽然数值上比顺序查找高效但是不一定快于后者
7.2 二叉排序树
左子树若不为空则比根结点小。右子树若不为空则比根结点大。左右子树都是二叉排序树。 增加结点 简单比结点大就放左子树比结点小就放右子树若不为空则继续
void insert(BSTree T, BSDataType e)
{if (T NULL){T (BSTNode*) malloc(sizeof(BSTNode));T-data e;T-left T-right NULL;}else{if (e T-data) insert(T-left, e);else insert(T-right, e);}
}删除结点 分为三个情况删除x结点
x为叶结点直接删除即可x有一个非空子树直接把此子树替代x结点x有两个非空子树让中序序列的x的直接前驱替代x左子树的最右的结点相当于删去此结点替换到x的位置若此结点也有子树(只有左子树)则启用方法2
7.3 平衡二叉树
左右子树深度差为-1、0、1称为平衡因子左右子树都是平衡二叉树 四个旋转LL、RR、LR、RL参考旋转方式
7.4 B-树
参考m阶b-树的特点
每个结点最多m个子树最少ceil(m/2)个子树每个结点有n个信息ceil(m/2)-1 ≤ n ≤ m-14阶b-树为[1,3]5阶b-树为[2,4]叶结点都在同一层
增加结点简单 以三阶b树为例每次插入到叶子结点若信息达到3个则把下标m/2的信息即中间的第二个上提到父结点若父节点也达到3个重复。 删除结点三种情况电子书P199 对于非终端结点则用右子树的最左结点即右边最小的元素替代此结点并删除该叶子结点的元素 对于终端结点如果信息 ceil(m/2)-1则无需更多操作 若 ceil(m/2)-1则向父结点借一位刚好比自己大的信息若不满足继续上借直到下沉参考文章
7.5 散列表的查找
构建散列函数 要求计算简单尽量做到一个关键词一个散列地址。散列值在表长范围内尽量减少冲突并且均匀分布 没有好与不好的函数只有适合与不适合的函数处理冲突的方法也如此 处理冲突 开放地址法若地址H0冲突则通过合适的计算得到另外一个地址H1 线性探测二次探测下一个位置为12, -12, 22, -22, …伪随机探测下一个地址Hibasedi(伪随机序列) 优点充分利用散列表空间缺点线性探测容易发生“二次聚集”现象二次探测和伪随机探测可以避免但还是不可避免不断地地址冲突 链地址法把相同散列值记录在单链表上
散列因子a 状如表的元素数量n / 散列表长度length 一般情况下a越大空间利用越高越容易发生冲突。a越小不易冲突但空间浪费多
等概率情况下ASL查找成功查找失败线性探测1/2 (1 1 / (1 - a))1/2 (1 1 / (1 - a)2)二次探测伪随机探测-1/a ln(1 - a)1 / (1 - a)链地址法1 a / 2a e-a一般做题不会用上面公式而是查找成功/失败的ASL用比较次数之和/总查找元素个数(电子书p209)
8. 排序
8.1 插入排序
思路将待排序关键字插入到已排序好的序列中合适的位置 直接插入排序顺序遍历序列每次选择一个关键字插入到已排序好的序列中从后往前如果序列趋于正序则插入部分速度越快接近O(1)最好情况是O(n)最坏情况下序列完全颠倒O(n2)平均O(n2)空间辅助O(1)排序稳定可适用于顺序表和链表
折半插入排序在直接插入的基础上改为折半查找并插入性能和上面一样。序列趋于有序和无序速度接近且不能适用于链表只适合顺序表
希尔排序缩小增量排序增量k的意义是将表每隔k个元素进行一次直接插入排序最好最好平均复杂度可参考上文直插排序然后缩小k并重复上述操作直到k1时序列趋于有序再对全体进行直插入排序。时复O(n1.3)空间辅助O(1)排序不稳定只可用于顺序表而且序列n越大越明显
8.2 交换排序
思路两两进行比较若不符合次序则交换直至整个有序 冒泡排序对序列中相邻的两个数若不符合顺序则进行交换并继续迭代。如果没有发生交换则算法结束。对于趋于正序发生交换的次数减少则迭代次数减少最好情况是完全正序时间复杂度O(n)一般和最差时复O(n2)空间辅助O(1)排序稳定。可适用于顺序表和链表
快速排序选择待排序列的某一个元素作为中枢pivot(一般第一个)序列最后下标为high第一个元素为low。从high往左找第一个比pivot小的元素与pivot进行交换。再从low往右边找第一个比pivot大的元素与pivot进行交换。重复操作直到lowhigh则固定了这个元素在已排好序列中的位置。最后对此元素的左右子序列进行同样的交换操作。 对于元素趋于有序正序or反序快速排序则退化成直接选择排序复杂度O(n2)最好的情况是分布均匀的序列复杂度O(nlogn)平均O(nlogn)因为用到了递归则最坏空间辅助O(n)平均空间辅助O(logn)不稳定排序仅适用于顺序表
8.3 选择排序
思路每一趟选择最小的关键字放在已排好序列的最后 直接选择排序序列前一段是已排序后一段是未排序。每一趟在未排序序列中选择最小的元素与未排序第一个进行交换。无论是否趋于有序选择最小元素必须遍历一次序列所以最好最坏平均复杂度都是O(n2)辅助O(1)不稳定排序可用于顺序表和链表
堆排序通过维护一个堆进行排序以小根堆为例从最后的非叶结点开始建立堆即把根和左右孩子中最小元素作为根并往前遍历直到整个堆的根此过程复杂度O(n)每次选出第一个元素把最后一个元素放第一个后维护堆此过程简述为换上来的根元素X与最小的孩子进行交换发生交换的一边继续交换直到X比左右孩子都小复杂度为O(logn)堆为空的时候完成排序。复杂度O(nlogn)空间可不用辅助数组O(1)不稳定排序仅顺序表
8.4 归并排序
思路将两个及以上的有序表合并成一个有序表 2-路归并排序1. 分治阶段每次从中间分割序列直到子序列长度2。2. 进行交换。3. 结合阶段所有子序列按照分治阶段的分组进行整合。每次整合复杂度O(n)分治结合的次数为O(logn)所以总复杂度O(nlogn)。需要辅助数组O(n)和递归空间O(logn)总空间辅助O(n)。稳定排序。可用于链表而且两个有序链表的合并不需要辅助数组辅助空间是递归空间O(logn)。但是需要手动找到序列中间位置。不过总时复不变
8.5 基数排序
不进行比较根据关键字的值来分配O(n)排序稳定考的少
排序名称最好情况最坏情况平均情况空间复杂度稳定性链式结构可用直接插入排序正序O(n)反序O(n2)O(n2)1稳定可用希尔排序O(n)O(n2)O(n1.3)1不稳定不可用直接选择排序O(n2)O(n2)O(n2)1不稳定可用堆排序O(nlogn)O(nlogn)O(nlogn)1不稳定不可用冒泡排序正序O(n)反序O(n2)O(n2)1稳定可用快速排序相对无序O(nlogn)正序或反序O(n2)O(nlogn)logn(最坏n)不稳定不可用归并排序O(nlogn)O(nlogn)O(nlogn)n稳定可用(链表版辅助空间logn)
后话
本人已从研究生毕业目前就职于某专科的专任教师以后有时间会再完善更新的
