408

放上一些没头没尾的东西

数据结构

线性表

顺序表

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

#define IniSize 100
#define false 0

typedef int ElemType;

typedef struct 
{
    ElemType *data; //指示动态分配数组的指针
    int MaxSize,length; //数组中最大容量和当前个数
} SeqList;  //动态分配数组顺序表的类型定义

void initList(SeqList *L)   //初始化
{
    L->data = (ElemType*)malloc(sizeof(ElemType)*IniSize);  //动态分配
    L->length = 0;
    L->MaxSize = IniSize;
}

void ListAdd(SeqList *L, ElemType e)    //添加
{
    if(L->length == IniSize)    //当满时
        return false;
    
    L->data[L->length] = e;
    L->length++;
}

void ListInsert(SeqList *L, int i, ElemType e)  //在表中第i个位置插入指定元素e
{
    if(i<1 || i>L->length || L->length >= IniSize)  //判断i的范围有效 判断存储空间是否满
        return false;

    for(int j=L->length; j>=i; j--) //将第i个元素以及之后的元素后移
        L->data[j] = L->data[j-1];

    L->data[i-1] = e;   //在位置i处放入e
    L->length++;    //线性表长度加1
}

void ListDelete(SeqList *L, int i, ElemType e)  //删除表中第i个位置的元素 并用e返回删除元素的值
{
    if(i<1 || i>L->length)
        return false;

    e = L->data[i-1];   //将被删除元素赋值给e

    for(int j=i; j<L->length; j++)  //将第i个元素后的前移
        L->data[j-1] = L->data[j];
    
    L->length--;    //线性表长度减1
}

void LocatElem(SeqList *L, ElemType e)  //按值查找 在表中查找具有给定关键字值的元素
{
    int i;
    for(i=0; i<L->length; i++)
    {
        if(L->data[i] == e)
            return i+1; //下标为i的元素值为e 返回其位序i+1
    }

    return false;   //查找失败
}

void Reverse(SeqList *L)    //将全部元素逆置 时间复杂度为o(1)
{                           //思想：扫描前半段元素 与后半段对应位置元素互换
    ElemType t;
    for(int i=0; i<L->length/2; i++)
    {
        t = L->data[i];
        L->data[i] = L->data[L->length-i-1];
        L->data[L->length-i-1] = 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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct LNode 
{
    ElemType data;  //数据域
    struct LNode *next; //指针域
}LNode, *LinkList;

LinkList List_HeadInsert(LinkList L)    //头插法 逆向建立 读入数据与生成链表数据顺序相反
{
    LNode *s;   //指针变量
    int x;
    L = (LinkList)malloc(sizeof(LNode));    //创建头结点
    L->next = NULL; //初始为空链表

    scanf("%d", &x);    //输入值

    while(x != 9999)    //输入9999结束
    {
        s = (LNode*)malloc(sizeof(LNode));  //创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;    //将新结点插入表中 L为头指针
        scanf("%d",&x);
    }

    return L;
}

LinkList List_TailInsert(LinkList L)    //尾插法 
{
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *r = L;   //r为表尾指针   让其始终指向当前链表的尾指针

    scanf("%d", &x);    //输入结点值

    while(x != 9999)
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;  //r指向新的表尾指针
        scanf("%d", &x);
    }

    r->next = NULL; //尾结点指针置空
    return L;
}

LinkList GetElem(LinkList L, int i)   //按序号查找结点值 顺指针next域逐个往下搜索
{
    int j=1;    //计数 初始值为1
    LNode *p=L->next;   //第一个结点指针赋给p

    if(!i)
        return L;   //i为0 则返回头结点
    
    if(i<1)
        return NULL;    //i无效 返回NULL
    
    while(p && j<i) //从第一个结点开始寻找 查找第i个结点
    {
        p = p->next;
        j++;
    }

    return p;   //返回第i个结点的指针 若i大于表长则返回NULL
}

LinkList LocateElem(LinkList L, ElemType e) //按值查找表结点 较简单
{
    LNode *p=L->next;

    while(p!=NULL && p->data!=e)
        p = p->next;

    return p;
}

双链表

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct DNode    //与单链表区别在于插入与删除元素 插入删除元素均为o(1)
{
    ElemType data;  //数据域
    struct DNode  *prior, *next; //指针域 前驱和后继指针
}DNode, *DLinkList;

顺序栈

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

#define Maxsize 50
#define false 0
#define true 1

typedef char ElemType;

typedef struct  //基础版
{
    ElemType data[Maxsize]; //存放栈中元素
    int top;    //栈顶指针
} SeqStack;

void InitStack(SeqStack *S) //初始化
{
    S->top = -1;    //初始化栈顶指针
}

int StackEmpty(SeqStack S) //判栈空
{
    if(S.top == -1)
        return true;    //栈空
    else
        return false;   //非空
}

void Push(SeqStack *S, ElemType x)  //进栈
{
    if(S->top == Maxsize-1) //栈满
        return false;

    S->top++;   //指针先加1
    S->data[S->top] = x;    //入栈

    return true;
}

void Pop(SeqStack *S,ElemType *x)   //出栈 注意使用 *x
{
    if(S->top == -1)    //栈空
        return false;

    *x = S->data[S->top];   //先出栈
    S->top--;   //指针减一

    return true;
}

ElemType Gettop(SeqStack S) //取栈顶元素
{
    if(S.top == -1)
        return false;

    return S.data[S.top];
}

void BracketsCheck(ElemType str[])   //括号匹配问题
{
    SeqStack S;
    InitStack(&S);
    char ch;
    int i;

    while(str[i] != '\0')
    {
        switch (str[i])
        {
        case '{':
        case '[':
        case '(':
            Push(&S, str[i]);
            break;
        
        case '}':
            ch = Gettop(S);
            if(ch == '{')
                Pop(&S, &ch);
            else return false;
            
            break;

        case ']':
            ch = Gettop(S);
            if(ch == '[')
                Pop(&S, &ch);
            else return false;
            
            break;

        case ')':
            ch = Gettop(S);
            if(ch == '(')
                Pop(&S, &ch);
            else return false;
            
            break;
        }

        i++;
    }

    if(StackEmpty(S))
        return true;
    else return false;
}

链式队列

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

#define Maxsize 50
#define false 0
#define true 1

typedef int ElemType;

typedef struct LinkNode //链式队列结点
{
    ElemType data;
    struct LinkNode *next;
    
} LinkNode;

typedef struct  //链式队列
{
    LinkNode *front, *rear; //队列的队头和队尾指针
} LinkQueue;

void InitQueue(LinkQueue *Q)    //初始化
{
    Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));   //建立头结点
    Q->front->next = NULL;  //初始为空
}

