1.三种复杂度
Ο，读音：big-oh；表示上界，小于等于。
Ω，读音：big omega、欧米伽；表示下界，大于等于。
Θ，读音：theta、西塔；既是上界也是下界，称为确界，等于。
2.抽象数据类型
3.堆，栈（queue，stack）
4.哈希
- 线性探测
- 二次探测（重要）
- 二次哈希
5.二叉搜索树（BST）
#include <iostream>// 定义二叉搜索树节点
struct Node {int key;Node* left;Node* right;Node(int k) : key(k), left(NULL), right(NULL) {}
};// 插入节点
Node* insert(Node* root, int key) {// 如果树为空,创建根节点if (root == NULL) {return new Node(key);}// 递归插入节点if (key < root->key) {root->left = insert(root->left, key);} else if (key > root->key) {root->right = insert(root->right, key);}// 返回根节点return root;
}// 查找节点
Node* search(Node* root, int key) {// 如果树为空或找到目标节点,返回该节点if (root == NULL || root->key == key) {return root;}// 递归查找节点if (key < root->key) {return search(root->left, key);} else {return search(root->right, key);}
}// 中序遍历
void inorderTraversal(Node* root) {if (root != NULL) {inorderTraversal(root->left);std::cout << root->key << " ";inorderTraversal(root->right);}
}int main() {Node* root = NULL;// 插入节点root = insert(root, 50);root = insert(root, 30);root = insert(root, 20);root = insert(root, 40);root = insert(root, 70);root = insert(root, 60);root = insert(root, 80);// 中序遍历std::cout << "Inorder Traversal: ";inorderTraversal(root);std::cout << std::endl;// 查找节点Node* found = search(root, 40);if (found) {std::cout << "Found node with key: " << found->key << std::endl;} else {std::cout << "Node not found" << std::endl;}return 0;
}
6.堆
- 二叉堆，完全二叉堆
完全二叉堆(Complete Binary Heap)和二叉堆(Binary Heap)之间的主要区别如下:
定义:
完全二叉堆是一种特殊的二叉堆,它要求除了最底层之外,其他层的节点都是满的,且最底层的节点都集中在左侧。
二叉堆则是一种满足特定性质的二叉树,可以是完全二叉堆,也可以不是。
性质:
完全二叉堆除了最后一层外,其他层的节点都是满的。
二叉堆要求堆中任何节点的值都大于等于(小于等于)其左右子节点的值。这种性质称为堆属性。
存储:
完全二叉堆可以用数组高效地存储和表示,因为它的特殊结构。数组中的第 i 个元素的左右子节点分别是 2i+1 和 2i+2。
二叉堆也可以用数组存储,但不一定是完全二叉堆的形式。
7.AVL平衡树
LL,LR,RL,RR
#include <algorithm>
#include <iostream>// AVL 树节点定义
struct Node {item data;int height;Node* lson;Node* rson;Node(item x) : data(x), height(1), lson(nullptr), rson(nullptr) {}
};// 获取节点高度
int h(Node* t) {return t == nullptr ? 0 : t->height;
}// 左旋操作
void rotateL(Node*& s) {Node* t = s->lson;s->lson = t->rson;t->rson = s;s->height = std::max(h(s->lson), h(s->rson)) + 1;t->height = std::max(h(t->lson), s->height) + 1;s = t;
}// 右旋操作
void rotateR(Node*& s) {Node* t = s->rson;s->rson = t->lson;t->lson = s;s->height = std::max(h(s->lson), h(s->rson)) + 1;t->height = std::max(h(t->rson), s->height) + 1;s = t;
}// 双左旋操作
void dbl_rotateL(Node*& s) {rotateR(s->lson);rotateL(s);
}// 双右旋操作
void dbl_rotateR(Node*& s) {rotateL(s->rson);rotateR(s);
}// 插入节点
void AVL::insert(Node*& t, item x) {if (t == nullptr) {t = new Node(x);return;}else if (x < t->data) {insert(t->lson, x);if (h(t->lson) == h(t->rson) + 2) {if (x < t->lson->data) {rotateL(t);} else {dbl_rotateL(t);}}} else if (x > t->data) {insert(t->rson, x);if (h(t->rson) == h(t->lson) + 2) {if (x > t->rson->data) {rotateR(t);} else {dbl_rotateR(t);}}} else {// 如果遇到重复值,可以选择不插入或根据需求处理}t->height = std::max(h(t->lson), h(t->rson)) + 1;
}// 构建 AVL 树
Node* buildAVLTree(item arr[], int n) {Node* root = nullptr;for (int i = 0; i < n; i++) {insert(root, arr[i]);}return root;
}int main() {item arr[] = {10, 20, 30, 40, 50, 25};int n = sizeof(arr) / sizeof(arr[0]);Node* root = buildAVLTree(arr, n);// 可以在这里添加遍历或其他操作return 0;
}
8.Splay平衡树
9.红黑树
https://blog.csdn.net/weixin_69519040/article/details/131396072
Red-black Tree
– Definition of null path:
• any path starting from the root where the last node is not a full node
– Properties/definitions of red/black tree
• The root must be black
• Each null path must have the same number of black nodes
• Every red node must be : a full node (with two black children), or a leaf node
• if a node P has exactly one child, it must be black and its child is red leaf node
– Be able to do two types of insertions by-hand, bottom up insertions
by-code
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;typedef enum { RED, BLACK } Color;struct RBTreeNode {int data;Color color;struct RBTreeNode* left;struct RBTreeNode* right;struct RBTreeNode* parent;
};RBTreeNode* createNode(int data) {RBTreeNode* node = (RBTreeNode*)malloc(sizeof(RBTreeNode));node->data = data;node->color = RED; node->left = node->right = node->parent = NULL;return node;
}// 左旋
void leftRotate(RBTreeNode** root, RBTreeNode* x){RBTreeNode* y = x->right;x->right = y->left;if (y->left != NULL) {y->left->parent = x;}y->parent = x->parent;if (x->parent == NULL) {*root = y;}else if (x == x->parent->left) {x->parent->left = y;}else {x->parent->right = y;}y->left = x;x->parent = y;
}// 右旋
void rightRotate(RBTreeNode** root, RBTreeNode* y) {RBTreeNode* x = y->left;y->left = x->right;if (x->right != NULL) {x->right->parent = y;}x->parent = y->parent;if (y->parent == NULL) {*root = x;}else if (y == y->parent->right) {y->parent->right = x;}else {y->parent->left = x;}x->right = y;y->parent = x;
}// 调整红黑树以维持其性质
void fixViolation(RBTreeNode** root, RBTreeNode* z) {while (z != *root && z->parent->color == RED) {if (z->parent == z->parent->parent->left) {RBTreeNode* y = z->parent->parent->right;if (y != NULL && y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;}else {if (z == z->parent->right) {z = z->parent;leftRotate(root, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rightRotate(root, z->parent->parent);}}else {RBTreeNode* y = z->parent->parent->left;if (y != NULL && y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;}else {if (z == z->parent->left) {z = z->parent;rightRotate(root, z);}z->parent->color = BLACK;z->parent->parent->color = RED;leftRotate(root, z->parent->parent);}}}(*root)->color = BLACK;
}// 插入新节点
void insert(RBTreeNode** root, int data) {RBTreeNode* z = createNode(data);RBTreeNode* y = NULL;RBTreeNode* x = *root;while (x != NULL) {y = x;if (z->data < x->data) {x = x->left;}else {x = x->right;}}z->parent = y;if (y == NULL) {*root = z;}else if (z->data < y->data) {y->left = z;}else {y->right = z;}fixViolation(root, z);
}// 打印红黑树
void printTreeHelper(RBTreeNode* root, int space) {int COUNT = 10; // 调整这个值来控制缩进的宽度if (root == NULL)return;space += COUNT;printTreeHelper(root->right, space);// 打印当前节点printf("\n");for (int i = COUNT; i < space; i++)printf(" ");printf("%d(%s)\n", root->data, root->color == RED ? "R" : "B");printTreeHelper(root->left, space);
}void printTree(RBTreeNode* root) {printTreeHelper(root, 0);
}int main() {RBTreeNode* root = NULL;int newElement;/* insert(&root,22);insert(&root,18);insert(&root,36);insert(&root,19);insert(&root,30);printTree(root);*/while (1) {cout<<"请输入要插入的新元素（输入-1结束）: ";cin >> newElement;if (newElement == -1) {break;}insert(&root, newElement);cout<<"插入 "<<newElement<<" 后的红黑树结构:\n";printTree(root);printf("\n");}return 0;
}
10.插入排序
template <typename Type>
void insertion_sort(Type *const array, int const n) {for (int k = 1; k < n; ++k) {Type value = array[k]; // Element to be insertedint j;// Shift elements of array[0..k-1], that are greater than value,// to one position ahead of their current positionfor (j = k; j > 0 && array[j - 1] > value; --j) {array[j] = array[j - 1]; // Move greater elements one position ahead}// Insert the value at its correct positionarray[j] = value;}
}
11.冒泡排序
（1）初始版本
template <typename Type>
void bubble(Type *const array, int const n) {// The outer loop controls the number of passes, with the largest element// "bubbling up" to its correct position at the end of each passfor (int i = n - 1; i > 0; --i) {// The inner loop is responsible for comparing and swapping adjacent elements// during each passfor (int j = 0; j < i; ++j) {// If the current element is greater than the next element, swap themif (array[j] > array[j + 1]) {std::swap(array[j], array[j + 1]);}}}
}
（2）
template <typename Type>void bubble( Type *const array, int const n ) {for ( int i = n - 1; i > 0; --i ) {Type max = array[0]; // assume array[0] is the maxfor ( int j = 1; j <= i; ++j ) {if ( array[j] < max ) {array[j - 1] = array[j]; // move} else {array[j – 1] = max; // store the old maxmax = array[j]; // get the new max}}array[i] = max; // store the max}
(3)
template <typename Type>void bubble( Type *const array, int const n ) {int pos;for ( int i = n - 1; i > 0;) {Type max = array[0];pos = 0;for ( int j = 1; j <= i; ++j ) {if ( array[j] < max ) {array[j - 1] = array[j];pos = j - 1;} else {array[j – 1] = max;max = array[j];}}array[i] = max;i = pos}}
（4）
#include<iostream>
using namespace std;int a[10] = { 3,5,1,2,4,7,9,8,6,0 };
//运用四种优化方法
void Improved4_BubbleSort(int *array, int n) {int lower = 0;int upper = n - 1;while (true) {bool sorted=1; //优化2 int max = array[lower]; //优化1 int new_upper = lower;for (int i = lower; i < upper; ++i) {if (array[i+1] < max) {array[i] = array[i + 1];new_upper = i;sorted=0;}else {array[i] = max;max = array[i + 1];}}if(sorted) break;array[upper] = max;upper = new_upper;if (lower == upper) {break;}int min = array[upper];int new_lower = upper;for (int i = upper; i > lower; --i) {if (array[i-1] > min) {array[i] = array[i-1];new_lower = i;sorted=0;}else {array[i] = min;min = array[i-1];}}if(sorted) break;array[lower] = min;lower = new_lower;if (lower == upper) {break;}}
}int main()
{cout<<"origin: ";for(int i=0;i<10;i++) cout<<a[i]<<' ';puts("");Improved4_BubbleSort(a, 10);for(int i=0;i<10;i++) cout<<a[i]<<' ';return 0;
}
12.堆排序
in-place
#include<bits/stdc++.h>
using namespace std;void Heapify(int a[], int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && a[left] > a[largest])largest = left;if (right < n && a[right] > a[largest])largest = right;if (largest != i) {swap(a[i], a[largest]);Heapify(a, n, largest);}
}void BuildMaxHeap(int a[], int n) {for (int i = n / 2 - 1; i >= 0; i--)Heapify(a, n, i);
}void HeapSort(int a[], int n) {BuildMaxHeap(a, n);int cnt=0;for (int i = n - 1; i > 0; i--) {swap(a[0], a[i]);Heapify(a, i, 0);}
}int main() {int a[] = {34, 15, 65, 59, 79, 42, 40, 80, 50, 61, 23, 46};int n = 12;cout << "Original array: ";for (int i = 0; i < n; i++)cout << a[i] << " ";cout << endl;HeapSort(a, n);cout << "Sorted array: ";for (int i = 0; i < n; i++)cout << a[i] << " ";cout << endl;return 0;
}
13.归并排序+求逆序对
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;int n, a[12000], b[12000];
long long int inversions = 0; // 用于记录逆序对的数量void merge(int low, int mid, int high) {int i = low, j = mid + 1, k = low;while (i <= mid && j <= high) {if (a[i] <= a[j]) {b[k++] = a[i++];} else {b[k++] = a[j++];inversions += (mid - i + 1); // 更新逆序对数量}}while (i <= mid)b[k++] = a[i++];while (j <= high)b[k++] = a[j++];for (int i = low; i <= high; i++)a[i] = b[i];
}void mergesort(int x, int y) {if (x >= y) return;int mid = (x + y) / 2;mergesort(x, mid);mergesort(mid + 1, y);merge(x, mid, y);
}int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];mergesort(1, n); // 调用函数for (int i = 1; i <= n; i++)cout << a[i] << " ";cout << endl;cout << "逆序对数量: " << inversions << endl;return 0;
}
14.快速排序
Median-of-three, in-place sorting, use insertion sort when size is small
#include<iostream>
using namespace std;
void insertionsort(int array[],int low, int high) {for (int i = low + 1;i <= high;i++) {int key = array[i];int j = i - 1;while (j >= low && array[j] > key) {array[j + 1] = array[j];--j;}array[j + 1] = key;}
}
int middle(int array[], int low, int high) {int mid = low + (high - low) / 2;if (array[low] > array[mid]) {swap(array[low], array[mid]);}if (array[low] > array[high]) {swap(array[low], array[high]);}if (array[mid] > array[high]) {swap(array[mid], array[high]);}return mid;
}
int partition(int array[], int low, int high) {int pivotIndex = middle(array, low, high);int pivot = array[pivotIndex];swap(array[pivotIndex], array[high]);int i = low - 1;for (int j = low; j < high; ++j) {if (array[j] < pivot) {++i;swap(array[i], array[j]);}}swap(array[i + 1], array[high]);return i + 1;
}
void quicksort(int array[],int low,int high) {if ((high - low + 1) <= 6) {insertionsort(array, low, high);return;}int pivotIndex = partition(array, low, high);quicksort(array, low, pivotIndex - 1);quicksort(array, pivotIndex + 1, high);
}
int main() {int n;cin >> n;int* array = new int[n];for (int i = 0;i < n;i++) {cin >> array[i];}quicksort(array, 0, n - 1);for (int i = 0;i < n;i++) {cout << array[i] << " ";}return 0;
}
15.基数排序
16.希尔排序
17.Multiway Search Tree（3-way trees）
template <typename Type>
Three_way_node *Three_way_node<Type>::find( Type const &obj ) const {if ( !full() ) {return ( first() == obj );}if ( (obj == first()) || (obj == second()) ) {return this;} else if ( obj < first() ) {return ( left() == nullptr) ? nulltpr : left()->find( obj );} else if ( obj > second()) ) {return ( right() == nullptr) ? nullptr : right()->find( obj );} else {return (middle() == nulltpr) ? nullptr : middle()->find( obj );}
}template <typename Type>
bool Three_way_node<Type>::insert( Type const &obj ) {if ( !full() ) {if ( obj == first() ) {return false;} else if ( obj < first() ) {second_value = first();first_value = obj;} else {second_value = obj;}num_values = 2;return true;}if ( obj == first() || obj == second() ) {return false;}if ( obj < first() ) {if ( left() == nullptr ) {p_left_tree = new Three_way_node( obj );return true;} else {return left()->insert( obj );}} else if ( obj > second() ) {// create or insert a new node at the right sub-tree} else {// create or insert a new node at the middle sub-tree}
}
template <typename Type, int N>
class Multiway_node {private:int num_values;Type elements[N – 1];Multiway_node *[N]; // an array of pointers to multiway nodespublic:Multiway_node( Type const & );// ...
};template<typename Type, int M>
bool M_ way_node<Type, M>::full() const {return ( num_values == M - 1 );
}
template <typename Type, int N>
void Multiway_node<Type, N>::in_order_traversal() const {if ( empty() ) {return;} else if ( !full() ) {for ( int i = 0; i < num_values; ++i ) {cout << elements[i];}} else {for ( int i = 0; i < N - 1; ++i ) {if ( subtrees[i] != nullptr ) {subtrees[i]->in_order_traversal();}cout << elements[i];}subtrees[N - 1]->in_order_traversal();}
}
