# 数据结构与算法 (DataStructureAndAlgorithms)

# 注意事项

  1. 该笔记使用 C++、开发环境为 VS2022
  2. 该笔记较少使用大量书面语言和数学证明去描述一些算法，因此不适合正规入门使用，也不适合考试使用

# TestArrCreate

作用：生成一个测试数组，用于测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//头文件
#pragma once
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<vector>
using namespace std;
class testArr
{
public:
	testArr();
	~testArr();

	int* arr;
	int arrLen;
	void createArr();
	void printArr();
};
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
//源文件
#include "testArr.h"

void testArr::createArr() {
	this->arrLen = rand() % 5 + 5;//长度为5-10
	this->arr = (int*)malloc(this->arrLen * 4);
	for (int i = 0; i < this->arrLen; i++) {
		arr[i] = rand() % 300;
	}
}

testArr::testArr() {
	srand((unsigned)time(NULL));
	this->createArr();
}

testArr::~testArr() {
	if (this->arr != NULL) {
		delete[] this->arr;
		this->arr = NULL;
	}
}

void testArr::printArr() {
	for (int i = 0; i < this->arrLen; i++) {
		cout << this->arr[i] << " ";
	}
}

# 算法、复杂度：

算法 (Algorithm) 是为了解决某类问题而规定的一个有限长的操作序列。

一个算法必须满足以下五个重要特性：

(1) 有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。

(2) 确定性。对千每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性， 使算法的执行者或阅读者都能明确其含义及如何执行。

(3) 可行性。算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。

(4) 输入。一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的， 在它们被调用时，从主调函数获得输入值。

(5) 输出。

复杂度包括：时间复杂度与空间复杂度，通常我们更加看重一个算法的时间复杂度。

拿算法中最经典的高斯算法为例：

求 1~n 的和，有常规的算法：循环实现，与高斯算法，下面是代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
//常规实现：
#include<iostream>
using namespace std;
int main() {
	int n = 100;
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		sum += i;
	}
	cout << sum;
	return 0;
}
1
2
3
4
5
6
7
8
9
//高斯算法实现
#include<iostream>
using namespace std;
int main() {
	int n = 100;
	int sum = (1 + n) * n / 2;
	cout << sum;
	return 0;
}

我们可以注意到，当使用常规算法时，需要执行的语句数会随着整数 n 的变化而变化，成线性相关，当 n 为一万时，那么 sum+=i; 这条语句需要执行的次数就是一万次。而使用高斯算法时，无论 n 的值是多少，sum = (1 + n) * n / 2; 都只会执行一次。

假设每条语句的执行时间都相同，设为 1，则使用常规算法消耗的时间大致可以认为是 n*1，高斯算法消耗的时间大概是 1。

我们通常使用大 O 表示法，来表示一个算法的复杂度，这里可以写为：常规算法 O (n)，高斯算法 O (1)

需要注意的是，若是算法中使用了两个循环 (非嵌套)，执行了 2n 条语句，我们仍然记为 O (n)

又或者使用了 2，3，4 条语句，只要这个算法的代码实现并不会随 n 变动，我们仍然记为 O (1)

因此，O (2n)，O (3n)，O (5)，这些形式都是错误的。通常有以下几种表达式来描述时间复杂度：

  • O (1)：常量阶
  • O (log n)：对数阶
  • O (n)：线性阶
  • O (n log n)：线性对数阶
  • O(n2)：二次方阶
  • O(2n)：指数阶
  • O (!n)：阶乘阶

对于一个算法，比如排序一组数据：

1
int arr[] = {1, 3, 5, 10, 9};

对于这组数据，显然只需要排序一次便能够得到有序数组，但是这并不代表使用的排序算法就是 O (1) 阶的，我们要按照最差的情况来估计，如果是冒泡排序，我们要按照每一次都需要排序来估计，第一次到第 n 次需要的执行的次数分别为 n-1 到 1，所以总执行次数为 n * (n - 1) / 2 也就是 1/2 * n^2 + 1/2 * n - 1/2 次，我们仅取其最大的部分，则冒泡排序的时间复杂度为 O (n2) 阶。