void isEmpty(LinkQueue Q)   //判队空
{
    if(Q.front == Q.rear)
        return true;

    else return false;
}

void EnQueue(LinkQueue *Q, ElemType x)  //入队
{
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));

    s->data = x;    //创建新结点 插入到链尾
    s->next = NULL; //新结点无下个结点

    Q->rear->next = s;  //入队新结点为最后一个结点
    Q->rear = s;    //队尾指向入队新结点
}

void DeQueue(LinkQueue *Q, ElemType *x) //出队
{
    if(Q->front == Q->rear) //空队
        return false;
    
    LinkNode *p = Q->front->next;   //结点指针指向队首有效结点

    *x = p->data;   //出队结点值
    Q->front->next = p->next;   //队首结点指针指向下个结点

    if(Q->rear == p)    //若原队列中只有一个结点 删除后变空队
        Q->rear = Q->front;
    
    free(p);    //释放空间
}

循环队列

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

#define Maxsize 50
#define false 0
#define true 1

typedef int ElemType;

typedef struct
{
    ElemType data[Maxsize]; //存放队列元素
    int front, rear;    //队头指针和队尾指针
} SeqQueue;

void InitQueue(SeqQueue *Q) //初始化
{
    Q->rear = Q->front = 0; //初始化队首、队尾指针
}

void isEmpty(SeqQueue Q)    //判空
{
    if(Q.rear == Q.front)   //队空条件
        return true;
    
    else return false;
}

void EnQueue(SeqQueue *Q, ElemType x)   //入队
{
    if((Q->rear+1)%Maxsize == Q->front) //队满
        return false;

    Q->data[Q->rear] = x;
    Q->rear = (Q->rear)%Maxsize;    //队尾指针加1 取模
}

void DeQueue(SeqQueue *Q, ElemType *x)  //出队
{
    if(Q->rear == Q->front)
        return false;

    *x = Q->data[Q->front];
    Q->front = (Q->front)%Maxsize;  //队头指针加1 取模
}

串

next数组值求解和nextval数组求解

https://www.zhihu.com/question/62030859/answer/835271234

假如有这样一串字符串

1 2 3 4 5 6

a a a a a a

