总结了下在iOS开发常用到的算法，不管是在面试中还是日常开发中，都会用到
1、冒泡排序
冒泡算法是重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
对以下一组数据进行降序排序（冒泡排序）“55, 23, 93, 23, 4, 56, 1, 34, 11, 69”
int array[10] = {55, 23, 93, 23, 4, 56, 1, 34, 11, 69};
int num = sizeof(array)/sizeof(int);
for (int i = 0 ; i < num - 1; i++) {
for (int j = 0 ; j < num - 1 - i; j++) {
if (array[j] < array[j +1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
for (int i = 0; i < num; i++) {
printf("%d", array[i]);
if (i == num - 1) {
printf("\n");
} else {
printf(" ");
}
}
2、选择排序
选择排序的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
对以下一组数据进行升序排序（选择排序）。“55, 23, 93, 23, 4, 56, 1, 34, 11, 69”
int array[10] = {55, 23, 93, 23, 4, 56, 1, 34, 11, 69};
int num = sizeof(array)/sizeof(int);
for (int i = 0; i < num - 1; i++) {
for (int j = i + 1; j < num ; j++) {
if (array[i] > array [j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
for (int i = 0; i < num; i++) {
printf("%d", array[i]);
if (i == num - 1) {
printf("\n");
} else {
printf(" ");
}
}
3、快速排序算法
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(55), @(23),@(93),@(23),@(4),@(56),@(1),@(34),@(69),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];
}
4、 归并排序
该方法的基本思想是：
1.分解：将待排序的问题分解成大小大致相等的两部分。
2.求解子问题：用归并排序的方法对两个子问题进行递归排序。
3.合并(merge)：将排好序的有序子序列进行合并，得到符合要求的子序列。
@interface ViewController ()
@property (nonatomic, strong) NSMutableArray *tempArr;
@end
@implementation ViewController
-(NSMutableArray *)tempArr
{
if (_tempArr == nil) {
_tempArr = [NSMutableArray array];
}
return _tempArr;
}
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(55), @(29),@(93),@(23),@(4),@(56),@(1),@(34),@(69),nil];
[self mergeSortArray:arr lowIndex:0 highIndex:arr.count - 1];
NSLog(@"%@",arr);
}
- (void)mergeSortArray:(NSMutableArray *)array lowIndex:(NSInteger)lowIndex highIndex:(NSInteger)highIndex
{
if (lowIndex >= highIndex) {
return;
}
NSInteger midIndex = lowIndex + (highIndex - lowIndex) / 2;
[self mergeSortArray:array lowIndex:lowIndex highIndex:midIndex];
[self mergeSortArray:array lowIndex:midIndex + 1 highIndex:highIndex];
[self mergeArray:array lowIndex:lowIndex midIndex:midIndex highIndex:highIndex];
}
- (void)mergeArray:(NSMutableArray *)array lowIndex:(NSInteger)lowIndex midIndex:(NSInteger)midIndex highIndex:(NSInteger)highIndex
{
for (NSInteger i = lowIndex; i <= highIndex; i ++) {
self.tempArr[i] = array[i];
}
NSInteger k = lowIndex;
NSInteger l = midIndex + 1;
for (NSInteger j = lowIndex; j <= highIndex; j ++) {
if (l > highIndex) {
array[j] = self.tempArr[k];
k++;
}else if (k > midIndex)
{
array[j] = self.tempArr[l];
l++;
}else if ([self.tempArr[k] integerValue] > [self.tempArr[l] integerValue])
{
array[j] = self.tempArr[l];
l++;
}else
{
array[j] = self.tempArr[k];
k++;
}
}
}
网友评论