区块链技术博客
www.b2bchain.cn

iOS —— 排序算法&&二叉树遍历求职学习资料

本文介绍了iOS —— 排序算法&&二叉树遍历求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

一、排序算法

1、冒泡排序

  • (1)算法原理:(升序)进行 n-1 趟的相邻比较,大的放在右边,每趟拿到一个最大值放在最右边
  • (2)时间复杂度:n(n-1)/2
  • (3)代码
+ (NSMutableArray *)mapaoSort:(NSMutableArray *)array {     NSInteger count = 0;     for (int i=0; i<array.count-1; i++) {         for (int j=0; j<array.count-1-i; j++) {             if ([array[j] integerValue] > [array[j+1] integerValue]) {                 [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];             }             count++;         }     }     NSLog(@"count=%zu",count);     return array; }

2、鸡尾酒排序

  • (1)算法原理:(升序)先找到最小的数字,把他放到第一位,然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到低位大于等于高位
  • (2)时间复杂度:n(n-1)/2
  • (3)代码
+ (NSMutableArray *)jiweijiuSort:(NSMutableArray *)array {     NSInteger count = 0;     NSInteger low = 0;     NSInteger high = array.count-1;     while (low < high) {         for (NSInteger i=low+1; i<=high; i++) {             if ([array[low] integerValue] > [array[i] integerValue]) {                 [array exchangeObjectAtIndex:low withObjectAtIndex:i];             }             count++;         }         low++;          for (NSInteger j=high-1; j>=low; j--) {             if ([array[high] integerValue] < [array[j] integerValue]) {                 [array exchangeObjectAtIndex:high withObjectAtIndex:j];             }             count++;         }         high--;     }     NSLog(@"count=%zu",count);     return array; }