这可以说是一个字符串间规律最强的一个数组了吧，让我们来手动模拟一下。

首先默认第一位是0，第二位是1，从第3位开始求，比较第3-1位和next[3-1]的字符是否相同，若相同，则next[3]=next[2]+1

所以第3位的值就是2.那么依此类推就可以得到，这个字符串的next数组为

1 2 3 4 5 6

a a a a a a

0 1 2 3 4 5

总结来看就是相同就在他的next数组值加1.

那么有这样一个字符串那

1 2 3 4 5 6

a b c d e f

默认给出第1位为0 第二位为1 ，发现全都不一样,可以说毫无相关性了，所以next数组为

1 2 3 4 5 6

a b c d e f

0 1 1 1 1 1

这两种极端情况可以让大家初步了解一下计算next数组的方法，起码可以初步理解一下next数组的意义。但是这还不完善。

下面介绍一到北邮2016年考研真题

1 2 3 4 5 6 7 8

a b a a b c a c

0 1 1 2 2 3 1 2

这是一个考试常见的字符串，是如何计算的那？

第n位：next[n]的值来自于第n-1位的字符，通过跟第next[n-1]位字符比较，如果相同next[n]=next[n-1]+1,如果不相同，就跟第next[next[n-1]]位的字符比较，就这样迭代直到相同的时候，加上1，如果实在没有，就为1.

这一段话可能很难理解，逐位分析。

让我们从依次来看：

第3位：第2位和第1位比较，不相同 所以为1

第4位：第3位和第1位比较，相同，所以为2

第5位：第4位和第2位比较，不相同，和第1位比较，相同，所以为2

第6位：第5位和第2位比较， 相同，所以为3

第7位：第6位和第3位比较，不同，和第1位比较，不同，所以为1

第8位：第7位和第1位比较，相同，所以为2.

这就是next数组的手动计算方法。

接下来介绍如何根据next数组计算nextval数组

nextval是在next数组的基础上优化算法，避免不必要的浪费。其实我也不太理解nextval的具体原理，现只能介绍一下如何计算。

依旧用上面北邮的真题为例，其真题本身求的就是nextval数组

现在我们已经有了next数组：

1 2 3 4 5 6 7 8

a b a a b c a c

0 1 1 2 2 3 1 2

现在通过next数组计算nextval数组，nextval数组与next相反，是找不同，

1 2 3 4 5 6 7 8

a b a a b c a c

0 1 1 2 2 3 1 2

0 1 0 2 1 3 0 2

第1位：必为0

第2位：第2位next值为1，所以第2位和第1位比较，不同，为第2位的next 值1

第3位：第3位next值为1，所以第3位和第1位比较，相同，因为到第1位了，所以为0

第4位：第4位next值为2，所以第4位和第2位比较，不同，就为第4位next值2

第5位：第5位next值为2，所以第5位和第2位比较，相同，则继续，第2位和第1位不同，则为第2位的next值1

第6位：第6位next值为3，所以第6位和第3位比较，不同，就为第6位的next值3

第7位：第7位next值为1，所以第7位和第1位比较，相同，则为0

第8位：第8位next值为2，所以第8位和第2位比较，不同，则为第8位的next值2

【简而言之】第n位nextval数组值就是，让第n位字符和第next[n]位比较，不同，则nextval[n]=next[n],如果相同，则比较第next[next[n]]位和第next[n]位比较，如果不同，则nextVal[n]=next[next[n]].就是这样的计算方式。

树

递归二叉树

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

typedef char ElemType;

typedef struct BitNode  //二叉树结点结构
{
    ElemType data;  //数据域
    struct BitNode *lchild, *rchild;    //左右孩子指针
} BitTree;

BitTree* Creatbitree(BitTree *T)    //创建二叉树
{
    char ch;
    scanf("%c", &ch);

    if(ch == '#')
        return 0;

    T = (BitTree*)malloc(sizeof(BitTree));  //传进来的数据为树节点的指针 此句可理解为实例化该指针指向树节点
    
    T->data = ch;
    T->lchild = Creatbitree(T->lchild); //递归创建左子树
    T->rchild = Creatbitree(T->rchild); //递归创建右子树
}

void PreOrder(BitTree *T)   //先序遍历
{
    if(T)   //非空
    {
        printf("%c ", T->data); //访问根结点
        PreOrder(T->lchild);    //递归遍历左子树
        PreOrder(T->rchild);    //递归遍历右子树
    }
}

