OC整理递归和排序算法
2018-06-26 本文已影响146人
wuyukobe
一、递归算法
递归算法:（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。好处就是它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
代码实现：
#pragma mark - 1.数组递归
- (NSMutableArray *)getResultArrayWithArray:(NSArray *)array {
for (int i = 0;i < array.count ; i++) {
if ([array[i] isKindOfClass:[NSArray class]]) {
[self getResultArrayWithArray:array[i]];
}else{
[_resultArray addObject:array[i]];
}
}
return _resultArray;
}
数据传入：
NSArray * dataArray = @[@"c",@[@"aa",@"ee"],@5,@[@"ko",@"ppp",@"ms",@[@[@8,@"yy"],@"zz"]]];
数据接收：
_resultArray = [NSMutableArray array];
获取结果：
2018-06-26 11:12:27.001176+0800 算法[1048:25334]递归结果为(
c,
aa,
ee,
5,
ko,
ppp,
ms,
8,
yy,
zz
)
二、排序算法
1、冒泡排序法
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。
代码实现：
- (NSMutableArray *)sortBubbleNumArray:(NSArray *)array {
NSInteger count = array.count;
NSMutableArray * dataArray = [NSMutableArray arrayWithArray:array];
for (NSInteger i=0; i<count-1; i++) {
for (NSInteger j=0; j<count-1-i; j++) {
if ([dataArray[j] intValue] < [dataArray[j+1] intValue]) {
//交换位置
[dataArray exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
return dataArray;
}
数据传入：
- (NSArray *)numArray {
if (!_numArray) {
_numArray = [NSArray arrayWithObjects:@"3",@"49",@"20",@"88",@"93",@"52",@"9",@"35",@"66",@"29", nil];
}
return _numArray;
}
获取结果：
2018-06-26 11:17:15.629232+0800 算法[1048:25334] 冒泡排序为(
93,
88,
66,
52,
49,
35,
29,
20,
9,
3
)
2、选择排序法
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
代码实现：
- (NSMutableArray *)sortSelectNumArray:(NSArray *)array {
NSInteger count = array.count;
NSMutableArray * dataArray = [NSMutableArray arrayWithArray:array];
for (NSInteger i=0; i<count; i++) {
for (NSInteger j=i+1; j<count; j++) {
if ([dataArray[i] intValue] < [dataArray[j] intValue]) {
//交换位置
[dataArray exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
return dataArray;
}
数据传入：
- (NSArray *)numArray {
if (!_numArray) {
_numArray = [NSArray arrayWithObjects:@"3",@"49",@"20",@"88",@"93",@"52",@"9",@"35",@"66",@"29", nil];
}
return _numArray;
}
获取结果：
2018-06-26 11:23:02.831709+0800 算法[1048:25334] 选择排序为(
93,
88,
66,
52,
49,
35,
29,
20,
9,
3
)
3、快速排序法
快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码实现：
/**
* 快速排序法
* @param array 排序数组
* @param leftIndex 数组首位
* @param rightIndex 数组末位
*/
- (void)quickSortArray:(NSMutableArray *)array leftIndex:(NSInteger)leftIndex rightIndex:(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--;
}
array[i] = array[j];//如果比基准数小，则将查找到的小值调换到i的位置
//当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值
while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
i++;
}
array[j] = array[i];//如果比基准数大，则将查找到的大值调换到j的位置
}
//将基准数放到正确位置
array[i] = @(key);
/**递归排序*/
//排序基准数左边的
[self quickSortArray:array leftIndex:leftIndex rightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array leftIndex:i + 1 rightIndex:rightIndex];
}
数据传入：
- (NSArray *)numArray {
if (!_numArray) {
_numArray = [NSArray arrayWithObjects:@"6",@"9",@"3",@"8",@"2",@"0",@"7",@"5",@"1",@"4", nil];
}
return _numArray;
}
获取结果：
2018-06-26 11:31:40.854133+0800 算法[1048:25334] 快速排序法(
0,
1,
2,
3,
4,
5,
6,
7,
8,
9
)
4、归并排序法
归并排序：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
代码实现：
- (NSArray *)mergeSortArray:(NSMutableArray *)array {
//归并排序需要两大步:首先将序列每次折半划分，然后将划分后的序列段两两合并后排序
NSMutableArray * tempArray = [NSMutableArray arrayWithCapacity:1];
for (NSNumber * num in array) {
NSMutableArray * subArray = [NSMutableArray array];
[subArray addObject:num];
[tempArray addObject:subArray];
}
//分解操作 每一次归并操作 tempArray的个数为（当数组个数为偶数时tempArray.count/2;当数组个数为奇数时tempArray.count/2+1）;当tempArray.count == 1时，归并排序完成
while (tempArray.count != 1) {
NSInteger i = 0;
//当数组个数为偶数时，进行合并操作，当数组个数为奇数时，最后一位轮空
while (i < tempArray.count - 1) {
//将i与i+1进行合并操作，将合并结果放入i位置上，将i+1位置上的元素删除
tempArray[i] = [self mergeFirstArray:tempArray[i] secondArray:tempArray[i + 1]];
[tempArray removeObjectAtIndex:i + 1];
i++;
}
}
return [tempArray firstObject];
}
//合并
- (NSArray *)mergeFirstArray:(NSArray *)firArray secondArray:(NSArray *)secArray {
NSMutableArray * resultArray = [NSMutableArray array];
//firstIndex是第一段序列的下标 secondIndex是第二段序列的下标
NSInteger firstIndex = 0, secondIndex = 0;
//循环第一段和第二段序列，直到任一段序列循环结束
while (firstIndex < firArray.count && secondIndex < secArray.count) {
//比较两段序列取出的数值大小，将其存入合并序列，并继续向下循环
if ([firArray[firstIndex] integerValue] < [secArray[secondIndex] integerValue]) {
[resultArray addObject:firArray[firstIndex]];
firstIndex++;
} else {
[resultArray addObject:secArray[secondIndex]];
secondIndex++;
}
}
//将第一段未循环剩余参数全部添加到合并序列
while (firstIndex < firArray.count) {
[resultArray addObject:firArray[firstIndex]];
firstIndex++;
}
//将第二段未循环剩余参数全部添加到合并序列
while (secondIndex < secArray.count) {
[resultArray addObject:secArray[secondIndex]];
secondIndex++;
}
return resultArray.copy;
}
数据传入：
- (NSArray *)numArray {
if (!_numArray) {
_numArray = [NSArray arrayWithObjects:@"3",@"49",@"20",@"88",@"93",@"52",@"9",@"35",@"66",@"29", nil];
}
return _numArray;
}
获取结果：
2018-06-26 11:34:50.403620+0800 算法[1048:25334] 归并排序结果：(
3,
9,
20,
29,
35,
49,
52,
66,
88,
93
)
5、插入排序法
插入排序基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
代码实现：
//插入排序法（默认从小到大）
- (NSArray *)insertSportArray:(NSArray *)array {
NSMutableArray * resultArray = [NSMutableArray array];
for (NSInteger i=0; i<array.count; i++) {
if (i==0) {//默认第一位不参与排位，直接添加到排序数组中
[resultArray addObject:array[i]];
} else {
if ([array[i] integerValue] >= [[resultArray lastObject] integerValue]) {
//如果待排位数据大于已排位数组最后一位，则待排位数据直接插入到已排位数组最后一位
[resultArray addObject:array[i]];
} else {
//遍历已排位数组，如果待排位数据小于某个已排位数据，则带排位数据直接插入到该已排位数据的位置
for (NSInteger j=0; j<resultArray.count; j++) {
if ([array[i] integerValue] <= [resultArray[j] integerValue]) {
[resultArray insertObject:array[i] atIndex:j];
break;
}
}
}
}
}
return resultArray;
}
数据传入：
- (NSArray *)numArray {
if (!_numArray) {
_numArray = [NSArray arrayWithObjects:@"3",@"49",@"20",@"88",@"93",@"52",@"9",@"35",@"66",@"29", nil];
}
return _numArray;
}
获取结果：
2018-06-26 11:37:06.773457+0800 算法[1048:25334] 插入排序法:(
3,
9,
20,
29,
35,
49,
52,
66,
88,
93
)
6、希尔排序法
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
代码实现：
- (NSArray *)shellSportArray:(NSMutableArray *)array {
//起始间隔值gap设置为总数的一半
NSInteger gap = array.count/2;
//当gap==1时结束循环
while (gap >= 1) {
//把距离为gap的元素编为一个组，循环所有组
for(NSInteger i=gap; i<array.count; i++){
//取出第gap的数据
NSInteger j = i;
NSNumber * temp = array[i];
//对距离为gap的元素组进行排序
while (j >= gap && [temp integerValue] < [array[(j-gap)] integerValue]) {
[array exchangeObjectAtIndex:j withObjectAtIndex:(j-gap)];
j = j - gap;
}
}
gap = gap/2;
}
return array;
}
数据传入：
- (NSArray *)numArray {
if (!_numArray) {
_numArray = [NSArray arrayWithObjects:@"3",@"49",@"20",@"88",@"93",@"52",@"9",@"35",@"66",@"29", nil];
}
return _numArray;
}
获取结果：
2018-06-26 11:39:58.895501+0800 算法[1048:25334] 希尔排序法:(
3,
9,
20,
29,
35,
49,
52,
66,
88,
93
)
以上是我自己最近整理总结的递归算法和排序算法， Demo地址：递归算法和排序算法
参考推荐：在线动画演示各种排序算法