3、选择排序

  • (1)算法原理:(算法原理:进行 n-1 趟,每趟找出一个最值
  • (2)时间复杂度:n(n-1)/2
  • (3)代码
+ (NSMutableArray *)selectSort:(NSMutableArray *)array {     NSInteger count = 0;     for (int i=0; i<array.count-1; i++) {         NSInteger min = [array[i] integerValue];         NSInteger index = i;         for (NSInteger j=i+1; j<array.count; j++) {              if (min > [array[j] integerValue]) {                 min = [array[j] integerValue];                 index = j;             }             count++;         }         [array exchangeObjectAtIndex:index withObjectAtIndex:i];     }     NSLog(@"count=%zu",count);     return array; }

4、插入排序

  • (1)算法原理:向有序的队列增加新值
  • (2)时间复杂度:<n(n-1)/2
  • (3)代码
+ (NSMutableArray *)insertSort:(NSMutableArray *)array {     if (array.count == 0) {         return array;     }     NSMutableArray *results = [NSMutableArray arrayWithObject:array[0]];     NSInteger count = 0;     for (NSInteger i=1; i<array.count; i++) {         for (NSInteger j=0; j<results.count; j++) {             count++;             if ([array[i] integerValue] < [results[0] integerValue]) {                 [results insertObject:array[i] atIndex:0];                 break;             }             if ([array[i] integerValue] >= [results[results.count-1] integerValue]) {                 [results addObject:array[i]];                 break;             }             if (j+1 < results.count && [array[i] integerValue] >= [results[j] integerValue] && [array[i] integerValue] <= [results[j+1] integerValue]) {                  [results insertObject:array[i] atIndex:j+1];                 break;             }         }      }     NSLog(@"count=%zu",count);     return results; }

优化写法:

- (NSMutableArray *)insertSort:(NSMutableArray *)array {      NSMutableArray *results = [NSMutableArray arrayWithArray:@[array[0]]];     for (int i = 1; i < array.count; i++) {         NSNumber *num = array[i];         NSInteger insertIndex = 0;         if (num.intValue < [results.firstObject intValue]) {             insertIndex = 0;         }else if (num.intValue > [results.lastObject intValue]) {             insertIndex = results.count;         }else {             for (int j = 0; j < results.count; j++) {                 if (j+1 < results.count && num.intValue > [results[j]intValue]  && num.intValue < [results[j+1]intValue]) {                     insertIndex = j+1;                 }             }         }          [results insertObject:num atIndex:insertIndex];     }     return results; }

5、二分插入排序

  • (1)算法原理:基于插入排序。由于插入排序是向有序的队列进行插入,那么在有序的队列中,我们可以使用更高效二分法去查找位置,而不需要从头到尾地遍历
  • (2)时间复杂度:<插入排序
  • (3)代码
+ (NSMutableArray *)halfInsertSort:(NSMutableArray *)array {     if (array.count == 0) {         return array;     }     NSMutableArray *results = [NSMutableArray arrayWithObject:array[0]];     NSInteger count = 0;     for (NSInteger i=1; i<array.count; i++) {         NSInteger low = 0;         NSInteger high = results.count-1;          while (low<=high) {             NSInteger mid = (low+high)/2;             if ([array[i] integerValue] >= [results[mid] integerValue]) {                 low = mid+1;             } else {                 high = mid-1;             }             count++;         }          [results insertObject:array[i] atIndex:low];     }     NSLog(@"count=%zu",count);     return results; }

6、快速排序

  • (1)算法原理:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
  • (2)时间复杂度:N*logN~N方
  • (3)代码

“`

一、排序算法

1、冒泡排序

  • (1)算法原理:(升序)进行 n-1 趟的相邻比较,大的放在右边,每趟拿到一个最大值放在最右边
  • (2)时间复杂度:n(n-1)/2
  • (3)代码
+ (NSMutableArray *)mapaoSort:(NSMutableArray *)array {     NSInteger count = 0;     for (int i=0; i<array.count-1; i++) {         for (int j=0; j<array.count-1-i; j++) {             if ([array[j] integerValue] > [array[j+1] integerValue]) {                 [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];             }             count++;         }     }     NSLog(@"count=%zu",count);     return array; }

2、鸡尾酒排序

  • (1)算法原理:(升序)先找到最小的数字,把他放到第一位,然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到低位大于等于高位
  • (2)时间复杂度:n(n-1)/2
  • (3)代码
+ (NSMutableArray *)jiweijiuSort:(NSMutableArray *)array {     NSInteger count = 0;     NSInteger low = 0;     NSInteger high = array.count-1;     while (low < high) {         for (NSInteger i=low+1; i<=high; i++) {             if ([array[low] integerValue] > [array[i] integerValue]) {                 [array exchangeObjectAtIndex:low withObjectAtIndex:i];             }             count++;         }         low++;          for (NSInteger j=high-1; j>=low; j--) {             if ([array[high] integerValue] < [array[j] integerValue]) {                 [array exchangeObjectAtIndex:high withObjectAtIndex:j];             }             count++;         }         high--;     }     NSLog(@"count=%zu",count);     return array; }

3、选择排序

  • (1)算法原理:(算法原理:进行 n-1 趟,每趟找出一个最值
  • (2)时间复杂度:n(n-1)/2
  • (3)代码
+ (NSMutableArray *)selectSort:(NSMutableArray *)array {     NSInteger count = 0;     for (int i=0; i<array.count-1; i++) {         NSInteger min = [array[i] integerValue];         NSInteger index = i;         for (NSInteger j=i+1; j<array.count; j++) {              if (min > [array[j] integerValue]) {                 min = [array[j] integerValue];                 index = j;             }             count++;         }         [array exchangeObjectAtIndex:index withObjectAtIndex:i];     }     NSLog(@"count=%zu",count);     return array; }

4、插入排序

  • (1)算法原理:向有序的队列增加新值
  • (2)时间复杂度:<n(n-1)/2
  • (3)代码
+ (NSMutableArray *)insertSort:(NSMutableArray *)array {     if (array.count == 0) {         return array;     }     NSMutableArray *results = [NSMutableArray arrayWithObject:array[0]];     NSInteger count = 0;     for (NSInteger i=1; i<array.count; i++) {         for (NSInteger j=0; j<results.count; j++) {             count++;             if ([array[i] integerValue] < [results[0] integerValue]) {                 [results insertObject:array[i] atIndex:0];                 break;             }             if ([array[i] integerValue] >= [results[results.count-1] integerValue]) {                 [results addObject:array[i]];                 break;             }             if (j+1 < results.count && [array[i] integerValue] >= [results[j] integerValue] && [array[i] integerValue] <= [results[j+1] integerValue]) {                  [results insertObject:array[i] atIndex:j+1];                 break;             }         }      }     NSLog(@"count=%zu",count);     return results; }

优化写法:

- (NSMutableArray *)insertSort:(NSMutableArray *)array {      NSMutableArray *results = [NSMutableArray arrayWithArray:@[array[0]]];     for (int i = 1; i < array.count; i++) {         NSNumber *num = array[i];         NSInteger insertIndex = 0;         if (num.intValue < [results.firstObject intValue]) {             insertIndex = 0;         }else if (num.intValue > [results.lastObject intValue]) {             insertIndex = results.count;         }else {             for (int j = 0; j < results.count; j++) {                 if (j+1 < results.count && num.intValue > [results[j]intValue]  && num.intValue < [results[j+1]intValue]) {                     insertIndex = j+1;                 }             }         }          [results insertObject:num atIndex:insertIndex];     }     return results; }

5、二分插入排序

  • (1)算法原理:基于插入排序。由于插入排序是向有序的队列进行插入,那么在有序的队列中,我们可以使用更高效二分法去查找位置,而不需要从头到尾地遍历
  • (2)时间复杂度:<插入排序
  • (3)代码
+ (NSMutableArray *)halfInsertSort:(NSMutableArray *)array {     if (array.count == 0) {         return array;     }     NSMutableArray *results = [NSMutableArray arrayWithObject:array[0]];     NSInteger count = 0;     for (NSInteger i=1; i<array.count; i++) {         NSInteger low = 0;         NSInteger high = results.count-1;          while (low<=high) {             NSInteger mid = (low+high)/2;             if ([array[i] integerValue] >= [results[mid] integerValue]) {                 low = mid+1;             } else {                 high = mid-1;             }             count++;         }          [results insertObject:array[i] atIndex:low];     }     NSLog(@"count=%zu",count);     return results; }

6、快速排序

  • (1)算法原理:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
  • (2)时间复杂度:N*logN~N方
  • (3)代码

“`

一、排序算法

1、冒泡排序

  • (1)算法原理:(升序)进行 n-1 趟的相邻比较,大的放在右边,每趟拿到一个最大值放在最右边
  • (2)时间复杂度:n(n-1)/2
  • (3)代码
+ (NSMutableArray *)mapaoSort:(NSMutableArray *)array {     NSInteger count = 0;     for (int i=0; i<array.count-1; i++) {         for (int j=0; j<array.count-1-i; j++) {             if ([array[j] integerValue] > [array[j+1] integerValue]) {                 [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];             }             count++;         }     }     NSLog(@"count=%zu",count);     return array; }

2、鸡尾酒排序

  • (1)算法原理:(升序)先找到最小的数字,把他放到第一位,然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到低位大于等于高位
  • (2)时间复杂度:n(n-1)/2
  • (3)代码
+ (NSMutableArray *)jiweijiuSort:(NSMutableArray *)array {     NSInteger count = 0;     NSInteger low = 0;     NSInteger high = array.count-1;     while (low < high) {         for (NSInteger i=low+1; i<=high; i++) {             if ([array[low] integerValue] > [array[i] integerValue]) {                 [array exchangeObjectAtIndex:low withObjectAtIndex:i];             }             count++;         }         low++;          for (NSInteger j=high-1; j>=low; j--) {             if ([array[high] integerValue] < [array[j] integerValue]) {                 [array exchangeObjectAtIndex:high withObjectAtIndex:j];             }             count++;         }         high--;     }     NSLog(@"count=%zu",count);     return array; }

3、选择排序

  • (1)算法原理:(算法原理:进行 n-1 趟,每趟找出一个最值
  • (2)时间复杂度:n(n-1)/2
  • (3)代码
+ (NSMutableArray *)selectSort:(NSMutableArray *)array {     NSInteger count = 0;     for (int i=0; i<array.count-1; i++) {         NSInteger min = [array[i] integerValue];         NSInteger index = i;         for (NSInteger j=i+1; j<array.count; j++) {              if (min > [array[j] integerValue]) {                 min = [array[j] integerValue];                 index = j;             }             count++;         }         [array exchangeObjectAtIndex:index withObjectAtIndex:i];     }     NSLog(@"count=%zu",count);     return array; }

4、插入排序

  • (1)算法原理:向有序的队列增加新值
  • (2)时间复杂度:<n(n-1)/2
  • (3)代码
+ (NSMutableArray *)insertSort:(NSMutableArray *)array {     if (array.count == 0) {         return array;     }     NSMutableArray *results = [NSMutableArray arrayWithObject:array[0]];     NSInteger count = 0;     for (NSInteger i=1; i<array.count; i++) {         for (NSInteger j=0; j<results.count; j++) {             count++;             if ([array[i] integerValue] < [results[0] integerValue]) {                 [results insertObject:array[i] atIndex:0];                 break;             }             if ([array[i] integerValue] >= [results[results.count-1] integerValue]) {                 [results addObject:array[i]];                 break;             }             if (j+1 < results.count && [array[i] integerValue] >= [results[j] integerValue] && [array[i] integerValue] <= [results[j+1] integerValue]) {                  [results insertObject:array[i] atIndex:j+1];                 break;             }         }      }     NSLog(@"count=%zu",count);     return results; }

优化写法:

- (NSMutableArray *)insertSort:(NSMutableArray *)array {      NSMutableArray *results = [NSMutableArray arrayWithArray:@[array[0]]];     for (int i = 1; i < array.count; i++) {         NSNumber *num = array[i];         NSInteger insertIndex = 0;         if (num.intValue < [results.firstObject intValue]) {             insertIndex = 0;         }else if (num.intValue > [results.lastObject intValue]) {             insertIndex = results.count;         }else {             for (int j = 0; j < results.count; j++) {                 if (j+1 < results.count && num.intValue > [results[j]intValue]  && num.intValue < [results[j+1]intValue]) {                     insertIndex = j+1;                 }             }         }          [results insertObject:num atIndex:insertIndex];     }     return results; }

5、二分插入排序

  • (1)算法原理:基于插入排序。由于插入排序是向有序的队列进行插入,那么在有序的队列中,我们可以使用更高效二分法去查找位置,而不需要从头到尾地遍历
  • (2)时间复杂度:<插入排序
  • (3)代码
+ (NSMutableArray *)halfInsertSort:(NSMutableArray *)array {     if (array.count == 0) {         return array;     }     NSMutableArray *results = [NSMutableArray arrayWithObject:array[0]];     NSInteger count = 0;     for (NSInteger i=1; i<array.count; i++) {         NSInteger low = 0;         NSInteger high = results.count-1;          while (low<=high) {             NSInteger mid = (low+high)/2;             if ([array[i] integerValue] >= [results[mid] integerValue]) {                 low = mid+1;             } else {                 high = mid-1;             }             count++;         }          [results insertObject:array[i] atIndex:low];     }     NSLog(@"count=%zu",count);     return results; }

6、快速排序

  • (1)算法原理:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
  • (2)时间复杂度:N*logN~N方
  • (3)代码

“`

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » iOS —— 排序算法&&二叉树遍历求职学习资料
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们