时间复杂度
O(1)O(logn)O(n)O(nlogn)O(n^2)O(n^3)O(2^n)O(n!)O(n^n)
$$
O(1) < O(log_n)<O(n)<O(nlog_n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
$$
排序
冒泡排序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// 最简单冒泡排序 void BubbleSort(int arr[], int length) { for (int i = 0; i < length; i++) { for (int j = 0; j < length - i - 1; j++) { if (arr[j] > arr[j+1]) { // 三种交换方法 // 1. 临时变量 2. 加减法 3. 异或 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// 优化 void BubbleSort(int arr[], int length) { for (int i = 0; i < length; i++) { bool is_sorted = true; for (int j = 0; j < length - i - 1; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; is_sorted = false; } } if (is_sorted) { break; } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
void BubbleSort(int arr[], int length) { int last_exchange_index = 0; int sort_border = length - 1; for (int i = 0; i < length; i++) { bool is_sorted = true; for (int j = 0; j < sort_border; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; is_sorted = false; last_exchange_index = j; } } sort_border = last_exchange_index; if(is_sorted) { break; } } } |
快速排序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
int get_pivot(int arr[], int start, int end) { int pivot = arr[start]; int left = start, right = end; while (left != right) { while (left < right && arr[right] > pivot) { right--; } while(left < right && arr[left] <= pivot) { left++; } if (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } } arr[start] = arr[left]; arr[left] = pivot; return left; } void quick_sort(int arr[], int start, int end) { if (start >= end) { return; } int pivot_index = get_pivot(arr, start, end); quick_sort(arr, start, pivot_index - 1); quick_sort(arr, pivot_index + 1, end); } |
堆排序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// 上浮 最小堆 void upAdjust(int arr[], int length) { int child_index = length - 1; int parent_index = (child_index - 1) / 2; int temp = arr[child_index]; while (child_index > 0 && temp > arr[parent_index]) { arr[child_index] = arr[parent_index]; child_index = parent_index; parent_index = (parent_index - 1) / 2; } arr[child_index] = temp; } // 下沉 最大堆 void downAdjust(int arr[], int parent_index, int length) { int temp = arr[parent_index]; int child_index = 2 * parent_index + 1; while (child_index < length) { if (child_index + 1 < length && arr[child_index + 1] > arr[child_index]) { child_index++; } if (temp >= arr[child_index]) { break; } arr[parent_index] = arr[child_index]; parent_index = child_index; child_index = 2 * child_index + 1; } arr[parent_index] = temp; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
void HeapSort(int arr[], int length) { for (int i = (length - 2) / 2; i >= 0; i--) { downAdjust(arr, i, length); } for (int i = length - 1; i > 0; i--) { int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; downAdjust(arr, 0, i); } } |
查找
顺序查找
|
1 2 3 4 5 6 7 8 9 |
int seq_search(int *a, int n, int key) { int i; for (i = 1; i <= n; i++) { if (a[i] == key) { return i; } } return 0; } |
折半查找
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int binary_search(int *a, int n, int key) { int low, high, mid; low = 1; high = n; while (low <= high) { mid = (low + high) / 2; if (key < a[mid]) { high = mid - 1; } else if (key > a[mid]) { low = mid + 1; } else { return mid; } } return 0; } |
插值查找
$$
mid = (high - low) \cdot \frac{key-arr[low]}{arr[high]-arr[low]}
$$
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
int binary_search(int *a, int n, int key) { int low, high, mid; low = 1; high = n; while (low <= high) { // 相对于二分查找来说，是在这个地方对于mid的确定，换了个算法 mid = low + (high - low)*(key - a[low])/(a[high] - a[low]); if (key < a[mid]) { high = mid - 1; } else if (key > a[mid]) { low = mid + 1; } else { return mid; } } return 0; } |
二叉排序树
- 又叫二叉查找树
- 它或者是一颗空树，或者是一颗具有以下性质的二叉树：
- 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值
- 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
结构
|
1 2 3 4 5 |
// 二叉树二叉链表结构 typedef struct BiTNode { int data; struct BiTNode* lchild, * rchild; } BiTNode, *BiTree; |
查找
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// f指向tree的双亲 // 查找成功，p指向该数据元素节点，否则p指向访问路径上的最后一个节点并返回FALSE Status SearchBST(BiTree* tree, int key, BiTree f, BiTree* p) { if (!tree) { *p = f; return FALSE; } else if (key == tree->data) { *p = tree; return TRUE; } else if (key < tree->data) { SearchBST(tree->lchild, key, tree, p); } else { SearchBST(tree->rchild, key, tree, p); } } |
插入
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Status InsertBST(BiTree * tree, int key) { BiTree p, s; if (!SearchBST(*tree, key, NULL, &p)) { s = (BiTree)malloc(sizeof(BiTree)); s->data = key; s->lchild = s->rchild = NULL; if (!p) { *tree = s; } else if (key < p->data) { p->lchild = s; } else { p->rchild = s; } return TRUE; } else { return FALSE } } |
删除
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Status DeleteBST(BiTree *tree, int key) { if (!*tree) { return FALSE; } else { if (key == tree->data) { return Delete(tree); } else if (key < tree->data) { return DeleteBST(&(*tree)->lchild, key); } else { return DeleteBST(&(*tree)->rchild, key); } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
Status Delete(BiTree * p) { BiTree q, s; if ((*p)->rchild == NULL) { q = *p; *p = (*p)->lchild; free(q); } else if ((*p)->lchild == NULL) { q = *p; *p = (*p)->rchild; free(q); } else { q = *p; s = (*p)->lchild; while (s->rchild) { q = s; s = s->rchild; } (*p)->data = s->data; if (q!=*p) { q->rchild = s->lchild; } else { q->lchild = s->rchild; } free(s); } return TRUE; } |
平衡二叉树（AVL）
- 是一种二叉排序树
- 其中每一个节点的左子树和右子树的高度差最多等于1
- 平衡二叉树是高度平衡的二叉排序树
- 它要么是一颗空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1
平衡因子
- 将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF
- 平衡二叉树上所有节点的平衡因子只可能是-1、0、1
- 只要有一个结点的平衡因子的绝对值大于1，该二叉树就是不平衡的
最小不平衡树
- 距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树，我们称为最小不平衡子树
构建平衡二叉树过程
- 每当插入一个结点时，先检查是否因插入而破坏了树的平衡性
- 如果破坏了，找出最小不平衡子树
- 在保持二叉排序树特性的前提下，调整最小不平衡子树中各节点之间的链接关系，进行相应的旋转
- 使之成为新的平衡子树
实现
|
1 2 3 4 5 |
typedef struct BiTNode { int data; int bf; struct BiTNode* lchild, * rchild; } BiTNode, *BiTree; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// 右旋 void R_Rotate(BiTree* p) { BiTree l; l = (*p)->lchild; (*p)->lchild = l->rchild; l->rchild = (*p); *p = l; } // 左旋 void L_Rotate(BiTree* p) { BiTree r; r = (*p)->rchild; (*p)->rchild = r->lchild; r->lchild = (*p); *p = r; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// 左平衡旋转 #define LH + 1 // 左高 #define EH 0 // 等高 #define RH - 1 // 右高 void LeftBalance(BiTree* t) { BiTree l, lr; l = (*t)->lchild; switch(l->bf) { case LH: (*t)->bf = l->bf = EH; R_Rotate(t); break; case RH: lr = l->rchild; switch (lr->bf) { case LH: (*t)->bf = RH; break; case EH: (*t)->bf = l->bf = EH; break; case RH: (*t)->bf = EH; l->bf = LH; break; } lr->bf = EH; L_Rotate(&(*t)->lchild); R_Rotate(t); } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
Status InsertAVL(BiTree* t, int e, Status* taller) { if (!*t) { // 插入新结点，树变高，taller为TRUE *t = (BiTree)malloc(sizeof(BiTNode)); (*t)->data = e; (*t)->lchild = (*t)->rchild = NULL; (*t)->bf = EH; *taller = TRUE; } else { if (e == (*t)->data) { // 树中已经存在相同关键字的结点 *taller = FALSE; return FALSE; } if (e < (*t)->data) { // 继续在t的左子树中搜索 if(!InsertAVL(&(*t)->lchild, e, taller)) { return FALSE; } 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 FALSE; } 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 TRUE; } |
多路查找树
- 又叫B树
- 每一个节点的孩子数可以多余两个，且每一个节点处可以存储多个元素
2-3树
- 每一个节点都具有两个孩子（2结点）或三个孩子（3结点）
- 一个2结点包含一个元素和两个孩子（或没有孩子，要么就是两个孩子，要么就是没有孩子），左子树包含的元素小于该元素，右子树包含的元素大于该元素
- 一个3结点包含一小一大两个元素和三个孩子（或没有孩子，要么就是三个孩子，要么就是没有孩子）
2-3-4树
- 2-3树概念的扩展
- 包含了4结点的使用
- 一个4结点包含了小中大三个元素和四个孩子（或没有孩子，要么有4个孩子，要么没有孩子）
B树
- B树是一种平衡的多路查找树，
2-3树和2-3-4树都是B树的特例 - 节点最大的孩子称为B树的阶
- 因此
2-3树是3阶B树，2-3-4树是4阶B数
- 因此
- m阶B树特点：
- 如果根结点不是叶结点，则其至少有两颗子树
- 每一颗非根的分支结点都有k-1个元素和k个孩子，其中
[m/2]<=k<=m
每一个叶子结点n都有k-1个元素，其中[m/2] <= k <= m - 所有叶子结点都位于同一层次
- 所有分支节点包含下列信息数据（
n,A0,K1,A1,K2,A2,...,Kn,An）,
n(m/2向上取整 -1 <= n <= m-1)为关键字的个数
ki（i=1,2,3,...)为关键字，且Ki<Ki+1 (i=1,2,...,n-1) Ai (i=0,2,...,n)为指向子树根节点的指针且子树Ai-1所指子树中所有节点的关键字均小于Ki（i=1,2,3,...,n），An所指子树中所有节点的关键字均大于Kn，n(m/2向上取整-1 <= n <= m-1)为关键字的个数（或n+1为子树的个数）
B+树
- 为了能够解决所有元素遍历等基本问题，在原有的B树结构基础上，加上了新的元素组织方式，就是B+树
- 在B树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支节点上。而在B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出
- 另外，每个叶子结点都会保存一个指向后一个叶子结点的指针
M阶B树与B+树差异
- 有n颗子树的节点包含有n个关键字
- 所有的叶子结点包含全部关键字信息，及指向包含这些关键字记录的指针，叶子结点本身依赖关键字的大小自小而大顺序链接
- 所有分支结点可以看成是索引，节点中仅含有其子树中的最大（或最小）关键字
哈希表
概念
- 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置
f(key)。 - f称为散列函数，或者哈希函数
- 采用哈希函数将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或者哈希表。
哈希函数构造方法
- 直接定址法
- 平方取中法
- 折叠法
- 除留余数法
f(key) = key mod p (p <= m)
- 随机数法
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
热评文章
- 大话数据结构_图表示 0
- 大话数据结构_树 0
- 大话数据结构_图遍历 0
- 大话数据结构_队列 0
- 大话数据结构_图相关 0
- 大话数据结构_栈_应用 0