每次面试，想必大家都会多多少少的遇到些算法题。忙里偷闲整理了几个基本的算法，就当是复习了，希望给需要的人作为参考！
以下这几道算法，都是用oc语言写的，大学那会学算法，是c++语言写的，后来查资料也都是类似的C语言写的，如今把她翻译成了OC语言。
1.桶排序（原理自己查资料）
[self algorithms];//桶排序 o(m+n)
- (void)algorithms{
NSArray *arr = @[@"5",@"3",@"5",@"2",@"8"];
for(NSString*a in arr) {
intb = [aintValue];
intc = [self.array[b]intValue];
self.array[b] = [NSStringstringWithFormat:@"%d",c+1];
}
// for (int j=0;j<self.array.count; j++){//从小到大
for(intj=10;j>0; j--){//从大到小
int c = [self.array[j] intValue];
if(c!=0){
for(intk =0; k<c; k++){
NSLog(@"%@%d",@"桶排序",j);
}
}
}
}
- (NSMutableArray *)array{
if(!_array){
_array= [[NSMutableArrayalloc]init];
for(inti=0; i<11; i++) {
_array[i]=@"0";
}
}
return _array;
}
2.冒泡排序
[self bubble];//冒泡排序 o(n*n)
- (void)bubble{//最后我们总结一下:如果有 n 个数进行排序，只需将 n-1 个数归位，也就是说要进行 n-1 趟操作
NSArray *arr = @[@{@"q":@"5"},@{@"w":@"3"},@{@"e":@"5"},@{@"r":@"2"},@{@"t":@"8"}];
NSMutableArray *mulArr= [[NSMutableArray alloc] initWithArray:arr];
for(int k=0; k<arr.count-1; k++){
for(inti=0; i<mulArr.count-k-1; i++){
NSArray*arr = [mulArr[i]allKeys];
NSString*value = [mulArr[i]valueForKey:arr[0]];
int a = [value intValue];
NSArray*arr1 = [mulArr[i+1]allKeys];
NSString*value1 = [mulArr[i+1]valueForKey:arr1[0]];
int b = [value1 intValue];
if(a<b){
NSDictionary*dic = mulArr[i] ;
mulArr[i] = mulArr[i+1];
mulArr[i+1] = dic;
}
}
}
NSLog(@"%@%@",@"冒泡排序",mulArr);
}
3.快排
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(7),@(9),@(3),@(4),@(5),@(10),@(8),nil];
[self quicksortWithleft:0 WithRight:9 WithArr:arr];
NSLog(@"%@",arr);
- (void)quicksortWithleft:(int)left WithRight:(int)right WithArr:(NSMutableArray*)a{
if(left>=right){
return;
}
int temp=[a[left]intValue];//temp中存的就是基准数
inti=left;
intj=right;
while(i!=j)
{
//顺序很重要，要先从右往左找
while([a[j]intValue]>=temp && i<j){
j--;
}
//再从左往右找
while([a[i]intValue]<=temp && I<j){
i++;
}
//交换两个数在数组中的位置 ,当哨兵i和哨兵j没有相遇时
if(I<j){
NSNumber*t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最终将基准数归位
a[left]=a[i];
a[i]=[NSNumber numberWithInt:temp];
[self quicksortWithleft:left WithRight:i-1 WithArr:a];//继续处理左边的，这里是一个递归的过程
[self quicksortWithleft:i+1 WithRight:right WithArr:a];//继续处理右边的，这里是一个递归的过程
}
4.直接插入排序
//直接插入排序 o(n*n)
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(7),@(9),@(3),@(4),@(5),@(10),@(8),nil];
[self insertSortWithArr:arr];
//当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N);当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N2)。所以，数据越接近正序，直接插入排序的算法性能越好。
- (void)insertSortWithArr:(NSMutableArray*)arr{
for(inti=1; i<arr.count; i++){
int temp = [arr[i] intValue];
int j;
for(j=i-1; j>=0&&[arr[j] intValue]>temp ;j--) {
arr[j+1] = arr[j];
}
arr[j+1] = [NSNumber numberWithInt:temp];
}
NSLog(@"%@",arr);
}
5.选择排序
//选择排序 o(n*n)
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(7),@(9),@(3),@(4),@(5),@(10),@(8),nil];
[self selectionWithArr:arr];
//选择排序的思想：选择排序算法的基本思想是对a[1]...a[r]进行r-1遍处理，第i遍处理 是将a[i]，⋯，a[r]中最小者d的位置找到，然后与a[i]交换位置。这样，经过r-1遍处理之后，较小的r-1个元素的位置已经是正确的了
- (void)selectionWithArr:(NSMutableArray*)arr{
for(inti =0;i<arr.count-1; i++){
//找出最小数的下标
intmin = i;
for(intj=i+1; j<arr.count; j++){
if([arr[j] intValue]<[arr[min] intValue]) {
min = j;
}
}
//交换位置
NSNumber*t=arr[min];
arr[min]=arr[i];
arr[i]=t;
}
NSLog(@"%@",arr);
}
以上有些算法没有表明原理，请自己查询。建议在对这些算法原理基本弄明白以后再去参考此代码，可以更加容易看懂！（上面的代码都是可以运行的，并且运行结果正确，如果你们有更简洁的写法可以提出来，如果有其他语言的版本，欢迎贴出来大家共享）
