常用算法

[iOS常用算法和数据结构]

数据结构通常分为四类：

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

1.1、集合结构：就是一个集合，就是一个圆圈中有很多个元素，元素与元素之间没有任何关系 。

1.2、线性结构 ：就是一个条线上站着很多个人。 这条线不一定是直的。也可以是弯的。也可以是值的 相当于一条线被分成了好几段的样子。 线性结构是一对一的关系。

1.3、树形结构 ：做开发的肯定或多或少的知道xml 解析 树形结构跟他非常类似。也可以想象成一个金字塔。树形结构是一对多的关系

1.4、图形结构：这个就比较复杂了。 无穷、无边、 无向（没有方向）图形机构 你可以理解为多对多 类似于我们人的交集关系。

2. 数据结构的存储

  数据结构的存储一般常用的有两种   顺序存储结构 和 链式存储结构。

2.1 顺序存储结构

  举个列子。数组。1-2-3-4-5-6-7-8-9-10。这个就是一个顺序存储结构 ，存储是按顺序的 栈。做开发的都熟悉。栈是先进后出 ，后进先出的形式。hello world 在栈里面从栈底到栈顶的逻辑依次为 h-e-l-l-o-w-o-r-l-d 这就是顺序存储 再比如 队列 ，队列是先进先出的对吧，从头到尾 h-e-l-l-o-w-o-r-l-d 就是这样排对的。

2.2 链式存储结构

  1-2-3-4-5-6-7-8-9-10  链式存储就不一样了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每个数字后面跟着一个地址 而且存储形式不再是顺序 ，也就说顺序乱了，1（地址） 1后面跟着的这个地址指向的是2，2后面的地址指向的是3，3后面的地址指向是谁你应该清楚了吧。他执行的时候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存储的时候就是完全随机的。

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

3.1 单向链表

      A->B->C->D->E->F->G->H. 这就是单向链表  H 是头 A 是尾  像一个只有一个头的火车一样 只能一个头拉着跑

3.2 双向链表

 H<- A->B->C->D->E->F->G->H. 这就是双向链表。有头没尾。两边都可以跑  跟地铁一样 到头了 可以倒着开回来

3.3 循环链表

 A->B->C->D->E->F->G->H. 绕成一个圈。就像蛇吃自己的这就是循环。

4.二叉树／平衡二叉树

4.1 什么是二叉树

  树形结构下,两个节点以内 都称之为二叉树 不存在大于2 的节点 分为左子树 右子树 有顺序 不能颠倒。

二叉树有五种表现形式

 1\. 空的树（没有节点）可以理解为什么都没 像空气一样

2\. 只有根节点。 （理解一个人只有一个头 其他的什么都没，说的有点恐怖）

3\. 只有左子树 （一个头 一个左手 感觉越来越写不下去了）

4\. 只有右子树

5 、左右子树都有

二叉树可以转换成森林 树也可以转换成二叉树。

5.算法，冒泡排序、选择排序、插入排序、快速排序、二分法查找、希尔排序、戴克斯特拉算法，快捷算法，动态规划，堆排序，归并排序。

** 5.1 冒泡排序**

1. 首先将所有待排序的数字放入工作列表中。

2. 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。

3. 重复2号步骤(倒数的数字加1。例如：第一次到倒数第二个数字，第二次到倒数第三个数字，依此类推...)，直至再也不能交换。

平均时间复杂度：O(n^2)

平均空间复杂度：O(1)

-(void)maoPao{//冒泡排序

NSMutableArray *arr=[NSMutableArray arrayWithArray:@[@"17",@"28",@"36",@"15",@"29",@"39"]];

for (int i=0;i<arr.count;i++) {

    for (int j=0; j<arr.count-1-i; j++) {

        if ([arr[j] intValue]>[arr[j+1] intValue]) {

            int temp=[arr[j] intValue];

            arr[j]=arr[j+1];

            arr[j+1]=[NSString stringWithFormat:@"%d",temp];

        }

    }

}

NSLog(@"%@",arr);

}

5.2 选择排序

1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。

2. I=1

3. 从数组的第i个元素开始到第n个元素，寻找最小的元素。（具体过程为:先设arr[i]为最小，逐一比较，若遇到比之小的则交换）

4. 将上一步找到的最小元素和第i位元素交换。

5. 如果i=n－1算法结束，否则回到第3步

平均时间复杂度：O(n^2)

平均空间复杂度：O(1)

-(void)xuanZe{//选择排序

NSMutableArray *arr=[NSMutableArray arrayWithArray:@[@"17",@"28",@"36",@"15",@"29",@"39"]];

for (int i=0;i<arr.count-1;i++) {

    for (int j=i+1; j<arr.count; j++) {

        if ([arr[i] intValue]>[arr[j] intValue]) {

            int temp=[arr[i] intValue];

            arr[i]=arr[j];

            arr[j]=[NSString stringWithFormat:@"%d",temp];

        }

    }

}

NSLog(@"%@",arr);

}

5.3 插入排序

1. 从第一个元素开始，认为该元素已经是排好序的。

2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。

3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。

4. 重复步骤3，直到已排好序的元素小于或等于新元素。

5. 在当前位置插入新元素。

6. 重复步骤2。

平均时间复杂度：O(n^2)

