零基础学算法 戴艳 学习笔记 读书笔记 记录于：海淀区北部文化中心图书馆

第1章
算法就是用于计算的方法，通过这种方法可以得到预期的计算结果。通俗说，算法就是一种方案。

程序=数据结构 + 算法 + 程序设计语言

数据结构表示 要处理的数据有 输入数据 和 输出的数据。

猜价格游戏：999以内的商品，娱乐节目 幸运52 一分钟内 高了 低了 <二分法>

百钱买鸡：枚举(穷举)

递推算法：斐波那契：兔子繁殖[顺推] 和 猴子吃桃[逆推]

递归算法：求阶乘
递归算法，就是程序中不断反复调用自身来求解问题的方法。将待求解问题 分解成 相同的每一个子问题，进行多次递归调用。

递归算法实质可以看出，递归算法也是一种特殊的 循环，这不是 循环语句来实现，而是 循环调用函数自身来实现的。

递归算法：三要素
1.必须要有明确的递归结束条件，递归出口。
2.前次输出作为后一次的输入

实例：进制转换
十进制转换：将 目标进制数 / 进制基数 余数作为 转换进制数的 最低位，再商 再除 进制基数，取余作为次低位...

121 / 2 60...1 1111001 
60 / 2 30...0 
30 / 2 15...0
15 / 2 7...1
7 / 2 3...1
3 / 2 1...1
1 / 2 0...1

第3章 复杂数据结构
树中节点最大度数没有限制，而二叉树节点最大度数为2。
树的节点无左、右之分，而二叉树的节点有左、右之分。
因为子树有左右之分，所以二叉树是有序树。

满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

宏观看，二叉树由 根节点、左子树、右子树三部分组成，只要遍历了这三部分，就等于遍历了整个二叉树。

二叉树的遍历 是一个递归的过程。

先序遍历二叉树

void BinTree_DLR(BinTree)
{
if(二叉树不为空)
{
// 访问根节点
BinTree_DLR(left); // 先序 遍历左子树
BinTree_DLR(right); // 先序 遍历右子树
}
}

中序遍历二叉树

void BinTree_DLR(BinTree)
{
if(二叉树不为空)
{
BinTree_DLR(left); // 先序 遍历左子树
// 访问根节点
BinTree_DLR(right); // 先序 遍历右子树
}
}

后序遍历二叉树

void BinTree_DLR(BinTree)
{
if(二叉树不为空)
{
BinTree_DLR(left); // 先序 遍历左子树
BinTree_DLR(right); // 先序 遍历右子树
// 访问根节点
}
}

第4章 排序

int creatData(int arr[],int n,int min,int max)
{
int i,j,flag;
srand( time(NULL) ); // 循环生成随机数
if( (max-min+1)<n ) return 0;
for(i=0;i<n;i++){
while(flag)
{
arr[i]=(max-min+1)*rand() / (RAND_MAX+1)+min;
flag = 0;
for(j=0;j<i;j++)
{
if(arr[i]==arr[j])
flag = 1;
}
}
}
return 1;
}

creatData(a,6,1,100);
getch();

快排
void 快排(数组，左侧序号，右侧序号)
{
分割数据，将left保存到i
快排(数组,原左侧序号,i-1);
快排(数组,i+1,原右侧序号);
}

快排有两个函数：分区函数、快排

int Division(int a[],int left,int right)
{
int base = a[left]; // 取左侧位基准原属
while(left<right) //左侧序号 小于 右侧序号
{ 
while(left<right && a[right]>base) // 从右向左 找第一个比基准小的元素
{
--right;
}
a[left] = a[right]; // 将比基准小的元素移动 左侧
while(left<right && a[right]<base) // 从左向右 找第一个比基准大的元素
{
--left;
}
a[right] = a[left]; // 将比基准大的元素移动 右侧
}
a[left] = base; // 保存基准数
return left;
}

void QuickSort(int a[],int left,int right)
{
int i,j;
if(left<right) // 递归的约束条件
{
i= Division(a,left,right); //数据分区，保存基准变量i
QuickSort(a,left,i-1); //对基准左边 快排
QuickSort(a,i+1,right); //对基准右边 快排
}
}

简单选择排序：选择一个数，作为参考，其它每个 数，依次与之比较，交换

void SelectSort(int a[],int n)
{
for(i=0;i<n-1;i++)
{
k =i; //记录需要和 第k个元素交换
for(j=i+1;j<n;j++)
if(a[j]<a[k]) k=j; // 查找最小数据，保存其 下标
tmp = a[i]; //交换
a[i] = a[k];
a[k] = tmp;
}
}

直接插入排序：有序 和 无序 两拨数据集合

void InsertSort(int a[],int n)
{
for(i=1;i<n;i++)
{
t = a[i]; // 取一个 不参与排序的 数据
for(j=i-1;j>=0&&a[j]>t;--j) //在排序序列查找位置
a[j+1] = a[j]; //向后移动数据
a[j+1] = t; // 插入到 已排好数的 序列中
}
}

希尔排序：增量排序，子序列划分
一般使用总元素和的一半作为增量。接着缩小增量一半，直到增量位1，在使用直接插入排序，得到结果。

void ShellSort(int a[],int n)
{
int d = n/2; 计算第一次增量
while(d>=1) //增量为1 希尔排序结束
{
for(i=d;i<n;i++)
{
x = a[i]; // 获取数列中下一个数据
j = i-d; //数列中前一个数据的序号
while( j>=0&&a[j]>x)//下一个数大于前一个数
{
a[i+1] = a[j]; //后数前移
j=j-d; //修改序号，继续向前比较
}
a[j+d]=x;//保存数据
}
d/=2; //每次缩小一半增量
}
}