数据结构

算法

数据结构

线性表

链表

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
// define element type
typedef int ElemType;

// define struct of linked list
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

// define Status
typedef enum Status {
    ERROR,
    SUCCESS
} Status;

LinkList CreateList_Head(LinkList &L)
{
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));     //创建头结点
    L->next  =NULL;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;                          //插入结点
        scanf("%d",&x);
    }
    return L;
}

void TraverseList(LinkList L)
{
    LNode *p = L->next;
    while(p){
        cout << p->data << " " ;
        p = p->next;
    }
}

int main(){
    LinkList L;
    L = new LNode;
    CreateList_Head(L);
    TraverseList(L);
    return 0;
}

栈

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
#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1
#define STACKSIZE 10;              //存储空间分配增量
#define STACK_INIT_SIZE 100;    //存储空间初始分配量

typedef int ElemType;
typedef int Status;

typedef struct
{
    ElemType* base;    //栈底
    ElemType* top;     //栈顶
    int stacksize;          //当前已分配的空间
}SqStack;

//初始化栈
Status initStack(SqStack &S)
{
    S.base = (ElemType *)malloc(100 * sizeof(ElemType));
    if (!S.base){
        exit(0);
    }
    S.top = S.base;
    S.stacksize = 100;
    return OK;

}

//入栈
Status Push(SqStack& S, ElemType e)
{
    if (S.top - S.base >= S.stacksize)   //如果栈满就追加空间
    {                           //新增内存空间
        S.base = (ElemType*)realloc(S.base, (S.stacksize + 10) * sizeof(ElemType));
        if (!S.base) exit(0);
        S.top = S.base + S.stacksize;
        S.stacksize += 10;
    }
    *S.top++ = e;
    return OK;
}

