iOS开发之数据结构和算法

废话不多说，我们开始～

一、数据结构

1.集合结构、线性结构、树形结构、图形结构

1.集合结构：一个集合中有很多元素，元素与元素之间无任何关系
2.线性结构：一条线上有很多元素（直线、曲线），元素与元素之间是一对一的关系
3.树形结构：想象成金字塔的一种结构，其元素之间是一对多的关系
4.图形结构：无穷、无边、无向，任意图形，其元素之间是多对多的关系

2.数据结构的存储

1.顺序存储结构（栈是先进后出、队列是先进先出---栈砌墙拆墙，队列蛇进出洞）
2.链式存储结构（12345数组存储时，链式存储则可能为1(地址)2(地址)5(地址)3(地址)4(地址)，存储时每个数字后跟着一个地址，而且存储形式不再是顺序，1(地址)1后跟着的这个地址指向的是2，2后面的地址指向3，执行时顺序拿出，存储时不会顺序存储哦而是随机）

3.单向链表、双向链表、循环链表

1.单向链表：A->B->C->D->E，E是头A是尾，形如只有一个车头的火车
2.双向链表：E<-A->B->C->D->E，有头无尾，两个头，两边都可以跑，形如两个头的火车
3.循环链表：->A->B->C->D->E->，绕成一圈

4.二叉树、平衡二叉树（树形结构下的哦）

1.二叉树：树形结构+两个节点以内，分别叫做左子树和右子树，有顺序不能颠倒
    五种表现形式：
    （1）空的树，无节点
    （2）只有根节点
    （3）只有左子树
    （4）只有右子树
    （5）左右子树都有

二、算法

1.冒泡排序

// 1.未排序的数组
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"16", @"28", @"6", @"8",  @"66", nil]

// 2.开始排序
for (int i = 0; i < arr.count - 1; i++)
{
  for (int j = 0; j < arr.count - 1 - i; j++)
  {
    // 比较次数
    if ([arr[j] intValue] > [arr[j + 1] interValue])
    {
      // 升序排序
      int temp = [arr[j] interValue];
      arr[j] = arr[j + 1];
      arr[j + 1] = [NSString stringWithFormat:@"%d", temp];
    }
  }
}

// 3.排序完成咯
NSLog(@"排序结果：%@", arr);

2.选择排序

// 1.未排序的数组
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"16", @"28", @"6", @"8",  @"66", nil]

// 2.开始排序
for (int i = 0; i < arr.count - 1; i++)
{
  for (int j = i + 1; j < arr.count; j++)
  {
    // 比较
    if ([arr[i] intValue] > [arr[j] interValue])
    {
      // 排序
      int temp = [arr[i] interValue];
      arr[i] = arr[j];
      arr[j] = [NSString stringWithFormat:@"%d", temp];
    }
  }
}

// 3.排序完成咯
NSLog(@"排序结果：%@", arr);

3.插入排序

NSMutableArray *list = [NSMutableArray = arrayWithObjects:@"16", @"18", @"6", @"8", @"66", nil];
for (int i = 1; i < [list count]; i++)
{
  int j = i;
  NSInteger temp = [[list objectAtIndex:i] integerValue];
  while (j > 0 && temp < [[list objectAtIndex:j-1] integerValue])
  {
      [list replaceObjectAtIndex:J withObject:[list objectAtIndex:(j - 1)]];
      j--;
  }
  [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
NSLog(@"输出结果：%@", list);

4.希尔排序

NSMutableArray *list = [NSMutableArray = arrayWithObjects:@"16", @"18", @"6", @"8", @"66", nil];
int gap = [list count] / 2.0;
while (gap >= 1)
{
  for (int I = gap; i < [list count]; i++)
  {
      NSInteger temp = [[list objectAtIndex:i] integerValue];
      int j = I;
      while (j >= gap && temp < [[list objectAtIndex:(j-gap)] integerValue])
      {
        [list replaceObjectAtIndex:j withObject:[list objectAtIndex:j - gap]];
      }
      [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
  }
  gap = gap / 2;
}
NSLog(@"输出结果：%@", list);

1.二分查找
if (low < height)
{
  NSInteger mid = (low + height) / 2;
  if (key == arr[mid])
  {
    return mid;
  } else if (key < arr[mid])
  {
    return [self erFenChaZhaoSuanFa:arr low:low High:mid - 1 Data:key];
  } else
  {
    return [self erFenChaZhaoSuanFa:arr low:mid + 1 High:hight Data:key];
  }
} else 
{
  NSLog(@"参数错误");
  return -1;
}
2.快排
- (void)kuaisupaixu:(NSMutableArray *)arr low:(NSInteger)left High:(NSInteger)right
{
  if(left <= right) return;
  NSInteger I = left;
  NSInteger j = right;
  NSInteger key = [arr[left] integerValue];

  while (I < j) {
    while (I < j && key <= [arr[j] integerValue]) {
      j--;
    }
    arr[i] = arr[j];
    while (I < j && key >= [arr[I] integerValue]) {
      I++;
    }
    arr[j] = arr[i];
   }
    arr[i] = [NSNumber numberWithInteger:key];
    [self kuaisupaixu:arr low:left high:i-1];
    [self kuaisupaixu:arr low:i+1 high:right];
}

参考文章
iOS数据结构 和 算法 上