iOS 中的算法—1.排序
2016-06-15 本文已影响275人
LeeDev
首先我们考虑的排序算法有，选择、冒泡、Shell、合并、快速排序
我是自定义了一个Sort 类，然后其他的排序都继承这个Sort 类，有点像简单的工厂的设计模式。以后可以再写写查找的算法。
0.首先看 下整体的代码逻辑 相对来说比较清爽
//
// ViewController.m
// 排序算法
//
// Created by lichory on 16/6/14.
// Copyright © 2016年 lichory. All rights reserved.
//
#import "ViewController.h"
#import "SelectedSort.h"
#import "BubbleSort.h"
#import "ShellSort.h"
#import "MergeSort.h"
#import "QuickSort.h"
@interface ViewController ()
@end
@implementation ViewController
- (void)viewDidLoad {
[super viewDidLoad];
// Do any additional setup after loading the view, typically from a nib.
NSArray * sortArr = @[@(1),@(4),@(3),@(8),@(2),@(10),@(23),@(15),@(16),@(0),@(14)];
/* 快速排序 通过递归的**/
[self selectedSortWithArr:sortArr];
/* 冒泡排序 **/
[self bubbleSortWithArr:sortArr];
/*shell 排序**/
[self ShellSortWithArr:sortArr];
/* 归并排序**/
[self MergeSortWithArr:sortArr];
/* 快速排序**/
[self QuickSortWithArr:sortArr];
}
- (void)selectedSortWithArr:(NSArray<NSNumber*> *)sortArr {
SelectedSort * sort = [[SelectedSort alloc]init];
sort.sortArr = sortArr.mutableCopy;
[sort startSort];
[sort printSort];
}
- (void)bubbleSortWithArr:(NSArray<NSNumber*> *)sortArr {
BubbleSort * sort = [[BubbleSort alloc]init];
sort.sortArr = sortArr.mutableCopy;
[sort startSort];
[sort printSort];
}
- (void)ShellSortWithArr:(NSArray<NSNumber*> *)sortArr {
ShellSort * sort = [[ShellSort alloc]init];
sort.sortArr = sortArr.mutableCopy;
[sort startSort];
[sort printSort];
}
- (void)MergeSortWithArr:(NSArray<NSNumber*> *)sortArr {
MergeSort * sort = [[MergeSort alloc]init];
sort.sortArr = sortArr.mutableCopy;
[sort startSort];
[sort printSort];
}
- (void)QuickSortWithArr:(NSArray<NSNumber*> *)sortArr {
QuickSort * sort = [[QuickSort alloc]init];
sort.sortArr = sortArr.mutableCopy;
[sort startSort];
[sort printSort];
}
@end
1.我先讲讲选择排序 （用递归）
其实选择排序相当于 先从1~n 中选择一个最小值，然后放到 第一个位置中，然后从 2~n 中选择一个最小的放到 2~n 中的第一个位置，如此往下进行就能整个数组有序的
//
// SelectedSort.m
// 排序算法
//
// Created by lichory on 16/6/14.
// Copyright © 2016年 lichory. All rights reserved.
//
#import "SelectedSort.h"
@implementation SelectedSort
- (void)startSort {
[self selectedSortWithStartIndex:0 endIndex:(int)self.sortArr.count-1];
}
- (void)selectedSortWithStartIndex:(int)startIndex endIndex:(int)endIndex {
/* 递归出口 **/
if (startIndex >= endIndex) {
return;
}
/* 下面就是 找到 最小值的下标 **/
int minIndex = startIndex;
for (int i = startIndex +1; i <= endIndex; i++) {
if ([self.sortArr[i] floatValue] < [self.sortArr[minIndex] floatValue]) {
minIndex = i;
}
}
/*如果找到了 就交互数据 **/
if (minIndex != startIndex) {
[self exchargeIndex:startIndex otherIndex:minIndex];
}
/* 接下来 就是 递归 从startIndex+1 开始的下标 然后找最小值**/
[self selectedSortWithStartIndex:startIndex+1 endIndex:endIndex];
}
@end
2.冒泡 （用递归）
其实冒泡 相当于 先从1~n 中 ，一直交换，最大的数就能放到最后了，然后从 1~n-1 ，如此往下进行就能整个数组有序
//
// BubbleSort.m
// 排序算法
//
// Created by apple on 16/6/15.
// Copyright © 2016年 lichory. All rights reserved.
//
#import "BubbleSort.h"
@implementation BubbleSort
- (void)startSort {
[self bubbleSortWithStartIndex:0 endIndex:(int)self.sortArr.count-1];
}
- (void)bubbleSortWithStartIndex:(int)startIndex endIndex:(int)endIndex {
if (startIndex >= endIndex) {
return;
}
for (int i = startIndex; i < endIndex; i++) {
/* 把大的数往后 冒泡**/
if ([self.sortArr[i] floatValue] > [self.sortArr[i+1] floatValue] ) {
[self exchargeIndex:i otherIndex:i+1];
}
}
[self bubbleSortWithStartIndex:startIndex endIndex:endIndex -1];
}
@end
3.Shell排序 (主要是减少冒泡交换的次数)
开始排序
- shell 排序的思想是
- 就是 以h间隔 有序 =》 相当于 一列数组中 从 a ——》a+h - 》 a+2h -> a+3h ....有序的
- 就是为当 h = 1 时候，交换的次数相对来说要减少
//
// ShellSort.m
// 排序算法
//
// Created by apple on 16/6/15.
// Copyright © 2016年 lichory. All rights reserved.
//
#import "ShellSort.h"
#import "BubbleSort.h"
@implementation ShellSort
- (void)startSort {
int h = 1;
//分成3段
while (h < self.sortArr.count/3) {
h = 3*h +1;
}
while (h >= 1) {
/*
* 让 从 i ->i+h ->i+2h ->i+3h 是有顺序的
**/
for (int i = 0; i < self.sortArr.count; i+=h) {
for (int j = 0 ; j + h < self.sortArr.count ; j+=h) {
if ( ([self.sortArr[j] floatValue] > [self.sortArr[j+h] floatValue])) {
[self exchargeIndex:j+h otherIndex:j];
}
}
}
h = h/3;
}
}
@end
4.合并算法
/*
- 合并算法的思想就是 自顶向下的思想
- 也是一个分治的思想，只要 最底层有解 那么它的最上层也是有解的
- 它其实就是 只要子问题中的 肯定存在 两个有序的：比如两个值 a 和b 那么必定 可以保证 a b是递增或者递减的，所以子问题保证了 就可以 往上回溯，是的 整个 数组是 有序的
**/
//
// MergeSort.m
// 排序算法
//
// Created by apple on 16/6/15.
// Copyright © 2016年 lichory. All rights reserved.
//
#import "MergeSort.h"
@implementation MergeSort
- (void)startSort {
[self sortWithStartIndex:0 endIndex:(int)self.sortArr.count -1];
}
- (void)sortWithStartIndex:(int)startIndex endIndex:(int)endIndex {
if (startIndex >= endIndex) {
return;
}
int mid = (startIndex+endIndex)/2;
[self sortWithStartIndex:startIndex endIndex:mid];//左边有序
[self sortWithStartIndex:mid+1 endIndex:endIndex];//右边有序
//归并
[self mergeSortWithStartIndex:startIndex midIndex:mid endIndex:endIndex];
}
/* 将两个有序的 归并成一个数组**/
- (void)mergeSortWithStartIndex:(int)startIndex midIndex:(int)midIndex endIndex:(int)endIndex {
/*
* startIndex -> midIndex(包括midIndex)
* midIndex+1 -> endIndex(包括endIndex)
**/
int i = startIndex;
int j = midIndex+1;
NSMutableArray * temp = [NSMutableArray array];
while (i <= midIndex && j <= endIndex) {
if ([self.sortArr[i] floatValue] > [self.sortArr[j] floatValue]) {
[temp addObject:self.sortArr[j++]];
}else {
[temp addObject:self.sortArr[i++]];
}
}
while (i <= midIndex) {
[temp addObject:self.sortArr[i++]];
}
while (j <= endIndex) {
[temp addObject:self.sortArr[j++]];
}
for (i = startIndex,j = 0; i <= endIndex ; i++,j++) {
self.sortArr[i] = temp[j];
}
}
@end
5.快速排序
可以理解成填坑 补坑的过程
//
// QuickSort.m
// 排序算法
//
// Created by apple on 16/6/15.
// Copyright © 2016年 lichory. All rights reserved.
//
#import "QuickSort.h"
@implementation QuickSort
- (void)startSort {
[self sortWithStartIndex:0 endIndex:(int)self.sortArr.count -1];
}
/*
* 快速排序的思想 其实和归并有点相同，也是分治的思想
**/
- (void)sortWithStartIndex:(int)startIndex endIndex:(int)endIndex {
if (startIndex >= endIndex) {
return;
}
int partion = [self partionForQuickSortWithStartIndex:startIndex endIndex:endIndex];
[self sortWithStartIndex:startIndex endIndex:partion]; //左边有序
[self sortWithStartIndex:partion+1 endIndex:endIndex];// 右边有序
}
/*
* 补坑的方法
**/
- (int)partionForQuickSortWithStartIndex:(int)startIndex endIndex:(int)endIndex {
int i = startIndex;
int j = endIndex;
// 1. 先占一个坑，i指针当前的这个坑
NSNumber * value = self.sortArr[startIndex];
while (i < j) {
/* 循从右边到 左边循环 如果存在比value 小的值保留同时break**/
while (i < j) {
if ([self.sortArr[j] floatValue] < [value floatValue]) {
//找到了 右边存在一个比 value 要小的值 那么直接 把这个值放到value 的位置中
//那么现在 j指向的位置是可以用来赋值的
// 2. 现在把值 填入 到前面的那个坑中，现在j 指向这个坑
self.sortArr[i] = self.sortArr[j];
i++; //通知开始 i指针工作
break;
}else {
j--;
}
}
/* 循从左到 右边循环 ，如果存在比value 大的值保留同时break **/
while (i < j) {
if ([self.sortArr[i] floatValue] > [value floatValue]) {
// 3. 现在把值 填入 到前面的那个坑中，现在i 指向这个坑
self.sortArr[j] = self.sortArr[i];
j--;//通知开始 j指针工作
break;
}else {
i++;
}
}
}
/*4. 最终肯定 i 和 j 同时 指向当前的这个 坑，然后 直接把value 值给它**/
self.sortArr[j] = value;
return j;
}
@end