//出栈
Status Pop(SqStack& S, ElemType &e)
{
    if (S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}

队列

根据存储结构划分：1.链式队列 2.循环队列 3.单向队列 4.双端队列

顺序队列

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
#define MAXSIZE 1000
typedef struct {
    int data[MAXSIZE];
    int front,rear;
}Sequeue;

void SequeueInit(Sequeue &Top){//队列的初始化
    Top.front=0;
    Top.rear=0;
}

void SequeueEmpty(Sequeue &Top){//判队列为空
    if(Top.rear==Top.front)
    {
        printf("队列为空\n");
    }
    else  printf("队列不为空\n");
}

void SequeuePush(Sequeue &Top,int m){//循环入队列
   if((Top.rear+1)%MAXSIZE==Top.front)
        {printf("队列已满");}
   else{
       Top.data[Top.rear]=m;
       printf("%d已入队\n",m);
       Top.rear=(Top.rear+1)%MAXSIZE;}
}

void SequeueTop(Sequeue &Top)//求队列头部元素
{
    printf("队列头部元素为%d\n",Top.data[Top.front]);
}

void SequeuePop(Sequeue &Top){//循环出队列
    int i=0;
    if(Top.rear==Top.front)
     {printf("队列为空");}
    else{
        while (Top.rear!=Top.front) {
            i++;
            printf("队第%d元素为%d\n",i,Top.data[Top.front]);
            Top.front=(Top.front+1)%MAXSIZE;
        }
    }
}

int SequeueTopp(Sequeue &Top)//求队列头部元素( 返回值)
{
    return Top.data[Top.front];
}
void SequeuePushh(Sequeue &Top,int m){//不循环入队列
    Top.data[Top.rear]=m;
    Top.rear++;
}
int  SequeuePopp(Sequeue &Top){//不循环出队列
    int m=Top.data[Top.front];
        Top.front++;
        return m;
}

循环队列

数组

动态数组

树和二叉树

二叉树

C++：nullptr 专用于初始化空类型指针

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<iostream>
using namespace std;

template<typename DataType>
struct BiNode
{
    DataType data;
    BiNode *lchild, *rchild;
};

template<typename DataType>
class BiTree
{
public:
    BiTree( ){
        root = Creat(root);	//构造函数，建立二叉树
    }
    ~BiTree( ){
        Release(root);   //析构函数，释放各结点的存储空间
    }
    void PreOrder( ){
        PreOrder(root);   //前序遍历二叉树
    }
    void InOrder( ){
        InOrder(root);   //中序遍历二叉树
    }
    void PostOrder( ){
        PostOrder(root);   //后序遍历二叉树
    }
    void LeverOrder( ); //层序遍历二叉树
private:
    BiNode <DataType>*Creat(BiNode<DataType> *bt); //构造函数
    void Release(BiNode<DataType> *bt); 		  //析构函数调用
    void PreOrder(BiNode<DataType> *bt); 		  //前序遍历函数
    void InOrder(BiNode<DataType> *bt); 		  //中序遍历函数
    void PostOrder(BiNode<DataType> *bt); 		  //后序遍历函数
    BiNode<DataType> *root;					     //指向根结点的头指针
};

template<typename DataType>
BiNode<DataType> *BiTree <DataType>:: Creat(BiNode<DataType> *bt)
{
    char ch;
    cout << "请输入扩展二叉树的前序遍历序列，每次输入一个字符:";
    cin >> ch; //输入结点的数据信息，假设为字符
    if (ch == '#') bt = nullptr; //建立一棵空树
    else
    {
        bt = new BiNode<DataType>;
        bt->data = ch;
        bt->lchild = Creat(bt->lchild); //递归建立左子树
        bt->rchild = Creat(bt->rchild); //递归建立右子树
    }
    return bt;
}

template<typename DataType>	//前序遍历
void BiTree<DataType>:: PreOrder(BiNode<DataType> *bt)
{
    if (bt == nullptr) return; 
    cout << bt->data; 	  
    PreOrder(bt->lchild); 
    PreOrder(bt->rchild); 
}

template<typename DataType>	//中序遍历
void BiTree<DataType>:: InOrder(BiNode<DataType> *bt)
{
    if (bt == nullptr) return; 
    else
    {
        InOrder(bt->lchild); 
        cout << bt->data; 
        InOrder(bt->rchild);
    }
}

template<typename DataType>	//后序遍历
void BiTree<DataType>:: PostOrder(BiNode<DataType> *bt)
{
    if (bt == nullptr) return;
    else
    {
        InOrder(bt->lchild);
        InOrder(bt->rchild);
        cout << bt->data;
    }
}

template<typename DataType>	//层次遍历
void BiTree<DataType>:: LeverOrder( )
{
    BiNode<DataType> *Q[100], *q = nullptr; //顺序队列
    int front = -1, rear = -1; //队列初始化
    if (root == nullptr) return; //二叉树为空，算法结束
    Q[++rear] = root; //根指针入队
    while (front != rear) //当队列非空时
    {
        q = Q[++front]; //出队
        cout << q->data;
        if (q->lchild != nullptr) Q[++rear] = q->lchild;
        if (q->rchild != nullptr) Q[++rear] = q->rchild;
    }
}

template<typename DataType>
void BiTree<DataType>:: Release(BiNode<DataType> *bt)
{
    if (bt == nullptr) return;
    else
    {
        Release(bt->lchild); //释放左子树
        Release(bt->rchild); //释放右子树
        delete bt; //释放根结点
    }
}

层序遍历

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
class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode* root) {
        vector<vector<int> > res;
        if(root == NULL)	//如果是空，则直接返回空vector
            return res; 
        queue<TreeNode*> q; 	//队列存储，进行层次遍历
        q.push(root);
        TreeNode* cur;
        while(!q.empty()){
            //记录二叉树的某一行
            vector<int> row;  
            int n = q.size();
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for(int i = 0; i < n; i++){
                cur = q.front();
                q.pop();
                row.push_back(cur->val);
                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);
            }
            //每一层加入输出
            res.push_back(row); 
        }
        return res;
    }
};

AVL Tree

AVL树（Adelson-Velsky and Landis Tree）是CS中最早被发明的自平衡二叉查找树。

