学习笔记C++（冒泡排序、选择排序、堆排序、递归）
冒泡排序法：就是两两交换到最后
冒泡排序法
重复执行n次冒泡，也就是 O(n^2)。 空间复杂度是O(n)。
选择排序法：
选择排序法
这样的过程要执行n次，所以时间复杂度还是O(n^2)。空间复杂度是O(n)
堆排序：
1、概念
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。
堆排序的时间复杂度是O(nlgN)，与快速排序达到相同的时间复杂度。但是在实际应用中，我们往往采用快速排序而不是堆排序。这是因为快速排序的一个好的实现，往往比堆排序具有更好的表现。堆排序的主要用途，是在形成和处理优先级队列方面。另外，如果计算要求是类优先级队列（比如，只要返回最大或者最小元素，只有有限的插入要求等），堆同样是很适合的数据结构。
2、基础知识
堆一般用数组表示，比如数组A数组的长度Length(A)，堆在数组中的元素个数HeapSize(A)。一般说来，HeapSize(A) <= Length(A)，因为数组A当中可能有一些元素不在堆中。
假设节点I是数组A中下标为i的节点。
Parent(i) : return Floor(i/2); //I的父节点下标，Floor(i)表示比i小的最大整数。
Left(i) : return 2*i; //I的左子节点
Right(i) : return 2*i+1; //I的右子节点
含有n个元素的堆A的高度是: Floor(lgn)。
3、在堆中定义以下几种操作：
最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
处理过程
思路
递归：参考
特点1 它有一个基本部分，即直接满足条件，输出
特点2 它有一个递归部分，即 通过改变基数（即n），来逐步使得n满足基本部分的条件，从而输出
例子1： 全排列
描述： 有n个数时， 输出n个数的所有排列组合
分析：
假设有 abc三个数，
特点3： 整体分割为局部，从基本部分开始输出
那么其输出为 abc, acb, bac, bca, cba, cab。
abc, bac, cba 三种情况下，都会从整体过度到 部分， 即 abc->bc, bac->ac, cba->ba, 而相应的 bc, ac, ba, 又会有cb, ca, ab的情况．即 perm(abc)-> a*perm(bc)+b*perm(ac)+c*perm(ba) （perm为排列的意思）
特点1：
当perm(bc)->b*perm(c)时，即perm的数目只有一个时，即为输出
特点2：
perm(abc)->perm(bc)->perm(c)即 perm的数目递减的过程，为递归部分
特点4： 将递归的操作作为自操作，完成当前整体的操作
一次，在一次整体的操作中， 需要abc, bac, cba三个，进行整体到部分的操作（即递归操作）。
而abc, bac, cba 是a 与 b, 与c交换的结果，因此，答案就出来了：
//Implementation Permutation n numbers
//交换位置
template
void swap(T &a, T &b)
{
T temp = a;
a = b;
b = temp;
}
//全排列,
//list为排列的数的数组，如{1, 2, 3}
//int k 为排列数组的起始点，int m 为排列数组的终点
//如k=0,m=2 将1,2,3进行全排列，当 k=1, m=2,将2,3全排列
template
void permulateNumber(T list[], int k, int m)
{
if (k == m) //输出条件，整体变部分，k 逐渐逼近 m直到=m
{
//特点1 基本部分, 完成数组从第一个到最后一个数的输出
for (int i = 0; i <= m; ++i)
{
std::cout << list[i];
}
std::cout << std::endl;
}
else{//特点2 递归部分
//以下为特点4
for (int i = k; i <= m; ++i)
{
swap(list[k], list[i]);// 完成当前排列部分中，第一个数，与后面数的交换
permulateNumber(list, k + 1, m);//特点3 整体到部分
swap(list[i], list[k]);
}
}
}
PS:递归算法可以理解为一种思想，还有一切其他例子的应用可以参考链接
