算法其实在实际应用中比较少,因为一般的APP用不到算法也可以很好的开发,但如果真的用到的还是很不好找的,我就在网上收集一些
1.线性查找
/// 冒泡排序
+ (void)bubbleSortWithArray:(NSMutableArray *)array withFirst:(NSInteger)first withEnd:(NSInteger)end{
for (NSInteger i = first ; i < end; i++) {
for (NSInteger j = end; j > i; j--) {
if (array[j] < array[j-1]) {
id temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
}
+ (void)bubbleSortWithArray:(NSMutableArray *)array{
return [self bubbleSortWithArray:array withFirst:0 withEnd:[array count] - 1];
}
//求取最小的k个数
//数组a中从a[p]到a[r]的元素按照x划分,大于或者等于x的在右边,小于x的在左边
+ (NSInteger)partitionModify:(NSMutableArray *)a withP:(NSInteger)p withR:(NSInteger)r withX:(NSInteger)x{
NSInteger i,j;
j = r;
for (i = p; i < j; i++) {
if ([a[i] integerValue] >= x) {
while (i<j && [a[j] integerValue] >= x) j--;
if (i != j) {
id t = a[i];
a[i] = a[j];
a[j] = t;
j--;
}
else break;
}
} /*上面的循环结束分为几种情况
1 i > j 此时必定有 a[i] >= x，否则 a[j+1] = a[i] < x 与 a[j+1] >= x 矛盾 ,如果不是边界，进入if语句
2 i = j 此时如果 a[i] < x 则a[i+1] = a[j+1] >x 返回 i
3 当i==p,此时直接返回边界元素下标
4 当i == r,此时为右边界，此时a[i]肯定为x，返回i - 1，也即r - 1
*/
if ([a[i] integerValue] >= x && i > p) {
return i - 1;
}
return i;
}
//将r-p+1个数据按五个元素分为一组，分别找出各组的中位数，
//再将各组的中位数与数组开头的数据在组的顺序依次交换，对这些各组的中位数
//按同样的方法继续求出中位数，最后得出的整个数组的中位数，利用中位数就可以将数据按照与中位数的比较来划分
+ (NSInteger)selectModify:(NSMutableArray *)array withP:(NSInteger)p withR:(NSInteger)r withK:(NSInteger)k{
NSInteger i;
if (r - p + 1 <= 5) {
[self bubbleSortWithArray:array withFirst:p withEnd:r];
return [array[p + k - 1] integerValue];
}
//将r-p+1个数据按五个元素分为一组，可以分为(r - p + 1) / 5组
//分别找出各组的中位数，再将各组的中位数与数组开头的数据按组的顺序依次交换
for (i = 0; i < (r-p+1)/5;i++ ) {
NSInteger s = p + 5*i,t=s+4;
[self bubbleSortWithArray:array withFirst:s withEnd:t];
id temp = array[p + i];
array[p + i] = array[s + 2];
array[s + 2] = temp;
}
//对这些各组的中位数
//按同样的方法继续求出中位数，最后得出的整个数组的中位数 x
NSInteger x = [self selectModify:array withP:p withR: p + (r - p + 1) / 5 - 1 withK:(r - p + 6) / 10];
i = [self partitionModify:array withP:p withR:r withX:x];
NSInteger j = i - p + 1;
if (k <= j) {
return [self selectModify:array withP:p withR:i withK:k];
}else{
return [self selectModify:array withP:i+1 withR:r withK:k-j];
}
}
+ (NSInteger)selectModify:(NSMutableArray *)array withNum:(NSInteger)n{
if (n == 0 || n > [array count]) return -1;// 未查到
return [self selectModify:array withP:0 withR:[array count] - 1 withK:n];
}
2.插入排序
+ (void)insertSort:(NSMutableArray *)list{
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]];
}
}
+ (void)binaryInsertSort:(NSMutableArray *)list{
for (int i = 1; i < [list count]; i++) {
NSInteger temp = [[list objectAtIndex:i] integerValue];
int left = 0;
int right = i - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (temp < [[list objectAtIndex:middle] integerValue]) {
right = middle - 1;
}else{
left = middle + 1;
}
}
for (int j = i; j > left; j--) {
[list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-1]];
}
[list replaceObjectAtIndex:left withObject:[NSNumber numberWithInteger:temp]];
}
}
3.戴克斯特拉算法
+ (NSArray *)dijkstra_alg:(NSMutableArray *)map withShotest:(NSMutableArray *)shortest withV:(NSMutableArray *)visited withO:(NSInteger)orig{
NSInteger n = [shortest count];
if ( n - 1 <= 0) return nil;
// 初始化，第一个顶点求出
shortest[orig] = @(0);
visited[orig] = @(YES);
// 要加入n-1个顶点
for (int p = 0; p != n - 1; p++) {
// 选出一个距离初始顶点最近的未标记顶点
int k = -1;
int min = -1;
for (int i = 0; i < n; i++) {
if ([visited[i] compare:@(0)] == NSOrderedSame && [map[orig][i] intValue] != -1) {
if (min == -1 || min > [map[orig][i] intValue]) {
min = [map[orig][i] intValue];
k = i;
}
}
}
// 正确的图生成的矩阵不可能出现K == M的情况
if (k == -1) {
NSLog(@"the input map matrix is wrong!");
return nil;
}
shortest[k] = @(min);
visited[k] = @(YES);
for (int i = 0; i < n; i++) {
if ([visited[i] compare:@(0)] == NSOrderedSame && [map[k][i] intValue] != -1) {
int callen = min + [map[k][i] intValue];
if ([map[orig][i] intValue] == -1 || [map[orig][i] intValue] > callen) {
map[orig][i] = @(callen);
}
}
}
}
return shortest;
}
+(NSArray *)dijkstra:(NSMutableArray *)map withOrig:(NSInteger)orig{
NSInteger n = [map count];
NSMutableArray *shortest = [NSMutableArray arrayWithCapacity:n];
NSMutableArray *visited = [NSMutableArray arrayWithCapacity:n];
for (int i = 0; i < n; i++) {
[shortest addObject:@(-1)];
[visited addObject:@(NO)];
}
return [self dijkstra_alg:map withShotest:shortest withV:visited withO:orig];
}
4.动态规划
+ (NSString *)getRandomString:(NSInteger)length{
NSString *str = @"abcdefghijklmnopqrstuvwxyz";
NSMutableString *res = [[NSMutableString alloc] initWithCapacity:length];
for (int i = 0; i < length; i++) {
NSRange range;
range.length = 1;
range.location = arc4random()%length;
NSString *r = [str substringWithRange:range];
[res appendString:r];
}
return res;
}
+ (NSString *)lcs:(NSString *)str1 withOtherString:(NSString *)str2{
int length1 = (int)[str1 length];
int length2 = (int)[str2 length];
NSMutableArray *p1 = [NSMutableArray arrayWithCapacity:length2 + 1];
// 构造二维数组记录子问题x[i]和y[i]的LCS的长度
NSMutableArray *opt = [NSMutableArray arrayWithCapacity:length1 + 1];
for (int i = 0; i < length2 + 1; i++) {
[p1 addObject:@0];
}
for (int i = 0; i < length1 + 1; i++) {
[opt addObject:p1];
}
for (int i = length1 - 1; i >= 0; i--) {
for (int j = length2 - 1; j >= 0; j--) {
NSRange range1 = {i,1};
NSRange range2 = {j,1};
if ([[str1 substringWithRange:range1] isEqualToString:[str2 substringWithRange:range2]]) {
opt[i][j] = @([opt[i+1][j+1] integerValue] + 1);
}else{
int i1 = [opt[i+1][j] intValue] , i2 = [opt[i][j+1] intValue];
opt[i][j] = @(MAX(i1,i2));
}
}
}
int i = 0,j = 0;
NSMutableString *result = [[NSMutableString alloc] init];
while (i < length1 && j < length2) {
NSRange range1 = {i,1};
NSRange range2 = {j,1};
if ([[str1 substringWithRange:range1] isEqualToString:[str2 substringWithRange:range2]]) {
[result appendString:[str1 substringWithRange:range1]];
i++;
j++;
}else if([opt[i + 1][j] intValue] >= [opt[i][j + 1] intValue]){
i++;
}else{
j++;
}
}
return result;
}
5.堆排序
/// 最大堆heap 最大／最小优先级队列
+ (void)createBiggestHeap:(NSMutableArray *)list withSize:(int)size beIndex:(int)element{
int lchild = element * 2 + 1,rchild = lchild + 1;//左右子树
while (rchild < size) {//子树均在范围内
//如果比左右子树都小，完成整理
if (list[element] <= list[lchild] && list[element] <= list[rchild]) return;
//如果左边最小
if(list[lchild] <= list[rchild]){
[list exchangeObjectAtIndex:element withObjectAtIndex:lchild];//把左面的提到上面
element = lchild;//循环时整理子树
}else{
//否则右面最小
[list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
element = rchild;
}
lchild = element * 2 + 1;
rchild = lchild + 1;//重新计算子树位置
}
//只有左子树且子树小于自己
if (lchild < size && list[lchild] < list[element]) {
[list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
}
}
//堆排序time:O(nlgn)
+ (void)heapSort:(NSMutableArray *)list{
int i , size;
size = [list count]/1.0;
// 从子树开始整理树
for (i = [list count]/1.0 - 1; i >= 0; i--) {
[self createBiggestHeap:list withSize:size beIndex:i];
}
//拆除树
while (size > 0) {
[list exchangeObjectAtIndex:size - 1 withObjectAtIndex:0];//将根（最小）与数组最末交换
size--;//树大小减小
[self createBiggestHeap:list withSize:size beIndex:0];//整理树
}
}
6.二叉树
/**
- 生成二叉树
- @param values 数组
- @return 二叉树
*/
+ (BinaryTreeNode *)createTreeWithValues:(NSArray *)values {
BinaryTreeNode *root = nil;
for (NSInteger i=0; i<values.count; i++) {
NSInteger value = [(NSNumber *)[values objectAtIndex:i] integerValue];
root = [[self class] addTreeNode:root value:value];
}
return root;
}
/**
翻转二叉树（非递归）
@param rootNode 根节点
-
@return 翻转后的树根节点（其实就是原二叉树的根节点）
*/
+ (BinaryTreeNode *)invertBinaryTreeWithoutRecursion:(BinaryTreeNode *)rootNode {
if (!rootNode) { return nil; }
if (!rootNode.leftNode && !rootNode.rightNode) { return rootNode; }
NSMutableArray *queueArray = [NSMutableArray array]; //数组当成队列
[queueArray addObject:rootNode]; //压入根节点
while (queueArray.count > 0) {
BinaryTreeNode *node = [queueArray firstObject];
[queueArray removeObjectAtIndex:0]; //弹出最前面的节点，仿照队列先进先出原则
BinaryTreeNode *pLeft = node.leftNode;
node.leftNode = node.rightNode;
node.rightNode = pLeft;if (node.leftNode) { [queueArray addObject:node.leftNode]; } if (node.rightNode) { [queueArray addObject:node.rightNode]; } } return rootNode; }
/**
- 翻转二叉树（又叫：二叉树的镜像）
- @param rootNode 根节点
- @return 翻转后的树根节点（其实就是原二叉树的根节点）
*/
+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode {
if (!rootNode) { return nil; }
if (!rootNode.leftNode && !rootNode.rightNode) { return rootNode; }
[self invertBinaryTree:rootNode.leftNode];
[self invertBinaryTree:rootNode.rightNode];
BinaryTreeNode *tempNode = rootNode.leftNode;
rootNode.leftNode = rootNode.rightNode;
rootNode.rightNode = tempNode;
return rootNode;
}
pragma mark - 遍历二叉树
/// 先序遍历
+ (void)treeFirstInformationWithNode:(BinaryTreeNode *)rootNode resultBlock:(void (^)(NSInteger value))block{
if (block) {
block(rootNode.value);
}
if (rootNode.leftNode) {
[self treeFirstInformationWithNode:rootNode.leftNode resultBlock:block];
}
if (rootNode.rightNode) {
[self treeFirstInformationWithNode:rootNode.rightNode resultBlock:block];
}
}
/// 中序遍历
+ (void)treeMiddleInformationWithNode:(BinaryTreeNode *)rootNode resultBlock:(void (^)(NSInteger value))block{
if (rootNode.leftNode) {
[self treeMiddleInformationWithNode:rootNode.leftNode resultBlock:block];
}
if (block) {
block(rootNode.value);
}
if (rootNode.rightNode) {
[self treeMiddleInformationWithNode:rootNode.rightNode resultBlock:block];
}
}
/// 后序遍历
+ (void)treeLastInformationWithNode:(BinaryTreeNode *)rootNode resultBlock:(void (^)(NSInteger value))block{
if (rootNode.leftNode) {
[self treeLastInformationWithNode:rootNode.leftNode resultBlock:block];
}
if (rootNode.rightNode) {
[self treeLastInformationWithNode:rootNode.rightNode resultBlock:block];
}
if (block) {
block(rootNode.value);
}
}
/// 二叉树深度
+ (NSInteger)depathOfTree:(BinaryTreeNode *)rootNode{
if (!rootNode) return 0;
if (!rootNode.leftNode && !rootNode.rightNode) return 1;
NSInteger leftDepth = [self depathOfTree:rootNode.leftNode];
NSInteger rightDepth = [self depathOfTree:rootNode.rightNode];
return MAX(leftDepth, rightDepth) + 1;
}
/// 二叉树所有节点数 节点数=左子树节点数+右子树节点数+1（根节点）
+ (NSInteger)numberOfNodesInTree:(BinaryTreeNode *)rootNode{
if (!rootNode) return 0;
return [self numberOfNodesInTree:rootNode.leftNode] + [self numberOfNodesInTree:rootNode.rightNode] + 1;
}
//二叉树中某个节点到根节点的路径
+ (NSArray *)pathOfTreeNode:(BinaryTreeNode *)treeNode inTree:(BinaryTreeNode *)rootNode {
NSMutableArray *pathArray = [NSMutableArray array];
[self isFoundTreeNode:treeNode inTree:rootNode routePath:pathArray];
return pathArray;
}
pragma mark - Private SEL
+ (BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value {
//根节点不存在，创建节点
if (!treeNode) {
treeNode = [BinaryTreeNode new];
treeNode.value = value;
NSLog(@"node:%@", @(value));
}
else if (value <= treeNode.value) {
NSLog(@"to left");
//值小于根节点，则插入到左子树
treeNode.leftNode = [[self class] addTreeNode:treeNode.leftNode value:value];
}
else {
NSLog(@"to right");
//值大于根节点，则插入到右子树
treeNode.rightNode = [[self class] addTreeNode:treeNode.rightNode value:value];
}
return treeNode;
}
+ (BOOL)isFoundTreeNode:(BinaryTreeNode *)treeNode inTree:(BinaryTreeNode *)rootNode routePath:(NSMutableArray *)path {
if (!rootNode || !treeNode) {
return NO;
}
//找到节点
if (rootNode == treeNode) {
[path addObject:rootNode];
return YES;
}
//压入根节点，进行递归
[path addObject:rootNode];
//先从左子树中查找
BOOL find = [self isFoundTreeNode:treeNode inTree:rootNode.leftNode routePath:path];
//未找到，再从右子树查找
if (!find) {
find = [self isFoundTreeNode:treeNode inTree:rootNode.rightNode routePath:path];
}
//如果2边都没查找到，则弹出此根节点
if (!find) {
[path removeLastObject];
}
return find;
}
7.二分查找
+ (NSInteger)binarySearchNoRecursion:(NSArray *)srcArray withDes:(NSNumber *)des{
NSInteger low = 0;
NSInteger high = [srcArray count] - 1;
while (low <= high) {
NSInteger middle = low + ((high + low)>>1);//中间位置计算,low+ 最高位置减去最低位置,右移一位,相当于除2.也可以用(high+low)/2
if ([des integerValue] == [srcArray[middle] integerValue]) return middle;
else if([des integerValue] < [srcArray[middle] integerValue]) high = middle - 1;
else low = middle + 1;
}
return -1;
}
+ (NSInteger)binarySearchWithRecursion:(NSArray *)srcArray withDes:(NSNumber *)des{
NSInteger low = 0;
NSInteger high = [srcArray count] - 1;
return [self binSearch:srcArray withLow:low withHigh:high withKey:des];
}
+ (NSInteger)binSearch:(NSArray *)srcArray withLow:(NSInteger)low withHigh:(NSInteger)high withKey:(NSNumber *)key{
if (low <= high) {
NSInteger mid = (low + high)/2;
if ([key integerValue] == [srcArray[mid] integerValue]) return mid;
else if([key integerValue] < [srcArray[mid] integerValue]) return [self binSearch:srcArray withLow:low withHigh:(mid - 1) withKey:key];
else return [self binSearch:srcArray withLow:mid+1 withHigh:high withKey:key];
}else{
return -1;
}
}
8.归并排序
+ (void)mergearray:(NSMutableArray *)ary withFirst:(NSInteger)first withMid:(NSInteger)mid withLast:(NSInteger)last ResultAry:(NSMutableArray *)temp{
NSInteger i = first, j = mid + 1;
NSInteger m = mid ,n = last;
NSInteger k = 0;
while (i <= m && j <= n) {
if (ary[i] <= ary[j]) temp[k++] = ary[i++];
else temp[k++] = ary[j++];
}
while (i <= m) temp[k++] = ary[i++];
while (j <= n) temp[k++] = ary[j++];
for (i = 0; i < k; i++) ary[first + i] = temp[i];
}
+ (void)mergeSort:(NSMutableArray *)ary withFirst:(NSInteger)first withLast:(NSInteger)last ResultAry:(NSMutableArray *)temp{
if (first < last) {
NSInteger mid = (first + last) / 2;
[self mergeSort:ary withFirst:first withLast:mid ResultAry:temp]; // 左边有序
[self mergeSort:ary withFirst:mid + 1 withLast:last ResultAry:temp]; // 右边有序
[self mergearray:ary withFirst:first withMid:mid withLast:last ResultAry:temp];// 将二个有序数列合并
}
}
+ (NSMutableArray *)mergeSort:(NSMutableArray *)ary withCapacity:(NSInteger)n{
NSMutableArray *p = [NSMutableArray arrayWithCapacity:n];
[self mergeSort:ary withFirst:0 withLast:n-1 ResultAry:p];
return p;
}
9. 汉诺塔
+ (void)move:(NSInteger)N withA:(NSString *)A withB:(NSString *)B withC:(NSString *)C{
if ( N == 1 ) {
NSLog(@"Move disk %ld from %@ to %@\n",N,A,C);
}else{
[self move:(N - 1) withA:A withB:C withC:B];
NSLog(@"Move disk %ld from %@ to %@\n",N,A,C);
[self move:(N - 1) withA:B withB:A withC:C];
}
}
10. 快速排序
+ (void)quickSortWithArray:(NSMutableArray *)array withLeft:(NSInteger)left andRight:(NSInteger)right{
if (left >= right) return;
NSInteger i = left;
NSInteger j = right;
NSInteger key = [array[left] integerValue];
while (i < j) {
while (i < j && key <= [array[j] integerValue]) {
j--;
}
array[i] = array[j];
while (i < j && key >= [array[i] integerValue]) {
i++;
}
array[j] = array[i];
}
array[i] = [NSNumber numberWithInteger:key];
[[self class] quickSortWithArray:array withLeft:left andRight:i - 1];
[[self class] quickSortWithArray:array withLeft:i + 1 andRight:right];
}
11. 冒泡排序
+ (void)bubbleSortWithArray:(NSMutableArray *)array{
for (int i = 0; i < array.count; i++) {
for (int j = 0; j < array.count - i - 1; j++) {
if (array[j] < array[j+1]) {
int temp = [array[j] intValue];
array[j] = array[j + 1];
array[j + 1] = [NSNumber numberWithInt:temp];
}
}
}
}
12. 希尔排序
+ (void)shellSort:(NSMutableArray *)list{
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]];
j-=gap;
}
[list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
}
gap = gap/2;
}
}
