https://www.runoob.com/w3cnote_genre/algorithm

冒泡排序

外层循环控制循环次数，内层循环进行比较

void BubbleSort(int arr[], int length){
	int flag = 0;
	for (int i = 0; i < length && flag == 0; i++){
		flag = 1; //认为已经排序好
		for (int j = length - 1; j > i; j--){
			if (arr[j - 1] < arr[j]){
				flag = 0;
				Swap(&arr[j - 1], &arr[j]);
			}
		}
	}
}

选择排序

每次循环选出最小的数，然后与外层循环的下标对应的变量进行交换

void SelectSort(int arr[],int length){	
	//选择排序是不是减少交换次数 
	for (int i = 0; i < length;i ++){
		int min = i;
		for (int j = i + 1; j < length; j++){
			if (arr[j] < arr[min]){
				min = j;
			}
		}
		if (min != i){
			Swap(&arr[min],&arr[i]);
		}
	}
}

插入排序

从下标1开始，与之前的数据进行比较，比较过程中前边的数据都是已经排好序的

void InsertSort(int arr[], int length){
	int j;
	for (int i = 1; i < length; i++){

		if (arr[i] < arr[i - 1]){

			int temp = arr[i];
			for (j = i - 1; j >= 0 && temp < arr[j]; j--){
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = temp;
		}
	}
}

希尔排序

确定增量，increasement = increasement / 3 + 1 （步长 = 步长 / 3 + 1） 根据增量分为若干子序列，分别进行插入排序；减小增量再进行排序...

void ShellSort(int arr[], int length){
	int increasement = length;
	int i, j,k;

	do{
		//确定分组的增量
		increasement = increasement / 3 + 1;
		for (i = 0; i<increasement;i++){
			
			for (j = i + increasement; j < length; j += increasement){		
				
				if (arr[j] < arr[j-increasement] ){
					
					int temp = arr[j];
					for (k = j - increasement; k >= 0 && temp < arr[k];k-=increasement){
						arr[k + increasement] = arr[k];
					}
					arr[k + increasement] = temp;
				}
			}
		}
	} while (increasement > 1);
}

快速排序

分治法，找到基准数，从右向左进行比较，然后再从左到右比较

void QuickSort(int arr[], int start, int end){	
	int i = start;
	int j = end;
	//基准数
	int temp = arr[start]; 
	if (i < j){
		while (i < j){
			//从右向左去找比基准数小的
			while (i<j && arr[j] >= temp ){
				j--;
			}
			//填坑
			if(i < j){
				arr[i] = arr[j];
				i++;
			}
			//从左向右 找比基准数大的数
			while (i < j && arr[i] < temp){
				i++;
			}
			//填坑
			if (i < j){
				arr[j] = arr[i];
				j--;
			}
		}
		//把基准数放到i位置
		arr[i] = temp;
		//对左半部分进行快速排序
		QuickSort(arr, start, i - 1);
		//对右半部分进行快速排序
		QuickSort(arr, i + 1, end);
	}
}

归并排序

https://www.cnblogs.com/chengxiao/p/6194356.html 分治法，基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？ 可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

//合并算法 从小到大
void Merge(int arr[], int start, int end, int mid, int* temp){

	int i_start = start;
	int i_end = mid;
	int j_start = mid + 1;
	int j_end = end;

	//表示辅助空间有多少个元素
	int length = 0;

	//合并两个有序序列
	while (i_start <= i_end && j_start <= j_end){

		if(arr[i_start] < arr[j_start]){
			temp[length] = arr[i_start];
			length++;
			i_start++;
		}else{
			temp[length] = arr[j_start];
			j_start++;
			length++;
		}
	}

	//i这个序列
	while (i_start <= i_end){
		temp[length] = arr[i_start];
		i_start++;
		length++;
	}

	//j序列
	while (j_start <= j_end){
		temp[length] = arr[j_start];
		length++;
		j_start++;
	}

	//辅助空间数据覆盖原空间
	for (int i = 0; i < length;i++){
		arr[start + i] = temp[i];
	}
}

//归并排序
void MergeSort(int arr[],int start,int end,int* temp){

	if (start >= end){
		return;
	}

	int mid = (start + end) / 2;
	//分组
	//左半边
	MergeSort(arr,start,mid,temp);
	//右半边
	MergeSort(arr, mid + 1, end,temp);
	//合并
	Merge(arr,start,end,mid,temp);
}

堆排序

https://www.cnblogs.com/chengxiao/p/6129630.html

/*
	@param myArr 待调整的数组
	@param index 待调整的结点的下标
	@param len 数组的长度
*/
void HeapAdjust(int arr[], int index, int len){

	//先保存当前结点的下标
	int max = index;
	//保存左右孩子的数组下标
	int lchild = index * 2 + 1;
	int rchild = index * 2 + 2;

	if (lchild < len && arr[lchild] < arr[max]){
		max = lchild;
	}

	if (rchild < len && arr[rchild] < arr[max]){
		max = rchild;
	}

	if (max != index){
		//交换两个结点
		MySwap(arr,max,index);
		HeapAdjust(arr,max,len);
	}
}

//堆排序
void HeapSort(int myArr[], int len){

	//初始化堆
	for (int i = len / 2 - 1; i >= 0; i --){
		HeapAdjust(myArr,i,len);
	}

	//交换堆顶元素和最后一个元素
	for (int i = len - 1; i >= 0; i --){
		MySwap(myArr, 0, i);
		HeapAdjust(myArr, 0, i);
	}

}

c++模板类与数据结构基础

：所有容器提供的都是值（value）语意，而非引用（reference）语意。容器执行插入元素的操作时，内部实施拷贝动作。所以STL容器内存储的元素必须能够被拷贝（必须提供拷贝构造函数）。

链表类_链式存储设计与实现

//LinkList.hpp
#ifndef LINKLIST_HPP
#define LINKLIST_HPP
#include <string>
//c++模板完成单向链表

//结点结构
template<class T>
class ListNode{
public:
	T data;  //数据域
	ListNode* next; //指针域
};

//定义链表类
template<class T>
class LinkList{
public:

	//构造函数
	LinkList():length(0),head(NULL){}

	//链表操作相关API
	//设置链表长度
	void setLength(int length){
		if (length < 0){
			return;
		}
		this->length = length;
	}
	//获得链表长度
	int getLength(){
		return this->length;
	}
	//设置链表头结点
	void setHead(ListNode<T>* head){
		this->head = head;
	}
	//获得链表的头结点
	ListNode<T>* getHead(){
		return this->head;
	}
	//插入元素
	int Insert(int pos, T value){
		
		//创建结点
		ListNode<T>* newnode = new ListNode<T>();
		newnode->next = NULL;
		newnode->data = value;

		//第一次插入
		if (this->head == NULL){
			this->head = newnode;
			this->length++;
			return 0;
		}

		//头插法
		ListNode<T>* pCurrent = head;
		if(pos == 0){
			newnode->next = pCurrent;
			this->head = newnode;
			this->length++;
			return 0;
		}

		//找到插入位置
		//ListNode<T>* pCurrent = head;
		for (int i = 1; i < pos;i++){
			if (pCurrent->next == NULL){
				break;
			}
			pCurrent = pCurrent->next;
		}
		//插入新的结点
		newnode->next = pCurrent->next;
		pCurrent->next = newnode;
		this->length++;
	}

	//删除某个位置的结点
	int Delete(int pos){
		
		if (this->length == 0){
			return -1;
		}
		if(pos > this->length || pos < 0){
			return -2;
		}

		//头删法
		if (pos == 0){
			ListNode<T>* pDel = this->head;
			this->head = pDel->next;
			this->length--;
			delete pDel;
			return 0;
		}

		//找删除的位置
		ListNode<T>* pCurrent = head;
		for (int i = 1; i < pos;i++){
			pCurrent = pCurrent->next;
		}

		ListNode<T>* pDel = pCurrent->next;
		//重新连接结点
		pCurrent->next = pDel->next;
		//删除结点
		delete pDel;
		this->length--;
	}

	//判断链表是否为空
	bool IsEmpty(){
		if (this->length == 0){
			return true;
		}
		return false;
	}
	~LinkList(){
		while (this->length){
			Delete(0);
		}
	}
private:
	int length; //保存结点数量
	ListNode<T>* head;
};

#endif

//LinkListTest.cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include"LinkList.hpp"
using namespace std;

//测试单向链表容器
void test01(){

	//创建容器
	LinkList<int> list;
	//向容器中插入数据
	for (int i = 0; i < 10; i++){
		list.Insert(list.getLength(), i);
	}
	//遍历打印链表
	ListNode<int>* pCurrent = list.getHead();
	while (pCurrent != NULL){
		cout << pCurrent->data << " ";
		pCurrent = pCurrent->next;
	}
	cout << endl;


	//删除结点
	list.Delete(0);
	list.Delete(1);

	//遍历打印链表
	pCurrent = list.getHead();
	while (pCurrent != NULL){
		cout << pCurrent->data << " ";
		pCurrent = pCurrent->next;
	}
	cout << endl;
}


//Teacher类
class Teacher{
public:
	Teacher(){}
	Teacher(string name, int age){
		this->m_name = name;
		this->m_age = age;
	}
	//拷贝构造
	Teacher(const Teacher& t){
		this->m_name = t.m_name;
		this->m_age = t.m_age;
	}
	//重载=操作符
	Teacher operator=(Teacher& t){
		this->m_name = t.m_name;
		this->m_age = t.m_age;
		return *this;
	}
public:
	string m_name;
	int m_age;
};

//容器中存储对象 重点：容器元素都是值寓意，而非引用寓意
void test02(){

	//创建两个Teacher类的实例
	Teacher t1("aaa", 10), t2("bbb", 20);
	//创建容器
	LinkList<Teacher> list;
	//向list中插入元素
	list.Insert(0, t1);
	list.Insert(0, t2);
	//打印容器中的元素的值
	ListNode<Teacher>* pCurrent = list.getHead();
	while (pCurrent != NULL){
		cout << "Name:" << pCurrent->data.m_name << " Age:" << pCurrent->data.m_age << endl;
		pCurrent = pCurrent->next;
	}
	list.Delete(1);
	//打印容器中的元素的值
	pCurrent = list.getHead();
	while (pCurrent != NULL){
		cout << "Name:" << pCurrent->data.m_name << " Age:" << pCurrent->data.m_age << endl;
		pCurrent = pCurrent->next;
	}

}

//容器中存储指针
void test03(){

	//创建两个Teacher类的实例
	Teacher t1("aaa", 10), t2("bbb", 20);
	//创建容器
	LinkList<Teacher*> list;
	//插入元素
	list.Insert(0, &t1);
	list.Insert(0, &t2);

	//打印容器中的元素的值
	ListNode<Teacher*>* pCurrent = list.getHead();
	while (pCurrent != NULL){
		cout << "Name:" << pCurrent->data->m_name << " Age:" << pCurrent->data->m_age << endl;
		pCurrent = pCurrent->next;
	}
}

int main(){

	//test01();
	//test02();
	test03();

	system("pause");
	return EXIT_SUCCESS;
}

栈类_链式存储设计与实现

//LinkStack.hpp
#ifndef LINKQUEUE_HPP
#define LINKQUEUE_HPP

//结点结构
template<class T>
class LinkNode{
public:
	T data;
	LinkNode* next;
};

//队列类
template<class T>
class LinkQueue{
public:
	//初始化链式队列
	LinkQueue(){
		pFront = NULL;
		pBack = NULL;
		mLength = 0;
	}
	//获得队列长度
	int getLength(){
		return this->mLength;
	}
	//队列加入元素
	void Push(T data){
		
		//创建新的结点
		LinkNode<T>* newnode = new LinkNode<T>();
		newnode->data = data;
		newnode->next = NULL;

		//判断是不是第一次插入
		if (pFront == NULL && pBack == NULL){
			pFront = newnode;
			pBack = newnode;
			this->mLength++;
			return;
		}

		//其他情况
		this->pBack->next = newnode;
		this->pBack = newnode;
		this->mLength++;

		return;
	}

	T& Front(){
		return this->pFront->data;
	}

	void Pop(){

		if (this->mLength == 0){
			return;
		}

		//当队列中只有一个元素的时候
		if (this->mLength == 1){
			delete this->pFront;
			this->pFront = NULL;
			this->pBack = NULL;
			this->mLength--;
			return;
		}

		//其他情况
		LinkNode<T>* pDel = this->pFront;
		this->pFront = pDel->next;
		delete pDel;
		this->mLength--;
		return;
	}
	~LinkQueue(){
		while (this->mLength > 0){
			Pop();
		}
	}
private:
	LinkNode<T>* pFront; //队头
	LinkNode<T>* pBack; //队尾
	int mLength; //队列长度
};
#endif

//LinkStackTest.cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include"LinkStack.hpp"
using namespace std;

//栈容器存储基础数据类型
void test01(){
	
	//创建栈容器
	LinkStack<int> lstack;
	//向栈中加入元素
	for (int i = 10; i < 20;i++){
		lstack.Push(i);
	}
	//打印栈中元素
	while (lstack.getLength() > 0){
		int val = lstack.Top();
		cout << val << " ";
		lstack.Pop();
	}
	cout << endl;
}

//栈容器存储对象

//Teacher类
class Teacher{
public:
	Teacher(){}
	Teacher(string name, int age){
		this->m_name = name;
		this->m_age = age;
	}
	//拷贝构造
	Teacher(const Teacher& t){
		this->m_name = t.m_name;
		this->m_age = t.m_age;
	}
	//重载=操作符
	Teacher operator=(Teacher& t){
		this->m_name = t.m_name;
		this->m_age = t.m_age;
		return *this;
	}
public:
	string m_name;
	int m_age;
};

void test02(){

	//创建栈
	LinkStack<Teacher> lstack;
	//插入数据
	Teacher t1("aaa", 10), t2("bbb", 20),t3("ccc",30);
	lstack.Push(t1);
	lstack.Push(t2);
	lstack.Push(t3);
	//遍历打印
	while (lstack.getLength() > 0){
		Teacher teahcer = lstack.Top();
		cout << "Name:" << teahcer.m_name << " Age:" << teahcer.m_age << endl;;
		lstack.Pop();
	}

}

//容器存储对象指针
void test03(){
	
	//创建栈
	LinkStack<Teacher*> lstack;
	//插入数据
	Teacher t1("aaa", 10), t2("bbb", 20), t3("ccc", 30);
	lstack.Push(&t1);
	lstack.Push(&t2);
	lstack.Push(&t3);
	//遍历打印
	while (lstack.getLength() > 0){
		Teacher* teahcer = lstack.Top();
		cout << "Name:" << teahcer->m_name << " Age:" << teahcer->m_age << endl;;
		lstack.Pop();
	}

}

int main(){

	//test01();
	//test02();
	test03();
	system("pause");
	return EXIT_SUCCESS;
}

队列类_链式存储设计与实现

//LinkQueue.hpp
#ifndef LINKQUEUE_HPP
#define LINKQUEUE_HPP

//结点结构
template<class T>
class LinkNode{
public:
	T data;
	LinkNode* next;
};

//队列类
template<class T>
class LinkQueue{
public:
	//初始化链式队列
	LinkQueue(){
		pFront = NULL;
		pBack = NULL;
		mLength = 0;
	}
	//获得队列长度
	int getLength(){
		return this->mLength;
	}
	//队列加入元素
	void Push(T data){
		
		//创建新的结点
		LinkNode<T>* newnode = new LinkNode<T>();
		newnode->data = data;
		newnode->next = NULL;

		//判断是不是第一次插入
		if (pFront == NULL && pBack == NULL){
			pFront = newnode;
			pBack = newnode;
			this->mLength++;
			return;
		}

		//其他情况
		this->pBack->next = newnode;
		this->pBack = newnode;
		this->mLength++;

		return;
	}

	T& Front(){
		return this->pFront->data;
	}

	void Pop(){

		if (this->mLength == 0){
			return;
		}

		//当队列中只有一个元素的时候
		if (this->mLength == 1){
			delete this->pFront;
			this->pFront = NULL;
			this->pBack = NULL;
			this->mLength--;
			return;
		}

		//其他情况
		LinkNode<T>* pDel = this->pFront;
		this->pFront = pDel->next;
		delete pDel;
		this->mLength--;
		return;
	}

private:
	LinkNode<T>* pFront; //队头
	LinkNode<T>* pBack; //队尾
	int mLength; //队列长度
};

#endif

//LinkQueueTest.cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include"LinkQueue.hpp"
using namespace std;

//存储基础数据类型
void test01(){

	//创建链式队列
	LinkQueue<int> queue;
	//添加数据
	for (int i = 0; i < 10;i++){
		queue.Push(i);
	}
	//修改队头元素的值
	queue.Front() = 100;
	//打印队列
	while (queue.getLength() > 0){
		int val = queue.Front();
		cout << val << " ";
		queue.Pop();
	}
	cout << endl;
}

int main(){

	test01();

	system("pause");
	return EXIT_SUCCESS;
}

链表类_顺序存储设计与实现

//SqList.hpp
#ifndef SQLIST_HPP
#define SQLIST_HPP

//链表类
template<class T>
class SqList{
public:
	//构造函数，由用户指定容量
	SqList(int capacity){
		this->mCapacity = capacity;
		this->mLength = 0;
		this->mArray = new T[capacity];
	}
	//获得容量
	int getCapacity(){
		return this->mCapacity;
	}
	//获得链表长度
	int getLength(){
		return this->mLength;
	}
	//获得数组
	T* getArray(){
		return this->mArray;
	}
	//获得指定位置元素
	T Get(int pos){
		if (pos > this->mLength - 1){
			return -1;
		}
		return this->mArray[pos];
	}
	//链表中指定位置插入结点
	void Insert(int pos, T data){
		if (this->mLength >= this->mCapacity){
			return;
		}
		if (pos > this->mLength){
			pos = this->mLength - 1;
		}

		this->mArray[pos] = data;
		this->mLength++;
	}
	//删除指定位置结点
	void Delete(int pos){
		
		if (pos > this->mLength-1){
			return;
		}

		for (int i = pos; i < mLength;i++){
			this->mArray[i] = this->mArray[i + 1];
		}
		this->mLength--;
	}

	~SqList(){
		if (mArray != NULL){
			delete mArray;
		}
	}
private:
	int mCapacity;//容量
	int mLength;//长度
	T* mArray;
};

#endif

//SqListTest.cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include"SqList.hpp"
using namespace std;

void test01(){
	
	//创建栈
	SqList<int> list(20);
	//插入数据
	for (int i = 0; i < 20;i++){
		list.Insert(i,i+1);
	}
	//打印数据
	for (int i = 0; i < 20;i++){
		cout << list.Get(i) << " ";
	}
	cout << endl;
}

int main(){
	test01();
	system("pause");
	return EXIT_SUCCESS;
}

栈类_顺序存储设计与实现

//SqStack.hpp
#ifndef SQSTACK_HPP
#define SQSTACK_HPP

//栈的顺序存储
template<class T>
class SqStack{
public:
	//构造函数
	SqStack(int capacity){
		this->mCapacity = capacity;
		this->mLength = 0;
		this->mArray = new T[capacity];
	}
	int getLength(){
		return this->mLength;
	}
	//压栈
	void Push(T data){
		
		if (this->mLength >= this->mCapacity){
			return;
		}

		this->mArray[this->mLength] = data;
		this->mLength++;

	}

	//出栈
	T Top(){
		return this->mArray[this->mLength - 1];
	}

	//弹出栈顶元素
	void Pop(){
		this->mLength--;
	}

	~SqStack(){
		if (this->mArray != NULL){
			delete this->mArray;
		}
	}
private:
	T* mArray;
	int mCapacity; //容量
	int mLength; //长度
};

#endif

//SqStackTest.cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include"SqStack.hpp"
using namespace std;

void test01(){
	
	//创建栈
	SqStack<int> stack(20);
	//压栈
	for (int i = 0; i < 20;i++){
		stack.Push(i);
	}
	//遍历
	while (stack.getLength() > 0){
		cout << stack.Top() << " ";
		stack.Pop();
	}
	cout << endl;

}

int main(){
	test01();
	system("pause");
	return EXIT_SUCCESS;
}

队列类_顺序存储设计与实现

//SqQueue.hpp
#ifndef SQQUEUE_HPP
#define SQQUEUE_HPP

//队列的顺序存储
template<class T>
class SqQueue{
public:
	SqQueue(int capacity){
		this->mCapacity = capacity;
		this->mLength = 0;
		this->mArray = new T[capacity];
	}
	//获得队列长度
	int getLength(){
		return this->mLength;
	}

	//获得容量
	int getCapacity(){
		return this->mCapacity;
	}

	//入队操作
	void Push(T data){
		if (this->mLength >= this->mCapacity){
			return;
		}
		this->mArray[mLength] = data;
		this->mLength++;
	}

	//出队操作
	T Front(){
		return this->mArray[0];
	}

	//队头弹出元素
	void Pop(){
		for (int i = 0; i < mLength; i++){
			mArray[i] = mArray[i + 1];
		}
		this->mLength--;
	}
private:
	int mLength;
	T* mArray;
	int mCapacity;
};

#endif

//SqQueueTest.cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include"SqQueue.hpp"
using namespace std;

void test01(){
	
	//创建队列
	SqQueue<int> queue(20);
	//向队列中插入元素
	for (int i = 0; i < 20;i++){
		queue.Push(i);
	}
	//打印队列元素
	while (queue.getLength() > 0){
		cout << queue.Front() << " ";
		queue.Pop();
	}
	cout << endl;

}

int main(){
	test01();
	system("pause");
	return EXIT_SUCCESS;
}