冒泡排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
void maoPao(int* arr, int arrLen) {
	for (int i = arrLen; i > 0; i--) {
		for (int j = 0; j < i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

int main() {
	int arr[] = { 10, 9, 5, 3, 1 };
	maoPao(arr, 5);
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << "\t";
	}
	return 0;
}

# 存储结构：

存储结构大致可以分为两类：

  1. 顺序结构：在物理内存中连续，并且在逻辑顺序上也连续。
  2. 链式结构：包含数据域与指针域，在物理内存中不一定连续，但在逻辑顺序上连续。

其中，数据域用于存储数据，指针域用于存储后继元素的地址。

如图：

顺序结构与链式结构图

由图可以直观的看出二者的差别。

顺序结构与链式结构比较：

顺序结构的数据存储密度更高，占用空间更少，但是需要一段连续的空间。

链式结构由于需要使用指针域保存与其关联的节点的地址，所以数据存储密度相对低，占用空间更多，但是由于分布存储的特点，并不需要一段连续的空间。

顺序结构的插入与删除更加繁琐，时间复杂度为 O (n)，但是顺序结构的修改，时间复杂度为 O (1)

链式结构的插入与删除，时间复杂度为 O (1)，但是查找数据和修改数据，时间复杂度为 O (n)

# 线性结构：

# 线性表 (List)

线性表（List）：零个或多个数据元素的有限序列。

线性表的数据集合为 {a1,a2,…,an}，假设每个元素的类型均为 DataType。其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 an 外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件

# 使用 C++ 实现顺序表：

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
//list.hpp
#pragma once
#include<iostream>
using namespace std;
template<class T>
class List
{
private:
	T* box;//容器
	int m_size;
	int m_capacity;

public:
	List() {//构造函数
		this->m_capacity = 2;
		this->m_size = 0;
		this->box = new T[this->m_capacity];
	}
		
	~List() {//析构函数
		if (this->box != NULL) {
			delete[] this->box;
			this->box = NULL;
		}
	}

	//这里仅提供部分方法用于学习，练习，C++的STL中的List更完善
	void push_front(T val) {//头插法
		if (this->m_size == this->m_capacity) {
			this->m_capacity *= 2;
			T* temp = new T[this->m_capacity];
			for (int i = 0; i < this->m_size; i++) {
				temp[i] = this->box[i];
			}
			delete[] this->box;
			this->box = temp;
		}
		for (int i = this->m_size; i > 0; i--)
			this->box[i] = this->box[i - 1];
		this->box[0] = val;
		this->m_size++;
	}

	void push_back(T val) {//尾插法
		if (this->m_size == this->m_capacity) {
			this->m_capacity *= 2;
			T* temp = new T[this->m_capacity];
			for (int i = 0; i < this->m_size; i++) {
				temp[i] = this->box[i];
			}
			delete[] this->box;
			this->box = temp;
		}
		this->box[this->m_size] = val;
		this->m_size++;
	}

	void insert(int index, T val) {//间插法
		if (this->m_size == this->m_capacity) {
			this->m_capacity *= 2;
			T* temp = new T[this->m_capacity];
			for (int i = 0; i < this->m_size; i++) {
				temp[i] = this->box[i];
			}
			delete[] this->box;
			this->box = temp;
		}
		for (int i = this->m_size; i > index; i--)
			this->box[i] = this->box[i - 1];
		this->box[index] = val;
		this->m_size++;
	}

	void popByIndex(int index) {//通过下标删除元素
		if (index < 0 || index > this->m_size) {
			cout << "Index error" << endl;
			return;
		}
		for (int i = index; i < this->m_size - 1; i++) {
			this->box[i] = this->box[i + 1];
		}
		this->m_size--;
	}

	int size(){//返回容器内元素数
		return this->m_size;
	}

	int capacity(){//返回容器容量
		return this->m_capacity;
	}

	bool isEmpty() {//判断容器内是否为空
		if (this->m_size == 0)
			return true;
		return false;
	}

	int findByElem(T Elem) {//通过元素本身查找,并返回其下标,未找到返回-1
		int index = -1;
		for (int i = 0; i < this->m_size; i++) {
			if (this->box[i] == Elem) {
				index = i;
				break;
			}
		}
		return index;
	}

	T getElemByIndex(int index) {//通过下标获取元素
		if (index < 0 || index > this->m_size) {
			cout << "Index error.Return head element!" << endl;
			return this->box[0];
		}
		return this->box[index];
	}

	void clear() {//清空容器内所有元素
		this->m_size = 0;
	}
};

main 函数调试

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
//main.cpp
#include<iostream>
#include"List.hpp"
#include"testArr.h"
using namespace std;

int main() {
	testArr ta;
	List<int> list;
	for (int i = 0; i < ta.arrLen; i++) {
		list.push_front(ta.arr[i]);//头插测试
	}

	for (int i = 0; i < ta.arrLen; i++) {
		list.push_back(ta.arr[i]);//尾插测试
	}

	for (int i = 0; i < list.size(); i++) {
		cout << list.getElemByIndex(i) << "\t";//获取元素测试
	}
	cout << "\n";
	list.popByIndex(0);//删除测试

	for (int i = 0; i < list.size(); i++) {
		cout << list.getElemByIndex(i) << "\t";
	}
	cout << "\n";
	list.insert(1, 100);//间插测试

	for (int i = 0; i < list.size(); i++) {
		cout << list.getElemByIndex(i) << "\t";
	}

	cout << "\n";
	list.clear();//清空测试
	if (list.isEmpty()) {//判断是否为空测试
		cout << "已清空" << endl;
	}
	return 0;
}

# 使用 C++ 实现单链表：

单链表指指针域中仅仅保存单方向指向后继节点的指针的链式存储线性表。

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
//Link.hpp
//该链表并未提供间插法
#pragma once
#include<iostream>
using namespace std;

template<class T>
class Node {//节点
public:
	T data;
	Node* next;
public:
	Node(T value) {//构造
		this->data = value;
		this->next = NULL;
	}
	~Node() {//析构
		if (this->next != NULL) {
			delete this->next;
			this->next = NULL;
		}
	}
};

template<class T>
class Link {//链表头
private:
	//T data;
	Node<T>* next;
	int size;
	Node<T>* end;
	
public:
	Link() {//构造函数
		this->next = NULL;
		this->end = NULL;
		this->size = 0;
	}
	~Link() {//析构函数
		this->next = NULL;
		this->end = NULL;
	}

	void push_front(T value) {//头插
		if (this->size == 0) {
			this->next = new Node<T>(value);
			this->end = this->next;
			this->size++;
			return;
		}
		Node<T>* newNode = new Node<T>(value);
		newNode->next = this->next;
		this->next = newNode;
		this->size++;
	}

	void push_back(T value) {//尾插
		if (this->size == 0) {
			this->next = new Node<T>(value);
			this->end = this->next;
			this->size++;
			return;
		}
		this->end->next = new Node<T>(value);
		this->end = this->end->next;
		this->size++;
	}

	Node<T>* find(T key) {//查找，并返回该节点
		Node<T>* p = this->next;
		for (int i = 0; p != NULL; p = p->next) {
			if (p->data == key) {
				return p;
			}
		}
		return NULL;
	}

	void pop_back() {//尾删
		if (this->size == 0) {
			return;
		}
		Node<T>* np = this->next;
		if (np == this->end) {
			this->next = NULL;
			this->end = NULL;
			this->size--;
			return;
		}
		for (; np->next != end; np = np->next);
		np->next = NULL;
		this->end = np;
		this->size--;
	}

	void pop_front() {//头删
		if (this->size == 0) {
			return;
		}
		this->next = this->next->next;
		this->size--;
	}

	void pop_Node(Node<T>* node) {//根据查找返回节点删除
		if (node == NULL) {
			cout << "pop error!" << endl;
			return;
		}
		for (Node<T>* np = this->next; np->next != NULL; np = np->next) {
			if (np->next == node) {
				np->next = np->next->next;
			}
		}
	}

	void printLink() {//打印链表
		for (Node<T>* p = this->next; p != NULL; p = p->next) {
			cout << p->data << "\t";
		}
	}

	void clearLink() {//清空链表
		this->next = NULL;
		this->end = NULL;
		this->size = 0;
	}
};

main 函数调试

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
//main.cpp
#include<iostream>
#include"Link.hpp"
#include"testArr.h"
using namespace std;

int main() {
	testArr ta;
	Link<int> link;
	//尾插测试
	for (int i = 0; i < ta.arrLen; i++) {
		link.push_back(ta.arr[i]);
	}
	//头插测试
	for (int i = ta.arrLen - 1; i > -1; i--) {
		link.push_front(ta.arr[i]);
	}
	link.printLink();
	cout << "\n";
	//按节点删除，与查找测试
	link.pop_Node(link.find(2));
	//头删测试
	link.pop_front();
	//尾删测试
	link.pop_back();
	link.printLink();
	cout << "\n";
	//清空链表测试
	link.clearLink();
	link.printLink();
	return 0;
}

# 栈 (Stack)

特点: 先进后出 (FILO)(First in Last out)

栈的结构类似于电梯，先进去的元素会在栈底，后进去的元素会在栈顶，后进的元素会先出，先进的元素会后出。

如下图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20


|		|	(栈顶)	
|		|
|		|
|		|
---------	(栈底)

|
|	(存入数据时)
|
V

|		|	DATA1先入栈，在栈底
|		|	DATA2后入栈，在栈顶
| DATA2	|	DATA2会先出栈
| DATA1	|	随后DATA1才能出栈
---------


# 使用 C++ 实现顺序栈：

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
#pragma once
#include<iostream>
#include<stdlib.h>
using namespace std;

template<class T>
class Stack
{
private:
	int size;//记录栈内元素个数
	int len;//记录栈容量
	T* stack;//栈底
public:
	Stack() {
		this->len = 2;
		this->size = 0;
		this->stack = new T[this->len];
	}
	Stack(int len) {
		this->len = len;
		this->size = 0;
		this->stack = new T[this->len];
	}
	~Stack() {
		delete[] this->stack;
		this->stack = nullptr;
	}
	int IsEmpty() {
		if (this->size == 0)
			return 1;//栈空返回1
		return 0;//栈非空返回0
	}
	int Size() {
		return this->size;
	}
	T GetTop() {
		return this->stack[this->size - 1];
	}
	void Push(T val) {
		//如果栈满了，则扩栈
		if (this->size == this->len) {
			this->len *= 2;
			T* newSpace = new T[this->len];
			for (int i = 0; i < this->size; i++) {
				newSpace[i] = this->stack[i];
			}
			
			delete[] this->stack;
			this->stack = newSpace;
		}
		
		this->stack[this->size] = val;
		this->size++;
	}
	void Pop() {
		if (this->IsEmpty())
			return;
		this->size--;
	}
};

main 函数调试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include"Stack.hpp"
#include"testArr.h"
using namespace std;

int main() {
	testArr ta;
	Stack<int> s;
	ta.printArr();//打印数组便于比较数据
	cout << endl;
	//入栈
	for (int i = 0; i < ta.arrLen; i++) {
		s.Push(ta.arr[i]);
	}
	//获取栈顶和出栈
	for (int i = 0; i < ta.arrLen; i++) {
		cout << s.GetTop() << "\t";
		s.Pop();
	}
	return 0;
}

# 使用 C++ 实现链栈：

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
#pragma
#include<iostream>
#include<cstdlib>
using namespace std;

template<class T>
class StackNode {
public:
	T data;//存储数据
	StackNode<T>* prior;//指向前节点
	StackNode(T val, StackNode* node = nullptr) {
		this->data = val;
		this->prior = node;
	}
	~StackNode() {};
};

template<class T>
class LinkStack {
private:
	StackNode<T>* top;//栈顶
	int size;//栈内元素数
public:
	LinkStack() {
		this->size = 0;
		this->top = nullptr;
	}
	int IsEmpty() {
		if (this->size == 0)
			return 1;
		return 0;
	}
	int Size() {
		return this->size;
	}
	T GetTop() {
		return this->top->data;
	}
	void Push(T val) {
		//创建新节点，并把其前指针指向当前的top
		StackNode<T>* sn = new StackNode<T>(val, this->top);
		//top改变
		this->top = sn;
		this->size++;
	}
	void Pop() {
		//如果栈空，直接返回
		if (this->IsEmpty())
			return;
		StackNode<T>* deln = this->top;
		this->top = this->top->prior;
		delete deln;
		this->size--;
		deln = nullptr;
	}
	~LinkStack() {
		//弹出直到栈空
		while (this->top)
			this->Pop();
	}
};

main 函数调试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include"LinkStack.hpp"
#include"testArr.h"
using namespace std;

int main() {
	testArr ta;
	LinkStack<int> ls;
	ta.printArr();//打印数组便于比较数据
	cout << endl;
	//入栈
	for (int i = 0; i < ta.arrLen; i++) {
		ls.Push(ta.arr[i]);
	}
	//获取栈顶和出栈
	for (int i = 0; i < ta.arrLen; i++) {
		cout << ls.GetTop() << "\t";
		ls.Pop();
	}
	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
#include <iostream>
#include "Stack.hpp"

using namespace std;

int main()
{
    /*使用栈将十进制数转换为二进制数*/

    int number = 180;

    Stack<int> stack;
    while (number != 0) {
        stack.Push(number % 2);
        number /= 2;
    }
    int stackLength = stack.Size();
    for (int i = 0; i < stackLength; i++) {
        if (i % 4 == 0)
            cout << " ";
        cout << stack.GetTop();
        stack.Pop();
    }
}

# 队列 (Queue)

特点: 先进先出 (FIFO)(First in First out)

类似于排队。仅能从队尾进入，队首离开。

# 使用 C++ 实现顺序循环队列：

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
#pragma once
#include<iostream>
#include<cstdlib>

using namespace std;

template<class T>
class Queue {
private:
	T* queue;
	int head;//头指针
	int rear;//尾指针
	int size;//记录队列内元素数
	int len;//记录队列长度
public:
	Queue() {
		this->len = 2;
		this->size = 0;
		this->head = this->rear = 0;
		this->queue = new T[this->len];
	}
	Queue(int len) {
		this->len = len;
		this->size = 0;
		this->head = this->rear = 0;
		this->queue = new T[this->len];
	}
	void Push(T val) {
		//如果队满，扩队
		if (this->len == this->size) {
			int length = this->len;
			this->len *= 2;
			T* newSpace = new T[this->len];
			int newIndex = this->head;
			int index = this->head;
			for (int i = 0; i < this->size; i++) {
				newSpace[newIndex] = this->queue[index];
				newIndex = (newIndex + 1) % this->len;
				index = (index + 1) % length;
			}
			delete[] this->queue;
			this->queue = newSpace;
			this->rear = newIndex;
		}
		//将数据存入队尾
		this->queue[this->rear] = val;
		//尾指针+1，使用循环队列，所以对队列长度求余
		this->rear = (this->rear + 1) % this->len;
		this->size++;
	}
	int IsEmpty() {
		if (this->size == 0)
			return 1;
		return 0;
	}
	T GetTop() {
		return this->queue[head];
	}
	int Size() {
		return this->size;
	}
	void Pop() {
		//队空，则直接返回
		if (IsEmpty())
			return;
		//头指针后移，使用循环队列，所以对队列长度求余
		this->head = (this->head + 1) % this->len;
		this->size--;
	}
};

main 函数调试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include"Queue.hpp"
#include"testArr.h"
using namespace std;

int main() {
	testArr ta;
	Queue<int> q;
	ta.printArr();//打印数组便于比较数据
	cout << endl;
	//入栈
	for (int i = 0; i < ta.arrLen; i++) {
		q.Push(ta.arr[i]);
	}
	//获取栈顶和出栈
	for (int i = 0; i < ta.arrLen; i++) {
		cout << q.Front() << "\t";
		q.Pop();
	}
	return 0;
}

# 使用 C++ 实现链式队列：

1

# 队列：热土豆问题：

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
/*
使用队列结构完成热土豆问题：
热土豆问题(约瑟夫问题、击鼓传花)：
从第1个人将热土豆向后传，选择一个数number，当热土豆传递到第number次时，持有热土豆的人离队，直到队列中只剩一人
解决思路：
1.热土豆不需要传递，只需将热土豆始终标记在队首
2.将队首移除加入队尾，视作一次传递
3.当传递到number次时，将队首永久移除
4.重复直至仅剩一人
*/

//程序实现：
#include<iostream>
#include"Queue.hpp"
#include"testArr.h"
using namespace std;

int main() {
    Queue<string> q;
    string seed[] = { "张三", "李四", "王五", "老六", "头七", "老八", "九哥" };
    //最终结果应该为：头七、王五、李四、老刘、九哥、张三、老八
    for (int i = 0; i < 7; i++) {
        q.Push(seed[i]);
    }

    int number = 5;//假设number为5
    while (!q.IsEmpty()) {
        for (int i = 1; i < number; i++) {
            string temp = q.Front();
            q.Pop();
            q.Push(temp);
        }
        cout << q.Front() << endl;
        q.Pop();
    }
    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
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
	/*
    打印任务问题：
    一个实验室，在任意的一个小时内，大约有10名学生在场，
    这一个小时中，每个人会发起2次左右打印，每次1~20页。
    打印机的性能：
    以草稿模式打印：每分钟10页
    以正常模式打印：打印质量更高，每分钟5页

    如何设定打印机的模式，让所有人都不会等太久的前提下尽量提高打印质量?
    */

    /*
    问题思路：

    对象：打印任务、打印队列、打印机
    打印任务属性：提交时间、打印页数
    打印队列属性：具有FIFO性质的打印任务队列
    打印机属性：打印速度、工作状态(是否正忙)

    过程：
    1.生成和提交打印任务
    生成概率：每小时会有10个学生提交共计20个打印任务，约为每180秒提交一个打印任务
    则生成一份打印任务的概率为  (1/180) 每秒

    2.打印页数：页数为1~20之间的概率相同

    3.实施打印：当前正在进行的打印任务
    打印结束倒计时：新任务开始时进行倒计时，倒计时为0时打印完毕，执行下一打印任务

    4.模拟时间：
    统一的时间框架：以统一最小单位(秒)均匀流逝的时间，设定结束时间
    同步所有过程：在一个时间单位里，对生成打印任务和实施打印两个过程各处理一次
    */

//打印机头文件
#pragma once
#include<iostream>
using namespace std;

class PrintProblem
{
public:
	bool free;//打印机状态
	float speed;//打印机打印速度
public:
	PrintProblem(int type);
	void printType(int type);
};
//打印机源文件
#include "PrintProblem.h"
PrintProblem::PrintProblem(int type) {
	if (type == 1) this->speed = 10.0 / 60;
	else this->speed = 5.0 / 60;
	this->free = true;
}

void PrintProblem::printType(int type) {
	if (type == 1) this->speed = 10.0 / 60;
	else this->speed = 5.0 / 60;
}

//main文件
#include<iostream>
#include<queue>
#include<ctime>
#include<cstdlib>
#include"PrintProblem.h"
using namespace std;

struct printTask {//打印任务结构体
    int startTime;//开始时间
    int printTime;//打印时间
    int printPage;//打印页数
};

int main()
{
    int flag = 0;//模拟时间，单位秒
    srand((unsigned)time(NULL));
    queue<struct printTask> printQueue;//该队列用于存储打印任务
    PrintProblem printer(1);//模式1为草稿模式，模式2为正常模式
    queue<int> waitTime;//完成任务所需时间

    while (flag < 3600) {
        
        if (rand() % 180 == 0) {//生成打印任务并加入打印队列
            struct printTask newTask;
            newTask.printPage = rand() % 20 + 1;
            newTask.startTime = flag;
            newTask.printTime = ceil(newTask.printPage / printer.speed);            
            printQueue.push(newTask);
        }
        
        if (!printQueue.empty() && printer.free) {//开始打印任务
            printer.free = false;
        }

        if (!printer.free) {//执行打印任务
            printQueue.front().printTime--;
            if (printQueue.front().printTime <= 0) {
                printer.free = true;
                int finishTime = flag;
                waitTime.push(finishTime - printQueue.front().startTime);
                printQueue.pop();
            }
        }
        flag++;
    }

    float average = 0.0f;
    int length = waitTime.size();

    for (int i = 0; i < length; i++) {
        average += waitTime.front();
        waitTime.pop();
    }

    cout << "平均等待时间" << (average / length) << "s" << "还有" << printQueue.size() << "个打印任务未完成" << endl;
    return 0;
}

# 双端队列 (Deque)

# C++ 提供的双端队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//C++提供的双端队列位于头文件<deque>中
#include<iostream>
#include<deque>
using namespace std;
int main(){
    deque<type> dequeName;
    //下面为deque的方法
    push_back();//在队列尾部添加元素，无返回值。
	push_front();//在队列头部添加元素，无返回值；
	pop_back();//删除队列尾部的元素，无返回值；
	pop_front();//删除队列头部的元素，无返回值；
	front();//获得队列头部元素。
	back();//获得队列尾部元素。
	size();//获得队列大小。
	empty();//判断队列是否为空。队列空：返回true；不空：返回false。
    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
/*
“回文词”：指正读反读都一样的词，如：abccba
*/
#include <iostream>
#include<cstring>
#include<deque>
using namespace std;
/*使用双端队列判断回文词*/
int main()
{
    deque<string> dQ;
    string huiWen[] = { "上","海","自","来","水","来","自" ,"海", "上" };
    int len = sizeof(huiWen) / sizeof(huiWen[0]);
    for (int i = 0; i < len; i++) {
        dQ.push_front(huiWen[i]);
    }
    len = dQ.size() / 2;
    bool judge = true;
    for (int i = 0; i < len; i++) {
        if (dQ.front() == dQ.back()) {
            dQ.pop_front();
            dQ.pop_back();
        }
        else judge = false;
    }
    if (judge) cout << "该string为回文" << endl;
    else cout << "该string不是回文" << endl;
    return 0;
}

# 散列表 (Hash Table / 哈希表)

创建一个存储空间，每个位置有对应的槽号，将数据存储后，只需要通过槽号进行读取。

则可以实现时间复杂度为 O (1) 的查找速度。

我们将数据项占据的比例称为散列表的 "负载因子"。例如：

某散列表大小为 11，存储项共 6 个，则其负载因子为 6/11

冲突：指两项数据，通过散列函数计算后，得到相同的 Hash 值

# 散列函数

(1) 求余散列函数：

假设散列表的总大小为 size，要存储的数据项为 item，则可以使用 h (item) = item % size

其中 h (item) 为 item 对应的存储槽号。若冲突，则将槽号向后顺延。

(2) 折叠散列函数：

将数据项按照位数分为若干段，再将几段数字相加，最后使用散列表大小求余，得到散列值。

(3) 平方取中散列函数：

先将数据项做平方运算，然后取平方数的中间两位。再对散列表大小求余。

# MD5 与 SHA

MD5 与 SHA 都是为了实现散列表槽位计算而出现的散列表函数。

将任意数据进行 MD5 或 SHA 计算后，会获得相应的散列值 (MD5 计算出的 Hash 值为 128 位，SHA0 计算出的 Hash 值为 160 位)

使用 MD5 或 SHA 计算出的 Hash 值几乎不存在冲突的可能。

# 区块链技术

区块链的发展得益于散列函数。

区块链是大规模的分布式数据库。

区块链的最本质特征是 "去中心化"。不存在任何控制中心、协调中心节点。所有的节点都是平等的，无法被控制。

区块链由一个个区块 (block) 组成，区块分为头 (head) 和体 (body)。

区块头记录了一些元数据和链接到前一个区块的信息：生成时间、前一个区块的散列值。

工作量证明 (Proof of Work):

由于区块链是大规模的分布式数据库，同步较慢，新区快的添加速度需要得到控制。

目前最大规模区块链 Bitcoin (比特币) 采用的速度是平均每 10 分钟生成一个区块。

# 处理冲突

(1) 开放地址

将冲突的数据项向后顺延，或者跳跃式顺延。

如 data1 和 data2 同样对应 0，则 data1 存于 0，data2 顺延存于 1。

但是这种顺延方式，若是冲突较多，则会导致冲突数据大量集中。

因此可以采取跳跃式顺延解决。

如 data1 存于 0，data2 存于 0+skip，skip 可以是任意不可以整除表大小的数。如果 skip 可以整除表，则会有部分槽永远不会被顺延。

(2) 数据链

将槽位的存储空间扩大。

如 data1 和 data2 同样对应 0，则使用数组等方式，将之一起存入 0 槽位。

查找时使用顺序查找的方式，从而获取数据项。这是介于 O (1) 和 O (n) 之间的选择。

# C++ 提供的 map 类

map 是 STL 的一个关联容器，它提供一对一的 hash。

​ 第一个可以称为关键字 (key)，每个关键字只能在 map 中出现一次；

​ 第二个可能称为该关键字的值 (value)；

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
//C++提供的map类位于头文件<map>中
#include<iostream>
#include<string>
#include<map>
using namespace std;
int main(){
    map<keyType, valueType> mapName;//创建一个map对象，通常keyType为int
    
    //接下来以创建学生map对象为例
    map<int, string> mapStudent;
        
    begin();//返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。
    end();//返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。
    rbegin();//返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。
    rend();//返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。
    
    cbegin(); //和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
	cend();   //和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
	crbegin();//和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
	crend();  //和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
    
    find(key);//在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。
    
    lower_bound(key);//返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。
    upper_bound(key);//返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。
    
    equal_range(key);
    //该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价。
    //pair.second 和 upper_bound() 方法的返回值等价。
    //也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。
    
    empty();//若容器为空，则返回 true；否则 false。
    size();//返回当前 map 容器中存有键值对的个数。
    max_size();//返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
    operator[];//map容器重载了[]运算符，只要知道map容器中某个值对应的键，就可以向获取数组中元素那样，通过键直接获取对应的值。
    
    at(key);//找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。
    
    insert({key,value});//使用insert函数插入数据
    erase();//删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。
    swap();//交换 2 个 map 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同。
    clear();//清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0。
    emplace();//在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。
    emplace_hint();//在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的。
    //不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。
    
    count(key);//在当前 map 容器中，查找键为 key 的键值对的个数并返回。
    //注意，由于 map 容器中各值对应的键是唯一的，因此该函数的返回值最大为 1。
    return 0;
}

# 算法

# 递归 (Recursion)

递归：指函数自我调用，分解问题，解决问题。

1. 存在一个大规模问题，可以被分解为小规模问题。

2. 小规模问题存在简单的解决方法。

3. 将小规模问题的结果汇总，得到大规模问题的解。

# 递归：冒泡排序 (递归实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//按照递归的解释，提供以下算法进行参考

void Sort::bubbleSort(int* arr, int arrLen) {
	arrLen--;
	if (arrLen <= 0) return;
	for (int i = 0; i < arrLen; i++) {
		if (arr[i] > arr[i + 1]) {
			int temp = arr[i];
			arr[i] = arr[i + 1];
			arr[i + 1] = temp;
		}
	}
	bubbleSort(arr, arrLen);
}

int main() {
	int arr[10] = { 1,6,7,3,5,6,9,0,4,5 };
	Sort sort;
	sort.bubbleSort(arr, 10);
	for (int i = 0; i < 10; i++) {
		cout << arr[i] << endl;
	}
	return 0;
}

# 贪心策略 (Greedy Method)

优化问题：找到一个问题的最优解。

例如：在一个城市中，找到从 A 地到 B 地的最优路线。

# 贪心：找零问题

1
2
3
4
//贪心策略：每次都试图解决问题尽量大的一部分。

//找零问题中，若要找回63，则优先使用25\*2，然后使用10\*1，最后使用1\*3。
//优先使用最大面值，试图解决尽量大的部分，是贪心策略的表现

# 动态规划 (Dynamic Planning)

# 动态规划：背包问题

现有 5 个物品，背包仅能负重 20 公斤，如何选取最高价值的物品？

item weight value
1 2 3
2 3 4
3 4 8
4 5 8
5 9 10

思路：
记 m (i,W) 为：前 i (1 <= i <= 5) 个宝物中，组合不超过 W (1 <= W <= 20) 重量，得到的最大价值
m (i,W) 应该取 m (i-1, W) 和 m (i-1, W-Wi)+vi 其中价值更高的值

1
2
3
4
5
/*
		{0											if i=0 or W=0	
m(i,W)={m(i-1,W)									if Wi > W
    	{max{m(i - 1, W),Vi + m(i - 1, W - Wi)}		otherwise
*/

则可以绘制动态规划表：

m(i\W) 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 3 3 3 3
2 0 0 3 4 4 7
3 0 0 3 4 8 8
4 0 0 3 4 8 8
5 0 0 3 4 8 8

由公式可知：m (5,5) = m (4,5) = max {m (3,5), m (3,0) + 8}

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
#include<iostream>
#include<vector>
using namespace std;

//物品最多数目 + 1
#define MAX_I 6
//背包最大承重 + 1
#define MAX_W 21

struct object {//物品结构体
	int w;//物品的重量
	int v;//物品的价值
};

int max(int a, int b) {
	if (a > b) return a;
	else return b;
}

int main() {
	vector<object> tr;//创建列表存储物品的重量和价值
	int wArr[5] = { 2,3,4,5,9 };
	int vArr[5] = { 3,4,8,8,10 };
	for (int i = 0; i < 5; i++) {//使用一个for循环将物品属性存储
		object temp;
		temp.w = wArr[i];
		temp.v = vArr[i];
		tr.push_back(temp);
	}
	//创建二维数组m，模拟二维表格m(i,w)
	//初始化二维表格m(i,w)，其中i表示前i个宝物，w表示重量上限
	//表示前i个物品中，最大重量w的组合，所得到的最大价值
	//当i=0或w上限为0，价值均为0
	int m[MAX_I][MAX_W];
	for (int i = 0, w = 0; w < MAX_W; w++) {
		m[i][w] = 0;//当i=0时，m=0
	}
	for (int w = 0, i = 0; i < MAX_I; i++) {
		m[i][w] = 0;//当w=0时，m=0
	}

	//逐个填写二维表格
	for (int i = 1; i < MAX_I; i++) {
		for (int w = 1; w < MAX_W; w++) {
			
			if (tr[i - 1].w > w) //如果装不下第i个物品，这里i-1是因为tr是0-4而非1-5
				m[i][w] = m[i - 1][w];//不装第i个物品
			
			else//如果装的下，使用max取不装第i个物品，与装第i个物品，两种情况下的最大价值 
				m[i][w] = max(m[i - 1][w],m[i - 1][w - tr[i - 1].w] + tr[i - 1].v);
		}
	}
	
	//打印表格
    /*
	for (int i = 0; i < MAX_I; i++) {
		for (int w = 0; w < MAX_W; w++) {
			cout << m[i][w] << "  ";
		}
		cout << endl;
	}
	*/
    cout << m[5][20] << endl;//仅输出结果
	
	return 0;
}

# 查找 (Search)

从数据头，向后逐个比对。

1
2
3
4
5
6
7
8
9
10
//时间复杂度O(n)
#include"Search.h"
int Search::sequentialSearch(vector<int>& arr, int item, int arrLen) {
	int pos = 0;
	while (pos < arrLen) {
		if (arr[pos] == item) return pos;//若找到返回下标
		pos++;
	}
	return -1;//表示未找到
}

二分查找基于二分法，仅能用于有序表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//时间复杂度O(log n)
#include "Search.h"
int Search::binarySearch(vector<int>& arr, int item, int arrLen) {
	int left = 0, right = arrLen - 1;
	while (left <= right) {//当左标记超过右标记时，结束循环
		int mid = (left + right) / 2;
		if (arr[mid] == item) return mid;//查找到时，返回下标
		
		if (item < arr[mid])//若目标小于中间项
			right = mid - 1;//改变右标记
		else//若目标大于中间项
			left = mid + 1;//改变左标记
	}
	return -1;//表示未找到
}

# 排序 (Sort)

# 冒泡排序 (Bubble Sort)

仅将相邻的两项进行排序。

当首次冒泡后，最大项会被置于最后 (升序)。则下一次只需对前 n-1 个数排序。

以此类推，直到 n=2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//比对与交换的时间复杂度O(n^2)
#include"Sort.h"

void Sort::bubbleSort(vector<int>& arr) {
	//对n-1个数排序
	//每次循环操作次数-1，所以i--
	for (int i = arr.size() - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				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
20
//该优化不改变时间复杂度
#include"Sort.h"

void Sort::bubbleSort(vector<int>& arr) {
	//对n-1个数排序
	//每次循环操作次数-1，所以i--
	for (int i = arr.size() - 1; i > 0; i--) {
		bool exchange = false;//记录是否发生交换
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				exchange = true;//发生交换
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}

		if (!exchange) return;//若未发生交换，直接返回
	}
}

# 选择排序 (Selection Sort)

在冒泡排序的思想上，对交换进行优化。

仍然进行多次对比，但不交换，记录最大项所在位置，最后再进行交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//选择排序的比对时间复杂度为O(n^2),交换时间复杂度为O(n)。相较于冒泡排序优化了交换
#include"Sort"

void Sort::selectionSort(vector<int>& arr) {
	for (int i = arr.size(); i > 0; i--) {
		//假设最大值的下标为0
		int maxIndex = 0;
		for (int j = 1; j < i; j++) {
			//从1开始遍历至i，当有大于arr[maxIndex]的值时
			//将标记最大值的下标指向它
			if (arr[j] > arr[maxIndex]) maxIndex = j;
		}

		//将最大值交换到找到的位置
		int temp = arr[i - 1];//使用i时减一防止越界
		arr[i - 1] = arr[maxIndex];
		arr[maxIndex] = temp;
	}
}

# 插入排序 (Insertion Sort)

插入排序维持一个已经排好序的子列表，其位置始终在列表的前部，然后逐步扩大这个子列表直到全表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//插入排序的时间复杂度为O(n^2)
#include"Sort"

void Sort::insertionSort(vector<int>& arr) {
	int index;//下标
	int currentValue;//当前值
	for (int i = 0; i < arr.size(); i++) {
		currentValue = arr[i];//令当前值=arr[i]
		index = i;//下标=i，因为左侧是排序好的表，所以从i开始遍历即可
		while (index > 0 && arr[index - 1] > currentValue){//当下标大于0并且当前值的左值大于当前值时
			arr[index] = arr[index - 1];//将左值后移(即与当前值交换位置)
			index--;//下标左移
		}
		//退出循环时，下标index的位置，即当前值应插入的位置
		arr[index] = currentValue;//插入当前值
	}
}

# 谢尔排序 (Shell Sort)

假设将数组 {6,5,4,3,2,1,9,8,7} 进行排序 (升序)。

则可以将其划分为三个子数组，为 {6,5,4}、{3,2,1}、

然后分别对其进行插入排序，变为

可以发现，虽然并未变成完全有序，但是相对于原数组，是更有序的。

假设现有 n 个数需要进行排序。可以将其划分为 n / 2 个子数组进行排序

对排序后的数组再划分为 n / 4 个子数组进行排序，以此类推，直到 n / … 为 1 时，即为插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//谢尔排序会减少许多"无效"对比，所以略优于插入排序
//时间复杂度大约介于O(n)和O(n^2)之间
#include"Sort.h"

void gapInsertionSort(vector<int>& arr, int start, int gap) {
	for (int i = start + gap; i < arr.size(); i += gap) {//对子数组排序
		int currentValue = arr[i];//接下来与插入排序相同
		int index = i;
		while (index >= gap && arr[index - gap] > currentValue) {
			arr[index] = arr[index - gap];
			index = index - gap;
		}
		arr[index] = currentValue;
	}
}

void Sort::shellSort(vector<int>& arr) {
	int subCount = arr.size() / 2;//设定间隔来划分子数组
	while (subCount > 0) {//间隔为0时退出循环
		for (int start = 0; start < subCount; start++)
			gapInsertionSort(arr, start, subCount);//该函数对子数组进行排序
		subCount /= 2;//缩小间隔
	}
}

# 归并排序 (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
//归并排序的时间复杂度为O(nlog n)。其中分裂过程的时间复杂度为O(log n),归并过程的时间复杂度为O(n)。
//归并排序使用更多的空间。(空间换时间)
#include"Sort.h"

void Sort::mergeSort(vector<int>& arr) {
	if (arr.size() > 1) {//当数据被分为1时，则不需要再分割，也就不需要进入以下代码
		int mid = arr.size() / 2;//取中间点
		vector<int> leftHalf(arr.begin(), arr.begin() + mid);//分为左半部分		
		vector<int> rightHalf(arr.begin() + mid, arr.end());//分为右半部分

		mergeSort(leftHalf);//对左半部分进行merge排序
		mergeSort(rightHalf);//对右半部分进行merge排序
		
		int i = 0, j = 0, k = 0;//其中i为left的下标，j为right的下标，k为arr的下标

		while (i < leftHalf.size() && j < rightHalf.size()) {
			//拉链式交错把左右半部从小归到大归并到结果vector
			if (leftHalf[i] < rightHalf[j]) {
				arr[k] = leftHalf[i];
				i++;
			}
			else {
				arr[k] = rightHalf[j];
				j++;
			}
			k++;
		}

		//归并左半部剩余的部分
		while (i < leftHalf.size()) {
			arr[k] = leftHalf[i];
			i++;
			k++;
		}

		//归并右半部剩余的部分
		while (j < rightHalf.size()) {
			arr[k] = rightHalf[j];
			j++;
			k++;
		}
	}
}

# 快速排序 (Quick Sort)

找到数据表的中值，并将数据表分为两半，随后自我调用，直到数据表仅有 1 项数据。

寻找中值：

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
//快速排序的时间复杂度为O(nlog n)。
//当分裂时，总能分为左右相同的两块，则其中分裂部分的复杂度为O(log n),移动部分的时间复杂度为O(n)
//当中值所在位置过于偏离中部，造成左右两块数量不平衡，会导致时间复杂度上升
//极端情况下，有一部分始终没有数据，则时间复杂度退化到O(n^2),考虑到递归调用，效率甚至低于冒泡排序
//快速排序相较于归并排序，不需要调用额外的空间
#include"Sort.h"

int getMidI(vector<int>& arr, int first, int last) {
	int midValue = arr[first];//选定中值

	int leftMark = first + 1;//左标
	int rightMark = last;//右标

	while (true) {
		//当左标小于右标，且左标指向的值小于中值时，左标右移
		while (leftMark <= rightMark && arr[leftMark] <= midValue) leftMark++;
		//当右标大于左标，且右标指向的值大于中值时，右标左移
		while (rightMark >= leftMark && arr[rightMark] >= midValue) rightMark--;
		if (rightMark < leftMark) break;//当左标大于右标，结束循环
		else {//否则当左标和右标都停止时，交换左标与右标指向的值
			int temp = arr[leftMark];
			arr[leftMark] = arr[rightMark];
			arr[rightMark] = temp;
		}
	}
	//最后将中值置于rightMark处
	int temp = arr[first];
	arr[first] = arr[rightMark];
	arr[rightMark] = temp;
	
	//返回中值的下标
	return rightMark;
}

void quickSortHelper(vector<int>& arr, int first, int last) {
	if (first < last) {
		int midValue = getMidI(arr,first,last);//获取中值的下标
		quickSortHelper(arr, first, midValue - 1);//从中值处分裂，处理中值左边的部分
		quickSortHelper(arr, midValue + 1, last);//处理中值右边的部分
	}
}

void Sort::quickSort(vector<int>& arr) {
	quickSortHelper(arr, 0, arr.size() - 1);
}