一棵AVL树有如下必要条件：

  • 必须是二叉查找树
  • 每个节点的左子树和右子树的高度差至多为1

AVL Tree Visualzation 可视化演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct AVLnode
{
    int key;    //值
    struct AVLnode *left;
    struct AVLnode *right;
    int height;     //高度
};

void printAVL(avlNode *node, int level)	//树尖向左打印
{
    int i;
    if (node != NULL)
    {
        printAVL(node->right, level + 1);
        printf("\n\n");

        for (i = 0; i < level; i++) printf("\t");

        printf("%d", node->key);

        printAVL(node->left, level + 1);
    }
}

平衡化操作

平衡二叉树 — 优雅的进行旋转

LL型

img

1
2
3
4
5
6
7
8
9
10
11
12
13
avlNode *rightRotate(avlNode *T)
{
    avlNode *L = T->left;
    avlNode *T3 = L->right;

    L->right = T;
    T->left = T3;

    T->height = (Max(nodeHeight(T->left), nodeHeight(T->right)) + 1);
    L->height = (Max(nodeHeight(L->left), nodeHeight(L->right)) + 1);

    return L;
}
RR型

img

1
2
3
4
5
6
7
8
9
10
11
12
13
avlNode *leftRotate(avlNode *T)
{
    avlNode *R= T->right;
    avlNode *T3 = R->left;

    R->left = z;
    T->right = T3;

    T->height = (Max(nodeHeight(T->left), nodeHeight(T->right)) + 1);
    R->height = (Max(nodeHeight(R->left), nodeHeight(R->right)) + 1);

    return R;
}
LR型

img

1
2
3
4
avlNode *LeftRightRotate(avlNode *z){
    T->left = leftRotate(T->left);
    return (rightRotate(T));
}
RL型

img

1
2
3
4
avlNode *RightLeftRotate(avlNode *T){
    T->right = rightRotate(T->right);
    return (leftRotate(T));
}

二叉查找树

​ 二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree）。

一棵空树或者具有下列性质的二叉树：

  • 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若任意结点的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
  • 任意结点的左、右子树也分别为二叉查找树
1
2
3
4
5
6
typedef struct node
{
     int data;
    struct node *left;
    struct node *right;
} node;

红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树

红黑树满足以下特征：

  • 节点分为红色或者黑色；
  • 根节点必为黑色；
  • 叶子节点都为黑色，且为null；
  • 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
  • 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
  • 新加入到红黑树的节点为红色节点；(推断)

类比234树——4阶B树

图

邻接表

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<iostream>
using namespace std;

struct EdgeNode //定义边表结点
{
    int adjvex; //邻接点域
    EdgeNode *next;
};

template <typename DataType>
struct VertexNode //定义顶点表结点
{
    DataType vertex;
    EdgeNode *firstEdge;
};

const int MaxSize = 10; //图的最多顶点数
int visited[MaxSize] = {0};
template  <typename DataType>
class ALGraph
{
public:
    ALGraph(DataType a[ ], int n, int e); //构造函数，建立n个顶点e条边的图
    ~ALGraph( ); //析构函数，释放邻接表各边表结点的存储空间
    void DFTraverse(int v); //深度优先遍历图
    void BFTraverse(int v); //广度优先遍历图
private:
    VertexNode<DataType> adjlist[MaxSize]; //存放顶点表的数组
    int vertexNum, edgeNum; //图的顶点数和边数
};

template <typename DataType>
ALGraph<DataType> :: ALGraph(DataType a[ ], int n, int e)
{
    int i, j, k;
    EdgeNode *s = nullptr;
    vertexNum = n;
    edgeNum = e;
    for (i = 0; i < vertexNum; i++) //输入顶点信息，初始化顶点表
    {
        adjlist[i].vertex = a[i];
        adjlist[i].firstEdge = NULL;
    }
    for (k = 0; k < edgeNum; k++) //依次输入每一条边
    {
        cout << "输入边所依附的两个顶点的编号：";
        cin >> i >> j; //输入边所依附的两个顶点的编号
        s = new EdgeNode;
        s->adjvex = j; //生成一个边表结点s
        s->next = adjlist[i].firstEdge; //将结点s插入到第i个边表的表头
        adjlist[i].firstEdge = s;
    }
}