void InOrder(BitTree *T)    //中序遍历
{
    if(T)   //非空
    {
        InOrder(T->lchild); //递归遍历左子树
        printf("%c ", T->data); //访问根结点
        InOrder(T->rchild); //递归遍历右子树
    }
}

void PostOrder(BitTree *T)  //后续遍历
{
    if(T)   //非空
    {
        PostOrder(T->lchild); //递归遍历左子树
        PostOrder(T->rchild); //递归遍历右子树
        printf("%c ", T->data); //访问根结点
    }
}

非递归二叉树(需借助栈和队列结构)

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define Maxsize 50
#define false 0

typedef char ElemType;

typedef struct BitNode  //二叉树结点结构
{
    ElemType data;  //数据域
    struct BitNode *lchild, *rchild;    //左右孩子指针
} BitTree;

typedef struct 
{
    BitTree *link;
    int flag;
} SeqStack;

BitTree* Creatbitree(BitTree *T)    //创建二叉树
{
    char ch;
    scanf("%c", &ch);

    if(ch == '#')
        return 0;

    T = (BitTree*)malloc(sizeof(BitTree));  //传进来的数据为树节点的指针 此句可理解为实例化该指针指向树节点
    
    T->data = ch;
    T->lchild = Creatbitree(T->lchild); //递归创建左子树
    T->rchild = Creatbitree(T->rchild); //递归创建右子树
}

void PreOrder(BitTree *T)   //先序遍历
{
    BitTree *p,*stack[Maxsize];
    int top;    //栈顶

    top = 0;
    p = T;  //p用于存储移动的指针的变量

    if(!T)  //栈空则返回
        return 0;
    
    while(p && top) //当根结点与栈均不为空时
    {
        while(p)    //深入左子树
        {
            printf("%c ", p->data);

            if(top <= Maxsize-1)
                stack[++top] = p;   //入栈 栈顶指针先+1
            else return false;

            p = p->lchild;  //深入当前结点左子树
        }

        if(top <= 0)
            return false;
        else
        {
            p = stack[top--];   //出栈后指针-1
            p = p->rchild;  //指向右子树
        }
    }  
}

void InOrder(BitTree *T)   //中序遍历
{
    BitTree *p,*stack[Maxsize];
    int top;    //栈顶

    top = 0;
    p = T;  //p用于存储移动的指针的变量

    if(!T)  //栈空则返回
        return 0;

    while(p && top) //当根结点与栈均不为空时
    {
        while(p)    //深入左子树
        {
            printf("%c ", p->data);

            if(top <= Maxsize-1)
                stack[++top] = p;   //入栈 栈顶指针先+1
            else return false;

            p = p->lchild;  //深入当前结点左子树
        }

        if(top <= 0)
            return false;
        else
        {
            p = stack[top--];   //出栈后指针-1
            printf("%c ", p->data);
            p = p->rchild;  //指向右子树
        }
    }
}

void PostOrder(BitTree *T)  //后序遍历(使用栈辅助)
{   //后序遍历中每个结点需要出入栈两次 应该访问哪一次出栈的值
    //解决方法 设置一个flag变量 为1时为第一次出栈 不访问 为2时为第二次出栈 访问
    SeqStack stack[Maxsize];
    BitTree *p;
    int top, sign;

    top = -1;   //因为使用栈 所以栈顶指针设为-1
    p = T;  //p用于存储移动的指针的变量

    if(!T)
        return false;

    while(p && top!=-1)
    {
        if(p)
        {
            stack[++top].link = p;  //入栈
            stack[top].flag = 1;    //第一次入栈 flag=1
            p = p->lchild;  //深入左子树
        }

        else
        {
            sign = stack[top].flag;
            p = stack[top--].link;  //出栈

            if(sign == 1)   //判断是否为第一次出栈
            {
                stack[++top].link = p;  //入栈
                stack[top].flag = 2;
                p = p->rchild;  //深入右子树
            }

            else
            {
                printf("%c ", p->data);
                p = NULL;
            }
        }
    }
}

void LevelOrder(BitTree *T) //层序遍历(使用队列辅助)
{
    BitTree *p, *queue[Maxsize];    //用一维数组表示队列结构
    int front, rear;    //front-队头指针 rear-队尾指针
    front = rear = 0;   //初始化

    if(T)
    {
        queue[rear++] = T;  //根节点入队

        while(front != rear)    //队列非空时
        {
            p = queue[front++]; //队首元素出队
            printf("%c ", p->data); //访问

            if(p->lchild)
                queue[rear++] = p->lchild;  //左子树非空则入队
            
            if(p->rchild)
                queue[rear++] = p->rchild;  //右子树非空则入队
        }
    }
}

