数据结构
通常可以分为四类：
集合结构：就是一个集合，就是一个圆圈中有很多个元素，元素与元素之间没有任何关系 。
线性结构 ：就是一个条线上站着很多个人。 这条线不一定是直的。也可以是弯的。也可以是值的 相当于一条线被分成了好几段的样子。 线性结构是一对一的关系。
树形结构 ：做开发的肯定或多或少的知道xml 解析 树形结构跟他非常类似。也可以想象成一个金字塔。树形结构是一对多的关系
图形结构：这个就比较复杂了。 无穷、无边、 无向（没有方向）图形机构 你可以理解为多对多 类似于我们人的交集关系。
数据结构的存储方式：
顺序存储方式和链式存储方式
链表可分为：
单向链表：A->B->C->D->E->F->G->H. 这就是单向链表 H 是头 A 是尾 像一个只有一个头的火车一样 只能一个头拉着跑
双向链表：H<- A->B->C->D->E->F->G->H. 这就是双向链表。有头没尾。两边都可以跑 跟地铁一样 到头了 可以倒着开回来
循环链表：A->B->C->D->E->F->G->H. 绕成一个圈。就像蛇吃自己的这就是循环。
什么是树
树 是由n（n>=1）个有限节点组成一个具有层次关系的集合。它具有以下特点：每个节点有零个或多个子节点；没有父节点的节点称为 根 节点；每一个非根节点有且只有一个 父节点 ；除了根节点外，每个子节点可以分为多个不相交的子树。
什么是二叉树
树形结构下,两个节点以内 都称之为二叉树 不存在大于2 的节点 分为左子树 右子树 有顺序 不能颠倒。
二叉树的第i层至多有2^(i-1)个结点；深度为k的二叉树至多有2^k-1个结点。
一棵深度为k，且有2^k-1个节点的二叉树称之为 满二叉树 ；
深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为 完全二叉树 。
二叉树有五种表现形式
1. 空的树（没有节点）可以理解为什么都没 像空气一样
2. 只有根节点。 （理解一个人只有一个头 其他的什么都没，说的有点恐怖）
3. 只有左子树 （一个头 一个左手 感觉越来越写不下去了）
4. 只有右子树
5 、左右子树都有
二叉树可以转换成森林 树也可以转换成二叉树。
二叉树遍历
在二叉树的一些应用中，常常要求在树中查找具有某种特征的节点，或者对树中全部节点进行某种处理，这就涉及到二叉树的遍历。二叉树主要是由3个基本单元组成，根节点、左子树和右子树。如果限定先左后右，那么根据这三个部分遍历的顺序不同，可以分为先序遍历、中序遍历和后续遍历三种。
(1) 先序遍历 若二叉树为空，则空操作，否则先访问根节点，再先序遍历左子树，最后先序遍历右子树。
(2) 中序遍历 若二叉树为空，则空操作，否则先中序遍历左子树，再访问根节点，最后中序遍历右子树。
(3) 后序遍历 若二叉树为空，则空操作，否则先后序遍历左子树访问根节点，再后序遍历右子树，最后访问根节点。
时间复杂度
简单来说，时间复杂度即是一个算法运行花费的时间。
如何求？
规模为n的一个算法内基本语句执行次数记为T(n)，此时另一个函数f(n)，当n趋近于无穷大时T(n)/f(n)为一个不等于零的常数，则该算法的时间复杂度记为O(f(n))，简写为O(n)；
如下代码：
for(i=1; i<=n; ++i)
{
for(j=1; j<=n; ++j)
{
c[i][j] = 0;//该步骤属于基本操作执行次数：n的平方次
for(k=1; k<=n; ++k)
c[i][j] += a[i][k] * b[k][j];//该步骤属于基本操作执行次数：n的三次方次
}
}
其时间复杂度为：T(n)=n3+n2，令f(n)=n3，此时T(n)/f(n)满足条件，则该代码的时间复杂度为O(n3)。
常见的算法时间复杂度由小到大依次为：
o(1)<o(log2(n))<o(n)<o(nlog2(n))<o(n2)<o(n3)<...<o(n!)
时间复杂度的分类
最坏时间复杂度：输入数据状态最不理想情况下的时间复杂度，也就是算法时间复杂度的上界。若没有特别声明，时间复杂度就是指最坏时间复杂度。
平均时间复杂度：在所有可能的输入实例均以等概率出现的情况下，算法的期望时间复杂度。
最好时间复杂度：输入数据状态最理想情况下的时间复杂度。
时间复杂度预估步骤
- 找出基本语句：算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
- 计算基本语句的执行次数的数量级：只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
- 用O()表示算法的时间性能：将基本语句执行次数的数量级放入O()中。
时间复杂度分析技巧
- 简单语句：程序的输入输出、赋值等语句都近似认为需要o(1)时间。
- 顺序结构：需要依次执行一系列语句所用的时间可采用O()的"求和法则"，
- 选择结构：如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要o(1)时间。
- 循环结构：循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用O()的"乘法法则"。
- 复杂算法：将其分成几个容易估算的部分,然后利用求和法则和乘法法则计算整个算法的时间复杂度。
空间复杂度
空间复杂度描述算法运行过程中临时占用的存储空间。
算法在计算机上的存储空间包括：
1)算法本身代码的存储空间；
2)算法的数据(输入输出的数据)的存储空间；
3)算法在运行过程中临时占用的存储空间；
如何求？
一般简单算法的空间复杂度为O(1)，一般的递归算法为O(n)，具体的分析需要根据算法中分配存储空间代码所处的位置(此处仅考虑代码本身的存储空间)。
f(n)越小，时间复杂度越低，算法效率越高。
常见算法的时间复杂度和空间复杂度如下：
975503-20170214211234550-1109833343.png
冒泡排序
/**
* 在待排序的数组中，将两个相邻的数依次进行比较和调整，较大的数往下沉，较小的数往上冒；
*
*/
- (void) sortForMaopao:(NSMutableArray*) array{
for (int i=0;i<array.count-1;i++){
// 比较的次数
for (int j=0;j<array.count-1-i; j++) {
if ([array[j] intValue] < [array[j+1] intValue]) {
// 升序排列
id temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
NSLog(@"----maopao-----%@",array);
}
快速排序
/**
* 快速排序是对冒泡排序的改进
* 选择一个基准元素，通常是第一个或最后一个；讲待排序的数组分割成2部分，通常一部分数比基准元素小，另一部分比基准元素大；此时基准元素的位置正确，然后分别对着两部分的元素按照同样的方法进行排序，直到整个序列有序为止
*
*/
- (void) sortForQuick:(NSMutableArray*) array left:(int) left right:(int) right{
if (left >= right) {
return;
}
// 假设中间元素
int key = [array[left] intValue];
int i = left;
int j = right;
while (i < j) {
while (i < j && key <= [array[j] intValue]) {
j--;
}
array[i] = array[j];
while (i < j && key >= [array[i] intValue]) {
i++;
}
array[j] = array[i];
}
array[i] = [NSNumber numberWithInt:key];
[self sortForQuick:array left:left right:i-1];
[self sortForQuick:array left:i+1 right:right];
NSLog(@"----maopao-----%@",array);
}
选择排序
/**
* 在待排序的数组中找一个最大（或最小）的数与第一个记录做替换；然后在剩下的数组中找最大（或最小）的数与第二个记录做替换，以此类推，直到第n-1个数的与第n个数做比较
*
*/
- (void) sortForCheck:(NSMutableArray*) array {
for (int i=0;i<array.count-1; i++) {
for (int j=i+1; j<array.count; j++) {
if ([array[i] intValue] > [array[j] intValue]) {
id temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
NSLog(@"----check-----%@",array);
}
插入排序
/**
* 先将序列的第一个记录看成是一个有序的子序列，然后从第二个记录逐个插入，知道有序为止
*
*/
- (void) sortForInsert:(NSMutableArray*) array {
for (int i=0; i<array.count; i++) {
int j = i;
int temp = [array[i] intValue];
while (j>0 && temp < [array[j-1] intValue]){
[array replaceObjectAtIndex:j withObject:array[j-1]];
j--;
}
[array replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%d",temp]];
}
NSLog(@"----insert-----%@",array);
}
希尔排序
/**
* 希尔排序是对插入排序的改进
* 先将整个带排序的记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，在对整个记录进行直接插入排序
*
*/
- (void) sortForXier:(NSMutableArray*) array {
int flag = array.count / 2;
while (flag >= 1) {
for (int i=flag; i<array.count; i++) {
int j = i;
int temp = [array[i] intValue];
while (j>=flag && temp < [array[j-flag] intValue]){
[array replaceObjectAtIndex:j withObject:array[j-flag]];
j-=flag;
}
[array replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%d",temp]];
}
flag = flag/2;
}
NSLog(@"----xier-----%@",array);
}
二分查找
/**
* 一个有序序列中，取中间的数值作为基数和目标数做比较；如果一致则返回基数位置；如果基数大于或者小于目标数，则从基数的左边或者右边重复上述步骤查找；直到找到对应的数据为止
*
*/
- (NSInteger)binarySearch:(NSArray *)source target:(NSInteger)target {
if (source.count == 0) {
return -1;
}
NSInteger start = 0;
NSInteger end = source.count - 1;
NSInteger mid = 0;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if ([source[mid] integerValue] == target) { // 相邻就退出
return mid;
} else if ([source[mid] integerValue] < target) {
start = mid;
} else {
end = mid;
}
}
if ([source[start] integerValue] == target) {
return start;
}
if ([source[end] integerValue] == target) {
return end;
}
return -1;
}
