之前参加了一场海归博士主持的面试,问了很多关于数组,字典,基础算法的知识,上学那会忽视了,经历那次之后想了很多,加上最近工作遇到了很多这方面的逻辑问题,所以在这里总结一下基础排序算法的OC实现.
常用基础排序算法
- 冒泡排序
- 快速排序
冒泡排序
NSMutableArray *ary = [NSMutableArray arrayWithObjects:@34,@12,@24,@3,@51,nil];
//遍历`数组的个数`次 /*
i = 0 的时候，j的相邻两个位置都要比较排一下位置：
j = 0 的时候：ary = 34,12,24,3,51
j = 1 的时候：ary = 34,24,12,3,51
j = 2 的时候：ary = 34,24,12,3,51
j = 3 的时候：ary = 34,24,12,51,3
i = 1; ............后面依次类推就可以了
*/
for (int i = 0; i < ary.count; ++i)
{
//遍历数组的每一个`索引`（不包括最后一个,因为比较的是j+1）
for (int j = 0; j < ary.count-1; ++j)
{
//根据索引的`相邻两位`进行`比较`
if (ary[j] < ary[j+1]) //从大到小,从小到大改一下此处的符号就好了
{
[ary exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"最终结果：%@",ary);
快速排序
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *arr = [[NSMutableArray alloc]initWithObjects:@(16), @(11),@(12),@(5),@(19),@(14),@(31),@(17),nil];
[self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count - 1];
NSLog(@"%@",arr); }
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex)
{
//如果数组长度为0或1时返回 return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//记录比较基准数
NSInteger key = [array[i] integerValue];
while (i < j)
{
/****
首先从右边j开始查找比基准数小的值
***/
while (i < j && [array[j] integerValue] >= key)
{
//如果比基准数大，继续查找 j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置 array[i] = array[j];
/****
当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值
***/
while (i < j && [array[i] integerValue] <= key)
{
//如果比基准数小，继续查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
array[j] = array[i];
}
//将基准数放到正确位置
array[i] = @(key);
/**** 递归排序 ***/
//排序基准数左边的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex]; }