排序

插入排序

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

typedef int ElemType;

void InsertSort1(ElemType A[], int n)//直接插入排序
{                                    //空间：o(1)
    int i,j;                         //时间：o(n²)
    
    for(i=2; i<=n; i++)//依次将A[2]~A[n]插入前面已排序序列
    {
        if(A[i]<A[i-1])//若A[i]关键码小于其前驱 将A[i]插入有序表
        {
            A[0] = A[i];//复制为哨兵 A[0]不存放元素

            for(j=i-1; A[0]<A[j]; --j)//从后往前查找待插入位置
                A[j+1] = A[j];//向后挪位

            A[j+1] = A[0];//复制到插入位置
        }
    }
}

void InsertSort2(ElemType A[], int n)//折半插入排序
{                                    //比较次数：o(nlog₂n)
    int i,j,low,high,mid;            //时间：o(n²)

    for(i=2; i<=n; i++)//依次将A[2]~A[n]插入前面的已排序序列
    {
        A[0] = A[i];//将A[i]暂存A[0]
        low = 1;//设置折半查找范围
        high = i-1;

        while(low<=high)//折半查找
        {
            mid = (low+high)/2;//取中间点

            if(A[mid>A[0]])
                high = mid-1;//查找左子表
            else low = mid+1;//查找右子表
        }

        for(j=i-1; j>=high+1; --j)
            A[j+1] = A[j];//统一后移元素 空出插入位置

        A[high+1] = A[0];//插入
    }
}

void ShellSort(ElemType A[], int n)//希尔排序
{                                  //空间：o(1)
    int i,j,dk;                    //时间：o(n)~o(n²)

    for(dk=n/2; dk>=1; dk=dk/2)//步长变化
    {
        for(i=dk+1; i<=n; ++i)
        {
            if(A[i]<A[i-dk])//需将A[i]插入有序增量子表
            {
                A[0] = A[i];//暂存

                for(j=i-dk; j>0&&A[0]<A[j]; j-=dk)
                    A[j+dk] = A[j];//记录后移 查找插入位置

                A[j+dk] = A[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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef int ElemType;

int Partition(ElemType A[], int low, int high)//快速排序进行一次划分
{
    ElemType pivot = A[low];//默认将表中第一个元素设置为枢轴 对表进行划分

    while(low<high)//循环跳出条件
    {
        while(low<high && A[high]>=pivot)
            --high;//找到比枢轴小的值
        A[low] = A[high];//将比枢轴小的元素移到左端

        while(low<high && A[low]<=pivot)
            ++low;//找到比枢轴大的值
        A[high] = A[low];//将比枢轴大的元素移到右端
    }

    A[low] = pivot;//枢轴元素存放到最终位置
    return low;//返回存放枢轴的位置
}

void QuickSort(ElemType A[], int low, int high)//快速排序(递归)
{                                              //空间：o(log₂n)
    if(low<high)//递归跳出条件                   //时间：o(n²)
    {
        int pivotpos = Partition(A,low,high);
        
        QuickSort(A,low,pivotpos-1);//依次对两个子表进行递归排序
        QuickSort(A,pivotpos+1,high);
    }
}

选择排序

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

typedef int ElemType;

void AdjustMaxHeap(ElemType A[], int target, int n)//构造大根堆
{
    int i = target;//target为需要调整的非叶子节点
    int j = 2*i+1;
    int temp = A[i];

    while(j<=n)
    {
        if(j<n && A[j]<A[j+1])//找出左右孩子的最大值
            j++;

        if(temp<A[j])//不满足大根堆则交换元素值
        {
            A[i] = A[j];
            i = j;
            j = 2*j+1;
        }
        else break;
    }

    A[i] = temp;//被筛选结点值放入最终位置
}

void HeadSort(ElemType A[], int n)//堆排序
{                                 //空间：o(1)
    int i;                        //时间：o(nlog₂n)
    int temp;

    for(i=n/2-1; i>=0; i--)//构造大根堆 元素从0开始
        AdjustMaxHeap(A, i, n-1);

    for(i=n-1; i>0; i--)//取堆顶元素 重新构造新堆 共n-1趟
    {
        temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        AdjustMaxHeap(A, 0, i-1);//把剩余i-1个元素整理成堆
    }
}