template <typename DataType>
ALGraph<DataType>  :: ~ALGraph( )
{
    EdgeNode *p = NULL, *q = NULL;
    for (int i = 0; i < vertexNum; i++)
    {
        p = q = adjlist[i].firstEdge;
        while (p != NULL)
        {
            p = p->next;
            delete q;
            q = p;
        }
    }
}

template  <typename DataType>
void ALGraph<DataType>  :: DFTraverse(int v)
{
    int j;
    EdgeNode *p = NULL;
    cout << adjlist[v].vertex;
    visited[v] = 1;
    p = adjlist[v].firstEdge; //工作指针p指向顶点v的边表
    while (p != NULL) //依次搜索顶点v的邻接点
    {
        j = p->adjvex;
        if (visited[j] == 0) DFTraverse(j);
        p = p->next;
    }
}

template <typename DataType>
void ALGraph<DataType> :: BFTraverse(int v)
{
    int w, j, Q[MaxSize]; //采用顺序队列
    int front = -1, rear = -1; //初始化队列
    EdgeNode *p = nullptr;
    cout << adjlist[v].vertex;
    visited[v] = 1;
    Q[++rear] = v; //被访问顶点入队
    while (front != rear) //当队列非空时
    {
        w = Q[++front];
        p = adjlist[w].firstEdge; //工作指针p指向顶点v的边表
        while (p != NULL)
        {
            j = p->adjvex;
            if (visited[j] == 0)
            {
                cout << adjlist[j].vertex;
                visited[j] = 1;
                Q[++rear] = j;
            }
            p = p->next;
        }
    }
}

int main( )
{
//测试数据是图6-20(a)，边是(0 1)(0 3)(0 4)(1 2)(2 4)(3 2)(3 4)
    char ch[ ] = {'A','B','C','D','E'};
    int i;
    ALGraph<char> ALG(ch, 5, 6); //建立具有5个顶点6条边的有向图
    for (i = 0; i < MaxSize; i++)
        visited[i] = 0;
    cout << "深度优先遍历序列是：";
    ALG.DFTraverse(0); //从顶点0出发进行深度优先遍历
    for (i = 0; i < MaxSize; i++)
        visited[i] = 0;
    cout << "广度优先遍历序列是：";
    ALG.BFTraverse(0); //从顶点0出发进行广度优先遍历
    return 0;
}

邻接矩阵

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/************************************************
邻接矩阵类MGraph的使用范例
*************************************************/
#include<iostream>
using namespace std;

const int MaxSize = 10; //图中最多顶点个数
int visited[MaxSize] = {0}; //全局数组变量visited初始化
template <typename DataType>
class MGraph
{
public:
    MGraph(DataType a[ ], int n, int e); //构造函数，建立具有n个顶点e条边的图
    ~MGraph( ) { }; //析构函数
    void DFTraverse(int v); //深度优先遍历图
    void BFTraverse(int v); //广度优先遍历图
private:
    DataType vertex[MaxSize]; //存放图中顶点的数组
    int edge[MaxSize][MaxSize]; //存放图中边的数组
    int vertexNum, edgeNum; //图的顶点数和边数
};

template<typename DataType>
MGraph <DataType>:: MGraph(DataType a[ ], int n, int e)
{
    int i, j, k;
    vertexNum = n;
    edgeNum = e;
    for (i = 0; i < vertexNum; i++) //存储顶点
        vertex[i] = a[i];
    for (i = 0; i < vertexNum; i++) //初始化邻接矩阵
        for (j = 0; j < vertexNum; j++)
            edge[i][j] = 0;
    for (k = 0; k < edgeNum; k++) //依次输入每一条边
    {
        cout << "请输入边依附的两个顶点的编号：";
        cin >> i >> j; //输入边依附的两个顶点的编号
        edge[i][j] = 1;
        edge[j][i] = 1; //置有边标志
    }
}