平均空间复杂度：O(1)

-(void)chaRu{//插入排序

NSMutableArray *arr=[NSMutableArray arrayWithArray:@[@"17",@"28",@"36",@"15",@"29",@"39"]];

for (int i=1;i<arr.count;i++) {

    int j=I;

    NSInteger temp=[[arr objectAtIndex:i]integerValue];

    while (j>0&&temp<[[arr objectAtIndex:j-1]integerValue]) {

        [arr replaceObjectAtIndex:j withObject:[arr objectAtIndex:(j-1)]];

        j--;

    }

    [arr replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];

}

NSLog(@"%@",arr);

}

5.4 希尔排序

-(void)xiEr{//希尔排序

NSMutableArray *arr=[NSMutableArray arrayWithArray:@[@"17",@"28",@"36",@"15",@"29",@"39"]];

NSInteger gap=arr.count/2;

while (gap>=1) {

    for (NSInteger i=gap; i<arr.count; i++) {

        NSInteger temp=[[arr objectAtIndex:i] integerValue];

        NSInteger j=I;

        while (j>=gap&&temp<[[arr objectAtIndex:(j-gap)] integerValue]) {\

            [arr replaceObjectAtIndex:j withObject:[arr objectAtIndex:j-gap]];

            j-=gap;

        }

        [arr replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];

    }

    gap=gap/2;

}

NSLog(@"%@",arr);

}

5.5 二分法查找

当数据量很大适宜采用该方法。 采用二分法查找时，数据需是排好序的。

基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段 中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

- (NSInteger)BinarySearch:(NSArray *)array target:(id)key{//二分法查找

    NSInteger left = 0;    

    NSInteger right = [array count] - 1;

    NSInteger middle = [array count] / 2;

    while (right >= left) {

        middle = (right + left) / 2;

        if (array[middle] == key) {

            return middle;

        }

        if (array[middle] > key) {

            right = middle - 1;

        }

        else if (array[middle] < key) {

            left = middle + 1;

        }        

    }

    return -1;

}

5.6 快速排序

1. 从数列中挑出一个元素，称为 "基准"（pivot），

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

平均时间复杂度：O(n^2)

平均空间复杂度：O(nlogn) O(nlogn)~O(n^2)

• (NSMutableArray *)QuickSorkOC:(NSMutableArray *)array Count:(NSInteger)count{//快速排序

  NSInteger i = 0;

  NSInteger j = count - 1;

  id pt = array[0];

  if (count > 1) {

    while (i < j) {
  
        for (; j > i; --j) {
  
            if (array[j] < pt) {
  
                array[i++] = array[j];
  
                break;
  
            }
  
        }
  
        for (; i < j; ++i) {
  
            if (array[i] > pt) {
  
                array[j--] = array[I];
  
                break;
  
            }
  
        }
  
        array[i] = pt;
  
        [self QuickSorkOC:array Count:i];
  
        [self QuickSorkOC:array Count:count - i - 1];
  
    }
  

  }

  return array;

}

5.7 归并排序

把序列分成元素尽可能相等的两半。

把两半元素分别进行排序。

把两个有序表合并成一个。

• (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr

{

NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];

for (NSNumber *num in ascendingArr) {

    NSMutableArray *subArray = [NSMutableArray array];

    [subArray addObject:num];

    [tempArray addObject:subArray];

}

while (tempArray.count != 1) {

    NSInteger i = 0;

    while (i < tempArray.count - 1) {

        tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];

        [tempArray removeObjectAtIndex:i + 1];

        I++;

    }

}

NSLog(@"归并升序排序结果：%@", ascendingArr);

}

• (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {

  NSMutableArray *resultArray = [NSMutableArray array];

  NSInteger firstIndex = 0, secondIndex = 0;

  while (firstIndex < array1.count && secondIndex < array2.count) {

    if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
  
        [resultArray addObject:array1[firstIndex]];
  
        firstIndex++;
  
    } else {
  
        [resultArray addObject:array2[secondIndex]];
  
        secondIndex++;
  
    }
  

  }

  while (firstIndex < array1.count) {

    [resultArray addObject:array1[firstIndex]];
  
    firstIndex++;
  

  }

  while (secondIndex < array2.count) {

    [resultArray addObject:array2[secondIndex]];
  
    secondIndex++;
  

  }

  return resultArray.copy;

}

5.8 基数排序

• (void)radixAscendingOrderSort:(NSMutableArray *)ascendingArr

{

NSMutableArray *buckt = [self createBucket];

NSNumber *maxnumber = [self listMaxItem:ascendingArr];

NSInteger maxLength = numberLength(maxnumber);

for (int digit = 1; digit <= maxLength; digit++) {

    // 入桶

    for (NSNumber *item in ascendingArr) {

        NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];

        NSMutableArray *mutArray = buckt[baseNumber];

        [mutArray addObject:item];

    }

    NSInteger index = 0;

    for (int i = 0; i < buckt.count; i++) {

        NSMutableArray *array = buckt[I];

        while (array.count != 0) {

            NSNumber *number = [array objectAtIndex:0];

            ascendingArr[index] = number;

            [array removeObjectAtIndex:0];

            index++;

        }

    }

}

NSLog(@"基数升序排序结果：%@", ascendingArr);

}