数据结构整理
时间复杂度（最坏情况）：算法中基本操作重复执行的次数是问题规模n的某个函数 f(n) ，记作：T(n) = O(f(n))，他表示随规模n的增加，算法执行时间的增长率和 f(n) 的增长率相同。
线性表的顺序存储结构：用一组地址连续的存储单元依次存储线性表的数据元素。（查找方便但增减复杂除了在末端）
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。# define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 # define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef struct { ElemType *elem; // 线性空间基址 int length; // 当前长度 int listszie; // 当前分配的存储空间容量（以sizeof（Element）为单位） }sqList;
线性表的链式存储结构（线性链表或单链表）：用一组任意的存储单元存储线性表的数据元素（存储单元可以是连续的也可以是不连续的），节点包含2个域：一个数据域，一个指针域指向下一个节点。（查找慢但灵活）
typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList;
循环链表：表中的最后一个节点的指针域指向头节点，整个链表形成一个环。
双向链表：比链式存储结构增加多一个指向前节点的指针。
typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode,*DuLinkList;
栈（顺序存储和链式存储）：是限定仅在表尾进行插入或删除操作的线性表。表尾称栈顶，表头称栈底。
栈的顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。base为栈底指针，始终指向栈底位置若为NULL则栈不存在，若top = base则为空栈。
typedef struct { SElemType *base; SElemType *top; int stacksize; // 当前栈的最大容量 }SqStack;
栈的链式存储结构：
typedef struct { SElemType *base; SElemType *top; }SqStack;
队列：一种先进先出的线性表，只允许在表的一端进行插入，而在另一端删除元素。允许插入的一端叫做队尾，允许删除的一端叫做队头。（定义与栈相同但是插入、删除等操作不同）
循环队列（顺序存储队列的节省空间的方式）：front == rear，队头等于队尾的情况有俩种（满或空队列），俩种处理方式：1.另设一个标志以区别队列是满或空 2.少用一个元素空间，约定如果队尾指针的下一个位置是队友的话则是队满。（对MAXQSIZE取余能实现循环队列）
#define MAXQSIZE 100 typedef struct { QElemType *base; // 初始化的动态分配存储空间 int front; // 头指针，若队列不空，指向队列头指针 int rear; // 尾指针，若队列不空，指向队列尾元素的下一位置 }SqQueue;
串（线性表结构）：由0个或多个字符组成的有限序列。串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串，通常称字符在序列中的序号为该字符在串中的位置，子串在主串的位置则以子串的第一个字符在主串中的位置来表示。
串的模式匹配：
int Index(SString S,SString T,int pos){ // 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0 // 其中，T非空，1 <= pos <= StrLength(S) // 串的第一个元素存放串的长度，即S[0] i = pos;j = 1; while(i <= S[0] && j <= T[0]){ if (S[i] == T[j]){++i;++j;} else{i = i - j + 2;j = 1;} } if(j > T[0]) return i - T[0]; else:return 0; }
改进的模式匹配算法（KMP算法）：每当一趟匹配过程中出现字符比较不等时，不需回溯 i 指针，而是利用已经得到的部分匹配的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。
int Index(SString S,SString T,int pos){ // 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0 // 其中，T非空，1 <= pos <= StrLength(S) // 串的第一个元素存放串的长度，即S[0] // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置 i = pos;j = 1; while(i <= S[0] && j <= T[0]){ if (j == 0 || S[i] == T[j]){++i;++j;} else j == next[j]; } if(j > T[0]) return i - T[0]; else:return 0; } void get_next(SString T,int next[]){ // 求模式串T的next函数值并存入数组next。 i == 1;next[1] = 0;j == 0; while(i < T[0]){ if (j == 0 || T[i] == T[j]){++i;++j;next[i] = j;} else j = next[j]; } }
int Index(char * haystack,int haystack_size,char * needle,int needle_size,int *next){ int i = 0,j = 0; while(i < haystack_size && j < needle_size){ if(j == -1 || haystack[i] == needle[j]){i++;j++;} else j = next[j]; } if(j >= needle_size)return i - needle_size; else return -1; } void get_next(char * needle,int *next,int needle_size){ int i = 0,j = -1; next[0] = -1; while(i < needle_size - 1){ if(j == -1 || needle[i] == needle[j]){i++;j++;next[i] = j;} else j = next[j]; } }
数组：n维数组是一个定长的线性表，他的每一个数据元素也是一个定长线性表。数组一旦被定义，他的维数和维界不再改变，除了结构的初始化和销毁之外，数组只能存取元素和修改元素值的操作。
# define MAX_ARRAY_DIM 8 // 假设数组维度的最大值为8 typedef struct { ElemType *base; // 数组元素的基址，有初始化函数分配 int dim; // 数组维度 int *bounds; // 数组维界基址，记录维度信息 int *constants; // 数组映像函数常量基址，如果225维度则该值为10,5,1
广义表：当广义表非空时，称第一个元素为表头，称其余元素组成的表为表尾。
1. 列表的元素可以是子表，而子表的元素还可以是子表.......
2. 列表可为其他列表所共享（引用）。
3.列表可以是一个递归的表，列表也可以是其本身的子表。
由于广义表中的数据元素可以具有不同的结构（或是元组或是列表），难以用顺序存储结构表示，通常采用链式存储结构。
typedef enum {ATOM,LIST} ElemTag; // ATOM == 0为原子，LIST == 1为子表 typedef struct GLNode{ ElemTag tag; // 公共部分，用以区分原子节点和表节点 union { // 原子节点和表节点的联合部分 AtomType atom; // atom是原子节点的值域 struct {struct GLNode *hp,*tp}ptr; // ptr是表节点的指针域，ptr.hp 和ptr.tp 分别指向表头和表尾 }; }
二叉树：每一个节点至多只有俩颗子树，而且二叉树的子树有左右之分，其次序不能任意颠倒。
1. 在二叉树的第 i 层至多有 2 ^ (i - 1)个节点（i >= 1）
2.深度为 k 的二叉树至多有 2 ^ k - 1个节点。
满二叉树：一个深度为 k 且有 2 ^ k - 1 个节点的二叉树称为满二叉树
完全二叉树：对满二叉树的节点进行连续编号，约定编号从根节点起，自上而下，自左而右。深度为 k 的有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中编号从1 至 n 的节点（满二叉树的节点数大于等于完全二叉树）一一对应时称为完全二叉树。
顺序存储结构：数组来存储，用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的节点元素。0代表不存在此节点，因此只适合完全二叉树。
链式存储结构：由数据域和左右指针组成。（如果加入指向其双亲的指针称为三叉链表）
typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
遍历二叉树：先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）
// 先序遍历 // Visit 为返回节点数据 Status PreOrderTraverse(BiTree T,Status (* Visit)(TElemType e)){ if(T){ if(Visit(T -> data)) if(PreOrderTraverse(T -> lchild,Visit) if(PreOrderTraverse(T -> rchild,Visit))return OK; return ERROR; }else return OK; }
// 中序遍历，非递归，栈实现 // Visit 为返回节点数据 Status PreOrderTraverse(BiTree T,Status (* Visit)(TElemType e)){ InitStack(S);Push(S,T); // 根指针进栈 while(!StackEmpty(S)){ while(GetTop(S,p) && p) Push(S,p -> lchild); // 向左走到尽头 Pop(S,p); // 空指针退栈 if(!StackEmpty(S)){ Pop(S,p); if(!Visit(p -> data)) return ERROR; Push(S,p -> rchild); } } return OK; }
线索二叉树：因为有 n 个节点的二叉树中必定存在 n + 1个空链域，所以用这些来存储前驱和后继。如果有左孩子则 lchild 指向左孩子，否则指向前驱，如果有右孩子则 rchild 指向右孩子，否则指向后继。
typedef enum Pointertag {link,Thread}; // Link == 0：指针 Thread == 1：线索 typedef struct BiThrNode{ TElemType data; struct BiThrNode *lchild,*rchild; Pointertag LTag,RTag; // 左右标志0代表左右节点 1代表前驱或后继 }BiThrNode,*BiThrTree;
最优二叉树（赫夫曼树）：
路径长度：从树中一个节点到另一个节点之间的分支构成这俩个节点之间的路径，路径上的分支数目称做路径长度。
树的带权路径长度（WPI）：该节点到树根之间的路径长度与节点上权的乘积（每一个叶子节点都有一个权重）。
最优二叉树：WPI最小的树。
赫夫曼算法：
1. 根据给定的 n 个权值{w1,w2,w3,w4,...wn}构成 n 棵二叉树的集合F= {T1,T2,T3...Tn}，其中每棵二叉树 Ti 中只有一个带权为 wi 的根节点，其左右子树均空。
2. 在 F 中选取俩棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，而且新的二叉树的根节点的权值为其左右子树上根节点的权值之和。
3. 在 F 中删除这俩棵树，同时将得到的二叉树加入 F 中。
4. 重复2、3步骤，知道 F 只含一棵树为止，这棵树就是赫夫曼树。
折半查找（有序表，顺序存储结构）：O(log(n))
int Search_Bin(SSTable ST,keyType key){ low = 1;high = ST.length; while(low >= high){ mod = (low + high) / 2; if(EQ(key,ST.elem[mid].key)) return mid; else if(LT(key,ST.elem[mid].key)) high = mid - 1; else low = mid + 1; } return 0; }
二叉排序树：一棵空树或满足以下条件：1. 若他的左（右）子树不为空，则左（右）子树上所有节点的值均小于他的根节点的值 2. 他的左右子树也分别是二叉排序树。中序遍历就是有序序列。
// 查找 Status SearchBST(BiTree T,KeyType key,BiTree f,Bitree &p){ // 在根指针 T 所指二排序树中递归地查找其关键词等于 key 的数据元素，若查找成功则指针 p 指向该数据元素节点，并返回TRUE， // 否则返回指针 p 指向查找路径上访问的最后一个节点并返回FALSE，指针 f 指向 T 的双亲，其初始值为 NULL if(!T){p = f;return FALSE;} else if(EQ(key,T -> data.key)){p = f;return TRUE;} else if(LT(key,T -> data.key))return SearchBST(T -> lchild;key;T;p); else return SearchBST(T -> rchild;key;T;p); } // 因为是动态查找，所以不存在的元素会进行插入 Status InsertBST(BiTree T,ElemType e){ if(!SearchBST(T,e.key,NULL,p){ s = (BiTree)malloc(sizeof (BiTNode)); s -> data = e; s -> lchild = s -> rchild = NULL; if(!p)T =s; else if(LT(e.key,p -> data.key))p -> lchild = s; else p -> rchild = s; return TRUE; else return FALSE; }
平衡二叉树：一棵空树或者他的左右子树都是平衡二叉树并且左右子树的深度之差的绝对值不超过1。
构成平衡的二叉排序树：把元素逐渐加入树中，遇到不属于平衡二叉树的情况则进行修正，有4种情况：LL、RR、LR(先RR再LL)、RL。
typedef struct BSTNode{ ElemType data; int bf; // 节点的平衡因子 struct BSTNode *lchild,*rchild; // 左右孩子指针 }BSTNode,*BSTree;
#define LH 1 // 左高 #define EH 0 // 等高 #define RH -1 // 右高 void LL(BSTree &p){ // LL情况 lc = p -> lchild; p -> lchild = lc -> rchild; lc -> rchild = p; p = lc; } void RR((BSTree &p){ // RR情况 rc= p -> rchild; p -> rchild= lc -> lchild; lc -> lchild= p; p = lc; } void Left_Balance(BSTree &T){ // 作左子树平衡，T指向新的根节点 lc = T -> lchild; // lc指向T的左子树根节点 switch(lc -> bf){ case LH: // LL的情况 T -> bf = lc -> bf = EH; LL(T); break; case RH: // LR情况 rd = lc -> rchild; swich(rd -> bf){ case LH:T -> bf = RH;lc -> bf = EH;break; case EH:T -> bf = lc -> bf = EH;break; case RH:T -> bf = EH;lc -> bf = LH;brea; } rd -> bf = EH; RR(T -> lchild); LL(T); } } int InsertAVL(BSTree &T,ElemType e,Boolean &taller){ // 若在平衡的二叉树T中不存在和e有相同关键字的节点，则插入一个数据元素为e的新节点，并返回1，否则返回0. // 若因插入而使二叉排序树失去平衡，则作平衡旋转处理，taller反映T长高与否 if(!T){ T = (BSTree)malloc(sizeof(BSTNode)); T -> bf = EH;T -> data = e; T -> lchild = T -> rchild = NULL; taller = TRUE; }else{ if(EQ(e.key,T -> data)){ // 存在相同的节点，不用插入 taller = 0; return 0; } if(LT(e.key,T -> data)){ if(!InsertAVL(T -> lchild,e,taller))return 0; // 未插入 if(taller) switch(T -> bf){ case LH:LeftBalance(T);taller = FALSE;break; case EH:T -> bf = LH;taller = TRUE;break; case RH:T -> bf = EH;taller = FALSE;break; } }else{ if(!InsertAVL(T -> rchild,e,taller))return 0; // 未插入 if(taller) switch(T -> bf){ case LH:T -> bf = EH;taller = FALSE;break; case EH:T -> bf = RH;taller = TRUE;break; case RH:RightBalance(T);taller = FALSE;break; } } } return 1; }
B-树：平衡的多路查找树
一棵m阶的B-树，或空树或满足以下条件：
1.树中每一个节点至多有m棵树
2.若根节点不是叶子节点，则至少有俩棵子树
3.除根之外的所有非终端节点至少有 m / 2(取整)棵子树
4.所有的非终端节点中包含下列信息数据
(n,A0,K1,A1,K2,.....Kn,An) 其中 Ki 为关键字，且 Ki < KI + 1(i = 1,2,3,...n - 1)；Ai(i = 0,1,2,...n)为指向子树根节点的指针，且指针 Ai - 1 所指子树中所有节点的关键字均小于Ki (i = 1,2...n)，An 所指子树所有节点的关键字均大于Kn，n为关键字的个数。
5.所有的叶子节点都出现在同一层次上，并且不带信息。
# define m 3 // B-树的阶 typedef struct BTNode{ int keynum; // 节点中关键字个数，即节点的大小 struct BTNode *parent; // 指向双亲节点 KeyType key[m+1]; // 关键字向量，0单元未用 struct BTNode *ptr[m+1]; // 子树指针向量 Record *recptr[m+1]; // 记录指针向量，0号单元未用 }BTNode,*BTree;
B+树：
一棵m阶的B+树和m阶的B-树的差异：
1.有 n 棵子树的节点中含有 n 个关键字。
2.所有的叶子节点中包含了全部的关键字的信息，及指向含有这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
3.所有的非终端节点可以看成是索引部分，节点中含有其子树（根节点）中的最大（最小）关键字。
哈希表：
1.直接定址法：取关键字或关键字的某个线性函数值为哈希地址
2.平方取中法：取关键字平方后的中间几位为哈希地址。因为中间几位与数的每一位的相关。
3.折叠法：将关键字分割成位数相同的几部分（最后一个可以不同），然后取这几部分的叠加和作为哈希地址。
4.除留余数法：取关键字被某个不大于哈希表表长 m 的数 p 除后所得余数为哈希地址。也可以在折叠、平方取中后进行取余。
冲突处理方法：
1.开放定址法：Hi = (H(key) + di) MOD m ， i = 1,2,3,4....k(k <= m - 1)，H（key）为哈希函数，m为表长，di为增量序列有以下3种取法：1.di = 1,2,3...m - 1，2.di = 1^2,(-1)^2,2^2,(-2)^2...，3.di = 伪随机数。
2.再哈希法：在同义词产生地址冲突时计算另一个哈希地址，知道冲突不再发生。
参考查找算法：https://www.cnblogs.com/maybe2030/p/4715035.html
折半排序：O（n^2）
void BInsertSort(SqList &L){ // 对顺序表 L 作折半插入排序 for(i = 2;i <= L.length;++i){ L.r[0] = L.r[i]; low = 1;high = i - 1; while(low <= high){ // 在 r[low..high]中折半查找有序插入的位置 m = (low + high) / 2; // 折半 if(LT(L.r[0].key,L.r[m].key)) high = m - 1; // 插入点在低半区 else low = m + 1; // 插入点在高半区 } for(j = i - 1;j >= high + 1; --j) L.r[j + 1] = L.r[j]; // 记录后移 L.r[high + 1] = L.r[0]; } }
快速排序 O(nlogn)：通过一趟排序将待排序记录分割成独立的俩部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这俩部分记录继续进行排序，已达到整个序列有序。
int Partition(SqList &L,int low,int high){ // 交换顺序表 L 中子表 r[low..high] 的记录，枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）与它 L.r[0] = L.r[low]; // 用子表的第一个记录作枢纽记录 pivotkey = L.r[low].key; // 枢纽记录关键字 while(low < high){ // 从表的俩端交替地向中间扫描 while(low < high && L.r[high].key >= povotkey) --high; L.r[low] = L.r[high]; // 将枢纽记录小的记录移到低端 while(low < high && L.r[low].key <= povotkey) ++low; L.r[high] = L.r[low]; // 将枢纽记录小的记录移到高端 } L.r[low] = L.r[0]; // 枢纽记录到位 return low; // 返回枢纽记录 } void QSort(SqList &L,int low,int high){ // 对顺序表 L 中的子序列 L.r[low..high]作快速排序 if(low < high){ pivotloc = Partition(L,low,high); QSort(L,low,pivotloc - 1); // 对低子表递归排序 QSort(L,pivotloc + 1,high); // 对高子表递归排序 } }
int fun(int* nums, int low,int high){ int norm = nums[low]; while(low < high){ while(low < high && nums[high] >= norm) --high; nums[low] = nums[high]; while(low < high && nums[low] <= norm) ++low; nums[high] = nums[low]; } nums[low] = norm; return low; } void Sort_fun(int* nums, int low,int high){ int mid; if(low < high){ mid = fun(nums,low,high); Sort_fun(nums,low,mid - 1); Sort_fun(nums,mid + 1,high); } }
堆排序 O(nlogn)：堆的含义为完全二叉树中所有非终端节点的值均不大于（或不小于）其左右孩子节点的值，堆顶元素必为序列中 n 个元素的最小值（或最大值）。若在输出堆顶的最小值（最大值）之后，使得剩余 n - 1 个元素的序列重新建一个堆，则得到次小值，反复执行得到有序序列。
typedef SqList HeapType; // 顺序存储结构 void HeadAdjust(HeapType &H,int s,int m){ // 已知 H.r[s..m] 中记录的关键字除 H.r[s].key 之外均满足堆的定义，本函数调整 H.r[s] 的关键字， // 使 H.r[s..m] 成为一个大顶堆（对其中记录的关键字而言） rc = H.r[s]; for(j = 2 * s;j <= m;j *= 2){ // 沿 key 较大的孩子节点向下筛选 if(j < m && LT(H.r[j].key,H.r[j + 1].key)) ++j; // j 为 key 较大的记录的下标 if(!LT(rc.key,H.r[j].key)) break; H.r[s] = H.r[j]; s = j; } H.r[s] = rc; } void HeapSort(HeapType &H){ // 对顺序表H进行堆排序 for(i = H.length / 2;i > 0;--i){ // 建大顶堆 HeadAdjust(H,i,H.length); } for(i = H.length;i > 1;--i){ H.r[1] <-> H.r[i]; // 将第一个记录与最后一个交换 HeadAdjust(H,1,i - 1); // 除去最后一个元素，重新建大顶堆 } }
void heap_sort(int* nums, int numsSize,int* res_index){ int tmp,tmp_index; for(int i = numsSize / 2 - 1;i >= 0;i--){ HeadAdjust(nums,i,numsSize,res_index); } for(int i = numsSize - 1;i > 0;i--){ tmp = nums[i]; tmp_index = res_index[i]; nums[i] = nums[0]; res_index[i] = res_index[0]; nums[0] = tmp; res_index[0] = tmp_index; HeadAdjust(nums,0,i,res_index); } } void HeadAdjust(int* nums, int index,int numsSize,int* res_index){ int norm = nums[index],norm_index = res_index[index]; for(int i = index * 2 + 1;i < numsSize;i = i * 2 + 1){ if(i + 1 < numsSize && nums[i] < nums[i + 1]) i++; if(norm >= nums[i])break; nums[index] = nums[i]; res_index[index] = res_index[i]; index = i; } nums[index] = norm; res_index[index] = norm_index; }
归并排序 O(nlogn)：假设初始序列含有 n 个记录，则可看成是 n 个有序的子序列，每一个子序列的长度为1，然后俩俩归并，得到 n / 2 个长度为2或1的有序子序列；再俩俩归并.......,如此重复，直到得到一个长度为n的有序序列为止。
void Merge(RcdType SR[],RcdType &TR[],int i,int m,int n){ // 将有序的S[i..m] 和 SR[m + 1....n]归并为有序的TR[i..n] for(j = m + 1,k = i;k <= m && j <= n;++k){ // 将SR中记录由小到大的并入TR if(LQ(SR[i].key,SR[j].key)) TR[k] = SR[i++]; else TR[k] = SR[j++]; } if(i <= m) TR[k..n] = SR[i..m]; // 将剩余的SR[i..m]复制到TR if(j <= m) TR[k..n] = SR[j..n]; } void MSort(RcdType SR[],RcdType &TR1[],int s,int t){ // 将SR[s..t]归并排序为TR1[s..t] if(s == t) TR1[s] = SR[s]; else{ m = (s + t) / 2; MSort(SR,TR2,s,m); MSort(SR,TR2,m + 1,t); Merge(TR2,TR1,s,m,t); } }
void Merge(int *SR,int *TR,int low,int mid,int high); void MSort(int *SR,int *TR,int SR_size,int low,int high){ if(low == high){ TR[low] = SR[low]; }else{ int *Tmp = (int*)malloc(sizeof(int) * SR_size); int mid = (low + high) / 2; MSort(SR,Tmp,SR_size,low,mid); MSort(SR,Tmp,SR_size,mid + 1,high); Merge(Tmp,TR,low,mid,high); free(Tmp); } } void Merge(int *SR,int *TR,int low,int mid,int high){ int k = low,j = mid + 1; for(;low <= mid && j <= high;k++){ if(SR[low] < SR[j]) TR[k] = SR[low++]; else TR[k] = SR[j++]; } if (low <= mid){ for(int i = low;i <= mid;i++)TR[k++] = SR[i]; } if (j <= high){ for(int i = j;i <= high;i++)TR[k++] = SR[i]; } } int main(){ int S[8] = {58,42,59,57,41,7,8,2}; MSort(S,S,8,0,7); return 0; }
void Merge(int *SR,int *TR,int low,int mid,int high){ int k = low,j = mid + 1; for(;low <= mid && j <= high;k++){ if(SR[low] < SR[j]) TR[k] = SR[low++]; else TR[k] = SR[j++]; } if (low <= mid){ for(int i = low;i <= mid;i++)TR[k++] = SR[i]; } if (j <= high){ for(int i = j;i <= high;i++)TR[k++] = SR[i]; } } int* MSort(int *SR,int *TR,int low,int high){ int i = low,x = 2; while(x <= high * 2){ while(i <= high){ int mid = (i * 2 + x) / 2 - 1; if(i == high)TR[i] = SR[i]; else{ int high_tmp = i + x - 1 > high ? high : i + x - 1; Merge(SR,TR,i,mid,high_tmp); } i += x; } x *= 2; i = 0; int *tmp = SR; SR = TR; TR = tmp; } return SR; } int main(){ int S[] = {58,42,59,57,41,7,8,2,2,45,12,-3},size = 12; int *tmp = (int*)malloc(sizeof(int) * size); for(int i = 0;i < size;i++){ tmp[i] = S[i]; } int *res = MSort(S,tmp,0,size - 1); free(tmp); return 0; }
| 排序方法 | 平均时间 | 最坏情况 | 辅助存储 |
| 简单排序 | O(n^2) | O(n^2) | O(1) |
| 快速排序 | O(nlogn) | O(n^2) | O(logn) |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) |
| 基数排序 | O(d(n + rd)) | O(d(n + rd)) | O(rd) |
