数据结构-期末复习
Published:
东南大学-数据结构-期末复习笔记
算法复杂度分析
空间复杂度
时间复杂度
注释语句 0
声明语句
定义常量、变量，允许用户自定义数据类型，判断访问权限的语句，描述函数特性 0
表达式和赋值语句
大部分为1
若包含函数调用，判断调用函数开销
循环语句
for(<初始化语句>;<表达式1>;<表达式2>)
第一次初始化+表达式1
之后表达式1+表达式2
while<表达式>do/do...while<表达式>
每次表达式 1
switch
if else
delete new sizeof 1
return continue break goto return<表达式> 1
数组和链表
数组优于链表的:
A. 内存空间占用的少，因为链表节点会附加上一块或两块下一个节点的信息。
但是数组在建立时就固定了。所以也有可能会因为建立的数组过大或不足引起内存上的问题。
B. 数组内的数据可随机访问，但链表不具备随机访问性。这个很容易理解，数组在内存里是连续的空间，比如如果一个数组地址从100到200，且每个元素占用两个字节，那么100-200之间的任何一个偶数都是数组元素的地址，可以直接访问。
链表在内存地址可能是分散的。所以必须通过上一节点中的信息找能找到下一个节点。
C. 查找速度上。这个也是因为内存地址的连续性的问题，不罗索了。
链表优于数组的:
A. 插入与删除的操作。如果数组的中间插入一个元素，那么这个元素后的所有元素的内存地址都要往后移动。删除的话同理。只有对数据的最后一个元素进行插入删除操作时，才比较快。链表只需要更改有必要更改的节点内的节点信息就够了。并不需要更改节点的内存地址。
B. 内存地址的利用率方面。不管你内存里还有多少空间，如果没办法一次性给出数组所需的要空间，那就会提示内存不足，磁盘空间整理的原因之一在这里。而链表可以是分散的空间地址。
C. 链表的扩展性比数组好。因为一个数组建立后所占用的空间大小就是固定的，如果满了就没法扩展，只能新建一个更大空间的数组;而链表不是固定的，可以很方便的扩展。
数组
- 优点：使用方便，查询效率比链表高，内存为一连续的区域
- 缺点：大小固定，不适合动态存储，不方便动态添加
遍历
for (int i=0; i<sizeof(ns)/sizeof(ns[0]); i++) {
cout << ns[i];
}
链表
- 优点：可动态添加删除，大小可变
- 缺点：只能通过顺次指针访问，查询效率低
遍历
ChainNode *p;
while(p!=0){
cout << p -> data;
p = p -> next;
}
Chain<int> chain;
Chain<int>::iterator<int> it;
int sum = 0;
for(it = chain.begin(); it != chain.end(); it++)
sum += *it;
在结尾插入
template <class T>
void Chain<T>::InsertBack(const T& e)
{
if (first) { // nonempty chain
last→link = new ChainNode<T>(e);
last =last→link;
}
else
first = last= new ChainNode<T>(e);
}
插入p
p -> next = x -> next;
x -> next = p;
删除
p -> next = p -> next -> next;
合并
template <class T>
void Chain<T>::Concatenate(Chain<T>& b)
{ // b is concatenete to the end of *this
if (first){
last→link = b.first;
last = b.last;
}
else{
first = b.first;
last = b.last;
}
b.first = b.last = 0;
}
反转
template <class T>
void Chain<T>::Reverse()
{ // make (a1,.., an) becomes (an,.., a1).
ChainNode<T> *current = first, *previous = 0;
while (current) {
ChainNode<T> *r = previous; // r trails previous
previous = current;
current = current→link;
previous→link = r;
}
first = previous;
}
KMP
移动位数 = 已匹配的字符数 - 对应的部分匹配值
6 -2 = 4
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
栈和队列
栈
栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素。
进栈和出栈
基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：
- 向栈中添加元素，此过程被称为”进栈”（入栈或压栈）；
- 从栈中提取出指定元素，此过程被称为”出栈”（或弹栈）；
栈的具体实现
栈是一种 “特殊” 的线性存储结构，因此栈的具体实现有以下两种方式：
- 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
- 链栈：采用链式存储结构实现栈结构；
两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表。
栈的应用
基于栈结构对数据存取采用 “先进后出” 原则的特点，它可以用于实现很多功能。
例如，我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A，然后关闭了页面 A 跳转到页面 B，随后又关闭页面 B 跳转到了页面 C。而此时，我们如果想重新回到页面 A，有两个选择：
- 重新搜索找到页面 A；
- 使用浏览器的”回退”功能。浏览器会先回退到页面 B，而后再回退到页面 A。
浏览器 “回退” 功能的实现，底层使用的就是栈存储结构。当你关闭页面 A 时，浏览器会将页面 A 入栈；同样，当你关闭页面 B 时，浏览器也会将 B入栈。因此，当你执行回退操作时，才会首先看到的是页面 B，然后是页面 A，这是栈中数据依次出栈的效果。
不仅如此，栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题，此功能的底层实现使用的就是栈结构。
同时，栈结构还可以实现数值的进制转换功能。例如，编写程序实现从十进制数自动转换成二进制数，就可以使用栈存储结构来实现。
顺序栈
//元素elem进栈
int push(int* a,int top,int elem){
a[++top]=elem;
return top;
}
//数据元素出栈
int pop(int * a,int top){
if (top==-1) {
cout << "空栈";
return -1;
}
cout << "弹栈元素：" << a[top];
top--;
return top;
}
链栈
typedef struct lineStack{
int data;
struct lineStack * next;
}lineStack;
lineStack* push(lineStack * stack,int a){
lineStack * line=(lineStack*)malloc(sizeof(lineStack));
line->data=a;
line->next=stack;
stack=line;
return stack;
}
lineStack * pop(lineStack * stack){
if (stack) {
lineStack * p=stack;
stack=stack->next;
cout << "弹栈元素：" << p->data;
if (stack) {
cout << "栈顶元素：" << stack->data;
}else{
cout << "栈已空\n";
}
free(p);
}else{
cout << "栈内没有元素";
return stack;
}
return stack;
}
队列
数据从表的一端进，从另一端出，且遵循 “先进先出” 原则的线性存储结构就是队列。
队列的实现
队列存储结构的实现有以下两种方式：
- 顺序队列：在顺序表的基础上实现的队列结构；
- 链队列：在链表的基础上实现的队列结构；
两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。
队列的实际应用
实际生活中，队列的应用随处可见，比如排队买 XXX、医院的挂号系统等，采用的都是队列的结构。
拿排队买票来说，所有的人排成一队，先到者排的就靠前，后到者只能从队尾排队等待，队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后，才轮到自己买票。
顺序队列
int enQueue(int *a,int rear,int data){
a[rear]=data;
rear++;
return rear;
}
void deQueue(int *a,int front,int rear){
//如果 front==rear，表示队列为空
while (front!=rear) {
cout << "出队元素：" << a[front];
front++;
}
}
整个顺序队列在数据不断地进队出队过程中，在顺序表中的位置不断后移。顺序队列整体后移造成的影响是：
- 顺序队列之前的数组存储空间将无法再被使用，造成了空间浪费；
- 如果顺序表申请的空间不足够大，则直接造成程序中数组 a 溢出，产生溢出错误；
环状表
#define max 5//表示顺序表申请的空间大小
int enQueue(int *a,int front,int rear,int data){
//添加判断语句，如果rear超过max，则直接将其从a[0]重新开始存储，如果rear+1和front重合，则表示数组已满
if ((rear+1)%max==front) {
cout << "空间已满";
return rear;
}
a[rear%max]=data;
rear++;
return rear;
}
int deQueue(int *a,int front,int rear){
//如果front==rear，表示队列为空
if(front==rear%max) {
cout << "队列为空";
return front;
}
cout << a[front];
//front不再直接 +1，而是+1后同max进行比较，如果=max，则直接跳转到 a[0]
front=(front+1)%max;
return front;
}
链式队列
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
QNode * initQueue(){
QNode * queue=(QNode*)malloc(sizeof(QNode));
queue->next=NULL;
return queue;
}
QNode* enQueue(QNode * rear,int data){
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
//使用尾插法向链队列中添加数据元素
rear->next=enElem;
rear=enElem;
return rear;
}
QNode* DeQueue(QNode * top,QNode * rear){
if (top->next==NULL) {
cout << "\n队列为空";
return rear;
}
QNode * p=top->next;
cout << p->data;
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
return rear;
}
栈首先是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系，只不过它是一种特殊的线性表而已。
栈的特殊之处在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。
栈的插入操作，叫做进栈；栈的删除操作叫做出栈。
二叉树
遍历
树的遍历主要有两种，一种是深度优先遍历，像前序、中序、后序；另一种是广度优先遍历，像层次遍历。在树结构中两者的区别还不是非常明显，但从树扩展到有向图，到无向图的时候，深度优先搜索和广度优先搜索的效率和作用还是有很大不同的。 深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。
前序
void pre_order(binode *p){
if (p != NULL){
cout << p->data;
pre_order(p->left);
pre_order(p->right);
}
}
中序
void in_order(binode *p){
if (p != NULL){
in_order(p->left);
cout << p->data;
in_order(p->right);
}
}
后序
void post_order(binode *p){
if (p!= NULL){
post_order(p->left);
post_order(p->right);
cout << p->data;
}
}
层次
void lever_order(binode *p){
// 使用队列
list<binode *> t;
if (p != NULL){
t.push_back(p);
}
while (t.size() > 0){
cout << (t.front())->data;
if ((t.front())->left != NULL){
t.push_back((t.front())->left);
}
if ((t.front())->right != NULL){
t.push_back((t.front())->right);
}
t.pop_front();
}
}
二叉查找树
左孩子小于父亲，右孩子大于父亲
中序遍历——升序
查找
template <class K, class E> // Driver
pair<K,E>* BST<K,E>::Get(const K& k)
{ // Search *this for a pair with key k.
return Get(root, k);
}
template <class K, class E> // Workhorse
pair<K,E>* BST<K,E>::Get(treeNode<pair<K,E>>* p,
const K& k)
{
if (!p) return 0;
if (k < p→data.first) return Get(p→leftChild, k);
if (k > p→data.first) return Get(p→rightChild, k);
return &p→data;
}
template <class K, class E> // Iterative version
pair<K,E>* BST<K,E>::Get(const K& k)
{
TreeNode<pair<K,E>>* currentNode = root;
while (currentNode){
if (k < currentNode→data.first)
currentNode = currentNode→leftChild;
else if (k > currentNode→data.first)
currentNode = currentNode→rightChild;
else return ¤tNode→data;
}// no matching pairs
return 0;
}
插入
template <class K, class E>
void BST<K,E>::Insert(const pair<K,E>& thePair) {
TreeNode<pair<K,E>> *p=root, *pp=0;
while (p) {
pp=p;
if (thePair.first < p→data.first)
p=p→leftChild;
else if (thePair.first > p→data.first) p=p→rightChild;
else // duplicate, update associated element
{
p→data.second=thePair.second;
return;
}
}
p=new TreeNode<pair<K,E>>(thePair,0,0);
if (root){// tree not empty
if (thePair.first < pp→data.first)
pp→leftChild=p;
else pp→rightChild=p;
}
else root=p;
}
删除
删除叶子结点——直接删
删除度为1的结点
跳过
删除度为2的结点
左子树的最右孩子（最大）替换所删除结点
败者树
int loserTree[K]; /* 存储中间节点值，下标0处存储冠军节点 */
int leaves[K+1]; /* 从下标1开始存储叶子节点值，下标0处存储一个最小值节点 */
void adjust(int i)
{
int parent=(i+K-1)/2; /* 求出父节点的下标 */
while(parent>0)
{
if(leaves[i]>leaves[loserTree[parent]])
{
int temp=loserTree[parent];
loserTree[parent]=i;
/* i指向的是优胜者 */
i= temp;
}
parent = parent / 2;
}
loserTree[0]=i;
}
void initLoserTree()
{
int i;
for(i=1;i<K+1;i++)
scanf("%d",&leaves[i]);
leaves[0]=MIN;
for(int i=0;i<K;i++)
loserTree[i]=0;
for(int i=K;i>0;i--)
adjust(i);
}
堆
STL
堆的STL包含于
#include "algorithm"
头文件中。
堆的STL支持以下的基本操作:
make_heap(first, last, comp);
建立一个空堆；
push_heap(first, last, comp);
向堆中插入一个新元素；
top_heap(first, last, comp);
获取当前堆顶元素的值；
sort_heap(first, last, comp);
对当前堆进行排序；
整体：
#include <vector>
#include <cassert>
using namespace std;
class MaxHeap
{
private:
vector<int> heap;
int size;
public:
void make_heap(vector<int> & nums, int s)
{ //构建堆
heap.assign(nums.begin(), nums.end());
size = s;
for (int i = size / 2 - 1; i >= 0; i--)
down(i);
}
void push(int num)
{ //插入元素
heap.push_back(num);
size++;
up(size - 1);
}
int pop()
{ //删除元素
assert(size > 0);
int result = heap[0];
heap[0] = heap[size - 1];
heap.pop_back();
size--;
down(0);
return result;
}
void down(int index)
{
assert(index >= 0);
int temp = heap[index];
index = index * 2 + 1;
while (index < size)
{
if (index + 1 < size && heap[index] < heap[index + 1])
index++;
if (heap[index] < temp)
break;
else
{
heap[(index - 1) / 2] = heap[index];
index = index * 2 + 1;
}
}
heap[(index - 1) / 2] = temp;
}
void up(int index)
{
assert(index < size);
int temp = heap[index];
while (index > 0 && temp > heap[(index - 1) / 2])
{
heap[index] = heap[(index - 1) / 2];
index = (index - 1) / 2;
}
heap[index] = temp;
}
};
父节点为n，左孩子为2n，右孩子为2n+1
图
最小代价生成树
克鲁斯卡尔算法
每次选择一条最短的边(但不构成环)
typedef struct
{
char vertex[VertexNum]; //顶点表
int edges[VertexNum][VertexNum]; //邻接矩阵,可看做边表
int n,e; //图中当前的顶点数和边数
}MGraph;
typedef struct node
{
int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
}Edge;
void kruskal(MGraph G)
{
int i,j,u1,v1,sn1,sn2,k;
int vset[VertexNum]; //辅助数组，判定两个顶点是否连通
int E[EdgeNum]; //存放所有的边
k=0; //E数组的下标从0开始
for (i=0;i<G.n;i++)
{
for (j=0;j<G.n;j++)
{
if (G.edges[i][j]!=0 && G.edges[i][j]!=INF)
{
E[k].u=i;
E[k].v=j;
E[k].w=G.edges[i][j];
k++;
}
}
}
heapsort(E,k,sizeof(E[0])); //堆排序，按权值从小到大排列
for (i=0;i<G.n;i++) //初始化辅助数组
{
vset[i]=i;
}
k=1; //生成的边数，最后要刚好为总边数
j=0; //E中的下标
while (k<G.n)
{
sn1=vset[E[j].u];
sn2=vset[E[j].v]; //得到两顶点属于的集合编号
if (sn1!=sn2) //不在同一集合编号内的话，把边加入最小生成树
{
printf("%d ---> %d, %d",E[j].u,E[j].v,E[j].w);
k++;
for (i=0;i<G.n;i++)
{
if (vset[i]==sn2)
{
vset[i]=sn1;
}
}
}
j++;
}
}
普利姆算法
加点
AOV顶点表示活动的网络
顶点代表任务或活动，边代表任务之间的优先关系的有向图
#include <stdio.h>
#include <malloc.h>
#define max 100
typedef struct arcnode
{
int adjvex;
struct arcnode *next;
} arcnode;
typedef struct
{
int vertex;
arcnode *firstarc;
} vexnode;
vexnode adjlist[max];
int creatadjlist()
{
arcnode *ptr;
int arcnum, vexnum, k, v1, v2;
printf("input vexnum and arcnum:");
scanf("%d,%d", &vexnum, &arcnum);
for (k = 1; k <= vexnum; k++)
{
adjlist[k].firstarc = NULL;
adjlist[k].vertex = 0;
}
for (k = 1; k <= arcnum; k++)
{
printf("v1,v2=");
scanf("%d,%d", &v1, &v2);
ptr = (arcnode *)malloc(sizeof(arcnode));
ptr->adjvex = v2;
ptr->next = adjlist[v1].firstarc;
adjlist[v1].firstarc = ptr;
adjlist[v2].vertex++;
}
return vexnum;
}
toposort(int n)
{
int queue[max];
int front = 0, rear = 0;
int v, w, m;
arcnode *p;
m = 0;
for (v = 1; v <= n; v++)
if (adjlist[v].vertex == 0)
{
rear = (rear + 1) % max;
queue[rear] = v;
}
printf("the toposort:\n");
while (front != rear)
{
front = (front + 1) % max;
v = queue[front];
printf("%d ", v);
m++;
p = adjlist[v].firstarc;
while (p != NULL)
{
w = p->adjvex;
adjlist[w].vertex--;
if (adjlist[w].vertex == 0)
{
rear = (rear + 1) % max;
queue[rear] = w;
}
p = p->next;
}
}
if (m < n)
printf("the toposort is fail.");
}
int main()
{
int n;
n = creatadjlist();
toposort(n);
return 0;
}
拓扑序列
最短路径
迪杰特斯拉算法Dijkstra
class MatrixUDG {
#define MAX 100
#define INF (~(0x1<<31)) // 无穷大(即0X7FFFFFFF)
private:
char mVexs[MAX]; // 顶点集合
int mVexNum; // 顶点数
int mEdgNum; // 边数
int mMatrix[MAX][MAX]; // 邻接矩阵
public:
// 创建图(自己输入数据)
MatrixUDG();
// 创建图(用已提供的矩阵)
//MatrixUDG(char vexs[], int vlen, char edges[][2], int elen);
MatrixUDG(char vexs[], int vlen, int matrix[][9]);
~MatrixUDG();
// 深度优先搜索遍历图
void DFS();
// 广度优先搜索（类似于树的层次遍历）
void BFS();
// prim最小生成树(从start开始生成最小生成树)
void prim(int start);
// 克鲁斯卡尔（Kruskal)最小生成树
void kruskal();
// Dijkstra最短路径
void dijkstra(int vs, int vexs[], int dist[]);
// 打印矩阵队列图
void print();
private:
// 读取一个输入字符
char readChar();
// 返回ch在mMatrix矩阵中的位置
int getPosition(char ch);
// 返回顶点v的第一个邻接顶点的索引，失败则返回-1
int firstVertex(int v);
// 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
int nextVertex(int v, int w);
// 深度优先搜索遍历图的递归实现
void DFS(int i, int *visited);
// 获取图中的边
EData* getEdges();
// 对边按照权值大小进行排序(由小到大)
void sortEdges(EData* edges, int elen);
// 获取i的终点
int getEnd(int vends[], int i);
};
/*
* Dijkstra最短路径。
* 即，统计图中"顶点vs"到其它各个顶点的最短路径。
*
* 参数说明：
* vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
* prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
* dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
*/
void MatrixUDG::dijkstra(int vs, int prev[], int dist[])
{
int i,j,k;
int min;
int tmp;
int flag[MAX]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
// 初始化
for (i = 0; i < mVexNum; i++)
{
flag[i] = 0; // 顶点i的最短路径还没获取到。
prev[i] = 0; // 顶点i的前驱顶点为0。
dist[i] = mMatrix[vs][i]; // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
}
// 对"顶点vs"自身进行初始化
flag[vs] = 1;
dist[vs] = 0;
// 遍历mVexNum-1次；每次找出一个顶点的最短路径。
for (i = 1; i < mVexNum; i++)
{
// 寻找当前最小的路径；
// 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
min = INF;
for (j = 0; j < mVexNum; j++)
{
if (flag[j]==0 && dist[j]<min)
{
min = dist[j];
k = j;
}
}
// 标记"顶点k"为已经获取到最短路径
flag[k] = 1;
// 修正当前最短路径和前驱顶点
// 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
for (j = 0; j < mVexNum; j++)
{
tmp = (mMatrix[k][j]==INF ? INF : (min + mMatrix[k][j]));
if (flag[j] == 0 && (tmp < dist[j]) )
{
dist[j] = tmp;
prev[j] = k;
}
}
}
// 打印dijkstra最短路径的结果
cout << "dijkstra(" << mVexs[vs] << "): " << endl;
for (i = 0; i < mVexNum; i++)
cout << " shortest(" << mVexs[vs] << ", " << mVexs[i] << ")=" << dist[i] << endl;
}
排序
冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法描述
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
选择排序（Selection Sort）
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
- 初始状态：无序区为R[1..n]，有序区为空；
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了。
算法分析
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
算法分析
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
希尔排序（Shell Sort）
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
算法分析
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。
归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
算法分析
归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。
快速排序（Quick Sort）⭐⭐
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码实现
/* 快速排序 */
ElementType Median3( ElementType A[], int Left, int Right )
{
int Center = (Left+Right) / 2;
if ( A[Left] > A[Center] )
Swap( &A[Left], &A[Center] );
if ( A[Left] > A[Right] )
Swap( &A[Left], &A[Right] );
if ( A[Center] > A[Right] )
Swap( &A[Center], &A[Right] );
/* 此时A[Left] <= A[Center] <= A[Right] */
Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
/* 只需要考虑A[Left+1] … A[Right-2] */
return A[Right-1]; /* 返回基准Pivot */
}
void Qsort( ElementType A[], int Left, int Right )
{ /* 核心递归函数 */
int Pivot, Cutoff, Low, High;
if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
Pivot = Median3( A, Left, Right ); /* 选基准 */
Low = Left; High = Right-1;
while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
while ( A[++Low] < Pivot ) ;
while ( A[--High] > Pivot ) ;
if ( Low < High ) Swap( &A[Low], &A[High] );
else break;
}
Swap( &A[Low], &A[Right-1] ); /* 将基准换到正确的位置 */
Qsort( A, Left, Low-1 ); /* 递归解决左边 */
Qsort( A, Low+1, Right ); /* 递归解决右边 */
}
else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */
}
void QuickSort( ElementType A[], int N )
{ /* 统一接口 */
Qsort( A, 0, N-1 );
}
#include<iostream>
using namespace std;
void quickSort(int a[],int,int);
int main()
{
int array[]={34,65,12,43,67,5,78,10,3,70},k;
int len=sizeof(array)/sizeof(int);
cout<<"The orginal arrayare:"<<endl;
for(k=0;k<len;k++)
cout<<array[k]<<",";
cout<<endl;
quickSort(array,0,len-1);
cout<<"The sorted arrayare:"<<endl;
for(k=0;k<len;k++)
cout<<array[k]<<",";
cout<<endl;
system("pause");
return 0;
}
void quickSort(int s[], int l, int r)
{
if (l< r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j]>= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
堆排序（Heap Sort）
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
算法描述
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法描述
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
算法分析
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
算法描述
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
算法分析
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
基数排序（Radix Sort）
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
算法描述
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
算法分析
基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。
基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n»k，因此额外空间需要大概n个左右。
https://www.cnblogs.com/onepixel/p/7674659.html
AVL树
左右子树相减-1、0、1
插入
哈希
哈希函数——将一个关键字映射为哈希表中的一个桶的地址 既容易计算又能将冲突数目最小化
冲突处理方法
开放定址法
线性探测
平均查找长度
二次探测
i平方
链地址法
多用链表
B树
m阶B树是m路查找树，或者为空，或者满足下列性质
- 根结点至少有两个孩子
- 除根结点和外部结点以外，所有节点至少有[m/2]（取上界）
- 所有外部结点位于同一层
插入
