目录
常见算法
不用中间变量,用两种方法交换A和B的值
求最大公约数
判断质数
字符串逆序输出
排序相关算法
选择排序
冒泡排序
折半查找（二分查找）
快速排序
模拟栈的操作
序言
虽然我们在平时工作中，算法用的比较少，但是面试的时候，算法考核算是一个必修课。所以熟悉算法，深刻理解本质，对于面试就成竹在胸了。
一 常用算法
1.1 不用中间变量,用两种方法交换A和B的值
// 1.中间变量voidswap(inta,intb){inttemp=a;a=b;b=temp;}// 2.加法voidswap(inta,intb){a=a+b;b=a-b;a=a-b;}// 3.异或（相同为0，不同为1. 可以理解为不进位加法）voidswap(inta,intb){a=a^b;b=a^b;a=a^b;}
1.2 求最大公约数
比如20和4的最大公约数为4。18和27的最大公约数为9。
/** 1.直接遍历法 */intmaxCommonDivisor(inta,intb){intmax=0;for(inti=1;i<=b;i++){if(a%i==0&&b%i==0){max=i;}}returnmax;}/** 2.辗转相除法 其中a为大数，b为小数 */intmaxCommonDivisor(inta,intb){intr;while(a%b>0){r=a%b;a=b;b=r;}returnb;}
1.3 判断质数
比如2,3,5,7,11,13,19等只能被1和自身整除的叫质数
这里只用最简单直接打判断，一个个除，看余数是否为零，如果不为零，则非质数。
intisPrime(intn){for(inti=2;i<=sqrt(n);i++){if(n%i==0){return0;}}return1;}
1.4 字符串逆序输出
直接用指针进行操作
voidreverse(chars[]){// p指向字符串头部char*p=s;// q指向字符串尾部char*q=s;while('\0'!=*q){q++;}q--;// 交换并移动指针，直到p和q交叉while(q>p){chart=*p;charm=*q;*p=m;*q=t;p++;q--;}}
二 排序相关算法
2.1 选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
最值出现在起始端
第1趟：在n个数中找到最小(大)数与第一个数交换位置
第2趟：在剩下n-1个数中找到最小(大)数与第二个数交换位置
重复这样的操作...依次与第三个、第四个...数交换位置
第n-1趟，最终可实现数据的升序（降序）排列。
voidselectSort(int*arr,intlength){for(inti=0;i<length-1;i++){//趟数for(intj=i+1;j<length;j++){//比较次数if(arr[i]>arr[j]){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}}}
2.2 冒泡排序
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
相邻元素两两比较，比较完一趟，最值出现在末尾
第1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n个元素位置
第2趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n-1个元素位置
…… ……
第n-1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第2个元素位置
voidbublleSort(int*arr,intlength){for(inti=0;i<length-1;i++){//趟数for(intj=0;j<length-i-1;j++){//比较次数if(arr[j]>arr[j+1]){inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}}
2.3 折半查找（二分查找）
在计算机科学中，折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半 [1]。
优化查找时间（不用遍历全部数据）
1 数组必须是有序的
2 必须已知min和max（知道范围）
3 动态计算mid的值，取出mid对应的值进行比较
4 如果mid对应的值大于要查找的值，那么max要变小为mid-1
5 如果mid对应的值小于要查找的值，那么min要变大为mid+1
已知一个有序数组, 和一个key, 要求从数组中找到key对应的索引位置
intfindKey(int*arr,int length,int key){intmin=0,max=length-1,mid;while(min<=max){mid=(min+max)/2;//计算中间值if(key>arr[mid]){min=mid+1;}elseif(key<arr[mid]){max=mid-1;}else{returnmid;}}return-1;}
2.4 快速排序
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
该方法的基本思想是：
1 先从数列中取出一个数作为基准数。
2 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3 再对左右区间重复第二步，直到各区间只有一个数。
** 一趟快速排序的算法是：**
1 设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2 以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3 从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]的值赋给A[i]；
4 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]的值赋给A[j]；
5 重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
或许很多人看了后还是很懵逼，有个哥们总结的很好
下面详细描述
虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法
以一个数组作为示例，取区间第一个数为基准数。
image.png
初始时，i = 0; j = 9; X = a[i] = 72
由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;
数组变为：
image.png
i = 3; j = 7; X=72
再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。
数组变为：
image.png
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
照着这个总结很容易实现挖坑填数的代码：
//快速排序voidquick_sort(ints[],intl,intr){if(l<r){//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1inti=l,j=r,x=s[l];while(i<j){while(i<j&&s[j]>=x)// 从右向左找第一个小于x的数j--;if(i<j)s[i++]=s[j];while(i<j&&s[i]<x)// 从左向右找第一个大于等于x的数i++;if(i<j)s[j--]=s[i];}s[i]=x;quick_sort(s,l,i-1);// 递归调用 quick_sort(s,i+1,r);}}
三 模拟栈的操作
栈是一种数据结构，特点：先进后出
代码实现
Stack.h
/**
定义block
@param obj 回调值
*/typedefvoid(^StackBlock)(id obj);/**
模拟栈实现 - 简单实现
*/@interfaceStack:NSObject// 初始化操作-(instancetype)initWithNumbers:(NSArray*)numbers;/** 入栈 @param obj 指定入栈对象 */-(void)push:(id)obj;/** 出栈 */-(id)popObj;/** 是否为空 */-(BOOL)isEmpty;/** 栈的长度 */-(NSInteger)stackLength;/** 从栈底开始遍历 @param block 回调遍历的结果 */-(void)enumerateObjectsFromBottom:(StackBlock)block;/** 从顶部开始遍历 */-(void)enumerateObjectsFromtop:(StackBlock)block;/** 所有元素出栈，一边出栈一边返回元素 */-(void)enumerateObjectsPopStack:(StackBlock)block;/** 清空 */-(void)removeAllObjects;/** 返回栈顶元素 */-(id)topObj;@end
Stack.m
@interfaceStack()// 存储栈数据@property(nonatomic,strong)NSMutableArray*stackArray;@end@implementationStack// 初始化操作-(instancetype)initWithNumbers:(NSArray*)numbers{self=[superinit];if(self){for(NSNumber*numberinnumbers){[self.stackArray addObject:number];}}returnself;}#pragmamark - push-(void)push:(id)obj{[self.stackArray addObject:obj];}#pragmamark - get-(id)popObj{if([selfisEmpty]){returnnil;}else{id lastObject=self.stackArray.lastObject;[self.stackArray removeLastObject];returnlastObject;}}-(id)topObj{if([selfisEmpty]){returnnil;}else{returnself.stackArray.lastObject;}}-(BOOL)isEmpty{return!self.stackArray.count;}-(NSInteger)stackLength{returnself.stackArray.count;}#pragmamark - 遍历// 从栈底开始遍历-(void)enumerateObjectsFromBottom:(StackBlock)block{[self.stackArray enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(id _Nonnull obj,NSUInteger idx,BOOL*_Nonnull stop){block?block(obj):nil;}];}// 从顶部开始遍历-(void)enumerateObjectsFromtop:(StackBlock)block{[self.stackArray enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id _Nonnull obj,NSUInteger idx,BOOL*_Nonnull stop){block?block(obj):nil;}];}// 所有元素出栈，一边出栈一边返回元素-(void)enumerateObjectsPopStack:(StackBlock)block{__weaktypeof(self)weakSelf=self;NSUInteger count=self.stackArray.count;for(NSUInteger i=count;i>0;i--){if(block){block(weakSelf.stackArray.lastObject);[self.stackArray removeLastObject];}}}#pragmamark - remove-(void)removeAllObjects{[self.stackArray removeAllObjects];}#pragmamark - lazy-(NSMutableArray*)stackArray{if(!_stackArray){_stackArray=[NSMutableArray array];}return_stackArray;}@end
本文参考
原文链接：https://www.jianshu.com/p/5423ac01475f
网友评论