template<typename DataType>
void MGraph <DataType>:: DFTraverse(int v)
{
    cout << vertex[v];
    visited[v] = 1;
    for (int j = 0; j < vertexNum; j++)
        if (edge[v][j] == 1 && visited[j] == 0) DFTraverse( j );
}

template<typename DataType>
void MGraph <DataType>:: BFTraverse(int v)
{
    int w, j, Q[MaxSize]; //采用顺序队列
    int front = -1, rear = -1; //初始化队列
    cout << vertex[v];
    visited[v] = 1;
    Q[++rear] = v; //被访问顶点入队
    while (front != rear) //当队列非空时
    {
        w = Q[++front]; //将队头元素出队并送到v中
        for (j = 0; j < vertexNum; j++)
            if (edge[w][j] == 1 && visited[j] == 0 )
            {
                cout << vertex[j];
                visited[j] = 1;
                Q[++rear] = j;
            }
    }
}

int main( )
{
    int i;
    char ch[ ]= {'A','B','C','D','E'};
    /* 测试数据六条边是：(0 1)(0 2)(0 3)(0 4)(1 2)(2 4) */
    MGraph<char> MG{ch, 5, 6}; //建立具有5个顶点6条边的无向图
    for (i = 0; i < MaxSize; i++)
        visited[i] = 0;
    cout << "深度优先遍历序列是：" << endl;
    MG.DFTraverse(0); //从顶点0出发进行深度优先遍历
    for (i = 0; i < MaxSize; i++)
        visited[i] = 0;
    cout << "广度优先遍历序列是：" << endl;
    MG.BFTraverse(0); //从顶点0出发进行广度优先遍历
    return 0;
}

字典

排序

经典排序算法

img

Bubble sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
include <iostream>
using namespace std;
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void bubble_sort(T arr[], int len) {
        int i, j;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1])
                                swap(arr[j], arr[j + 1]);
}
int main() {
        int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        bubble_sort(arr, len);
        for (int i = 0; i < len; i++)
                cout << arr[i] << ' ';
        cout << endl;
        float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
        len = (float) sizeof(arrf) / sizeof(*arrf);
        bubble_sort(arrf, len);
        for (int i = 0; i < len; i++)
                cout << arrf[i] << ' '<<endl;
        return 0;
}

Selection sort

Selection sort is a simple and intuitive sorting algorithm that is O(n²) time complex no matter what data goes in. So when using it, the smaller the data size, the better. The only advantage is that it doesn’t take up extra memory space.

算法步骤

  1. First, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence.
  2. Then find the smallest (large) element from the remaining unsorted elements and put it at the end of the sorted sequence.
  3. Repeat the second step until all elements are sorted.
1
2
3
4
5
6
7
8
9
10
template<typename T>
void selection_sort(vector<T>& arr) {
    for (int i = 0; i < arr.size() - 1; i++) {
        int min = i;
        for (int j = i + 1; j < arr.size(); j++)
            if (arr[j] < arr[min])
                min = j;
        swap(arr[i], arr[min]);
    }
}

Insertion sort

The code implementation of insertion sort is not as simple and brutal as bubble sort and selection sort, but its principle should be the easiest to understand, because anyone who has played poker should be able to understand it in seconds. Insertion sort is one of the simplest and most intuitive sorting algorithms. It works by constructing an ordered sequence, and for unsorted data, scanning backward and forward in the sorted sequence to find the appropriate position and insert it.

Insertion sort, like bubble sort, also has an optimization algorithm called split-half insertion.

1
2
3
4
5
6
7
8
9
10
11
void insertion_sort(int arr[],int len){
    for(int i=1;i<len;i++){
        int key=arr[i];
        int j=i-1;
        while((j>=0) && (key<arr[j])){
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=key;
    }
}

Shell sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T>
void shell_sort(T array[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }
}

Merge sort

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
61
62
// 迭代版
template<typename T>
void merge_sort(T arr[], int len) {
    T *a = arr;
    T *b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

//递归版
void Merge(vector<int> &Array, int front, int mid, int end) {
    // preconditions:
    // Array[front...mid] is sorted
    // Array[mid+1 ... end] is sorted
    // Copy Array[front ... mid] to LeftSubArray
    // Copy Array[mid+1 ... end] to RightSubArray
    vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
    vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
    int idxLeft = 0, idxRight = 0;
    LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
    RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
    // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
    for (int i = front; i <= end; i++) {
        if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
            Array[i] = LeftSubArray[idxLeft];
            idxLeft++;
        } else {
            Array[i] = RightSubArray[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(vector<int> &Array, int front, int end) {
    if (front >= end)
        return;
    int mid = (front + end) / 2;
    MergeSort(Array, front, mid);
    MergeSort(Array, mid + 1, end);
    Merge(Array, front, mid, end);
}

Quick sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {
    if (start >= end)
        return;
    T mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) { //在整个范围内搜寻比枢纽元值小或大的元素，然后将左侧元素与右侧元素交换
        while (arr[left] < mid && left < right) //试图在左侧找到一个比枢纽元更大的元素
            left++;
        while (arr[right] >= mid && left < right) //试图在右侧找到一个比枢纽元更小的元素
            right--;
        std::swap(arr[left], arr[right]); //交换元素
    }
    if (arr[left] >= arr[end])
        std::swap(arr[left], arr[end]);
    else
        left++;
    quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
template <typename T>
void quick_sort(T arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

Time complexity

​ During the partition process, both the head and tail pointers are scanned cyclically to the last position where the base value was placed. Thus, the head and tail pointer scans together are equivalent to scanning the entire region of the array to be sorted. Therefore, we can conclude that the time complexity of a single partition operation is O(n). The formula for the overall time complexity: T(n) = n + T(L) + T®.

img

Time complexity：O(nlog⁡2n)O(n\log_{2}{n})

Optimization

One-sided recursive optimization

​ Mode：when this layer has finished the partition operation, let this layer continue to complete the partition operation to the left of the base value, while the sorting work to the right of the base value is left to the next layer of recursive functions to handle.

img

function is called 4 times.

Without the method, the actual number is 7.

1
2
3
4
5
6
7
8
9
10
11
12
void quick_sort(int *arr, int l, int r) {
    while (l < r) {
        // 进行一轮 partition 操作
        // 获得基准值的位置
        int ind = partition(arr, l, r);
        // 右侧正常调用递归函数 
        quick_sort(arr, ind + 1, r);
        // 用本层处理左侧的排序
        r = ind - 1;
    }
    return ;
}
Optimization of benchmark value selection

three-point middle method is to take the three values of the head, tail and middle elements of the sorting interval in each round, and then use the middle value after they are sorted as the base value for the current round.For example, suppose the three values of this round are 2, 9 and 7, and the middle value is 7, so the base value of this round is 7.

Partition Operation Optimization
img

Let the head pointer look backward for red elements and the tail pointer look forward for green elements, then swap the elements pointed by the head and tail pointers and repeat the process until the head and tail pointers are interleaved and stop.

Heapsort

经典问题：蚂蚁问题

假设现在有一个水平面，上面有 8 只蚂蚁排成一排。方便起见，我们给所有的蚂蚁从左到右依次编号，编号为 1 到 8。从 0 秒开始，红色蚂蚁向左爬，蓝色蚂蚁向右爬，爬行的速度都是 1m/s。如果有 2 只蚂蚁迎面碰到以后，这 2 只蚂蚁不会做任何的感情交流，而会立刻掉头向相反方向继续爬行。而爬行到桌子边沿的蚂蚁，会从桌子上掉下去。问：有哪些蚂蚁会从左边掉下去，又有哪些蚂蚁会从右边掉下去？

img

大顶堆

img