# 在Object-C中学习数据结构与算法之排序算法
![](http://oriq21dog.bkt.clouddn.com/bloc/2017-07-15-Snip20170715_24.png)
> 笔者在学习数据结构与算法时,尝试着将排序算法以动画的形式呈现出来更加方便理解记忆,本文配合[Demo 在Object-C中学习数据结构与算法之排序算法](https://github.com/MisterBooo/Play-With-Sort-OC)阅读更佳。
> 你可以在公众号 **五分钟学算法** 获取更多数据结构与算法相关的内容
> 公众号回复 **github** 获取十大经典排序动画。
## 目录
* 选择排序
* 冒泡排序
* 插入排序
* 快速排序
* 双路快速排序
* 三路快速排序
* 堆排序
* 总结与收获
* 参考与阅读
### 选择排序
选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
#### 1.算法步骤
1. 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
2. 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
3. 重复第二步,直到所有元素均排序完毕。
#### 2.动画演示
![](http://oriq21dog.bkt.clouddn.com/bloc/2017-08-02-%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F.gif)
#### 3.代码实现
```
#pragma mark - /**选择排序*/
- (void)mb_selectionSort{
for (int i = 0; i < self.count; i++) {
for (int j = i + 1; j < self.count ; j++) {
if (self.comparator(self[i],self[j]) == NSOrderedDescending) {
[self mb_exchangeWithIndexA:i indexB:j];
}
}
}
}
```
### 冒泡排序
冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
#### 1.算法步骤
1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤,除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
#### 2.动画演示
![](http://oriq21dog.bkt.clouddn.com/bloc/2017-08-02-%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F.gif)
#### 3.代码实现
```
#pragma mark - /**冒泡排序*/
- (void)mb_bubbleSort{
bool swapped;
do {
swapped = false;
for (int i = 1; i < self.count; i++) {
if (self.comparator(self[i - 1],self[i]) == NSOrderedDescending) {
swapped = true;
[self mb_exchangeWithIndexA:i indexB:i- 1];
}
}
} while (swapped);
}
```
### 插入排序
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
![](http://oriq21dog.bkt.clouddn.com/bloc/2017-08-02-Snip20170802_30.png)
#### 1.算法步骤
1. 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
#### 2.动画演示
![](http://oriq21dog.bkt.clouddn.com/bloc/2017-08-02-%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F.gif)
#### 3.代码实现
```
#pragma mark - /**插入排序*/
- (void)mb_insertionSort{
for (int i = 0; i < self.count; i++) {
id e = self[i];
int j;
for (j = i; j > 0 && self.comparator(self[j - 1],e) == NSOrderedDescending; j--) {
[self mb_exchangeWithIndexA:j indexB:j- 1];
}
self[j] = e;
}
}
```
### 归并排序
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
>1. 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法)
>2. 自下而上的迭代;
本文使用的是**自顶向下**的归并排序
#### 1.算法步骤
1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
4. 重复步骤 3 直到某一指针达到序列尾;
5. 将另一序列剩下的所有元素直接复制到合并序列尾。
#### 2.动画演示
![](http://oriq21dog.bkt.clouddn.com/bloc/2017-08-02-%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F.gif)
#### 3.代码实现
```
#pragma mark - /**归并排序 自顶向下*/
- (void)mb_mergeSort{
[self mb_mergeSortArray:self LeftIndex:0 rightIndex:(int)self.count - 1];
}
- (void)mb_mergeSortArray:(NSMutableArray *)array LeftIndex:(int )l rightIndex:(int)r{
if(l >= r) return;
int mid = (l + r) / 2;
[self mb_mergeSortArray:self LeftIndex:l rightIndex:mid];
[self mb_mergeSortArray:self LeftIndex:mid + 1 rightIndex:r];
[self mb_mergeSortArray:self LeftIndex:l midIndex:mid rightIndex:r];
}
- (void)mb_mergeSortArray:(NSMutableArray *)array LeftIndex:(int )l midIndex:(int )mid rightIndex:(int )r{
SEL func = NSSelectorFromString(@"resetSortArray:");
// 开辟新的空间 r-l+1的空间
NSMutableArray *aux = [NSMutableArray arrayWithCapacity:r-l+1];
for (int i = l; i <= r; i++) {
// aux 中索引 i-l 的对象 与 array 中索引 i 的对象一致
aux[i-l] = self[i];
}
// 初始化,i指向左半部分的起始索引位置l;j指向右半部分起始索引位置mid+1
int i = l, j = mid + 1;
for ( int k = l; k <= r; k++) {
if (i > mid) { // 如果左半部分元素已经全部处理完毕
self.comparator(nil, nil);
self[k] = aux[j - l];
j++;
}else if(j > r){// 如果右半部分元素已经全部处理完毕
self.comparator(nil, nil);
self[k] = aux[i - l];
i++;
}else if(self.comparator(aux[i - l], aux[j - l]) == NSOrderedAscending){// 左半部分所指元素 < 右半部分所指元素
self[k] = aux[i - l];
i++;
}else{
self.comparator(nil, nil);
self[k] = aux[j - l];
j++;
}
NSMutableArray *mutArray = [NSMutableArray array];
[self enumerateObjectsUsingBlock:^(MBBarView * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
[mutArray addObject:[NSString stringWithFormat:@"%f",obj.frame.size.height]];
}];
objc_msgSendSortArray(self.vc,func,mutArray);
}
}
```
### 快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效
没有合适的资源?快使用搜索试试~ 我知道了~
基础排序 冒泡排序 插入排序 快速排序 双路快速排序 三路快速排序 堆排序.zip
共24个文件
m:7个
h:5个
plist:3个
需积分: 1 0 下载量 86 浏览量
2024-03-20
13:14:26
上传
评论
收藏 72KB ZIP 举报
温馨提示
快速排序 基础排序 冒泡排序 插入排序 快速排序 双路快速排序 三路快速排序 堆排序.zip
资源推荐
资源详情
资源评论
收起资源包目录
基础排序 冒泡排序 插入排序 快速排序 双路快速排序 三路快速排序 堆排序.zip (24个子文件)
基础排序 冒泡排序 插入排序 快速排序 双路快速排序 三路快速排序 堆排序
Play-With-Sort-OC
ViewController.h 229B
Sort
MBHeap.m 3KB
MBHeap.h 1KB
Base.lproj
Main.storyboard 3KB
LaunchScreen.storyboard 2KB
AppDelegate.h 291B
AppDelegate.m 2KB
main.m 348B
NSMutableArray+MBSort.h 960B
MBBarView.m 978B
MBBarView.h 257B
NSMutableArray+MBSort.m 12KB
ViewController.m 11KB
Info.plist 1KB
Assets.xcassets
AppIcon.appiconset
Contents.json 585B
Play-With-Sort-OCTests
Play_With_Sort_OCTests.m 943B
Info.plist 680B
README.md 16KB
Play-With-Sort-OC.xcodeproj
project.pbxproj 19KB
xcuserdata
Zeno.xcuserdatad
xcdebugger
Breakpoints_v2.xcbkptlist 523B
xcschemes
Play-With-Sort-OC.xcscheme 4KB
xcschememanagement.plist 579B
project.xcworkspace
contents.xcworkspacedata 162B
xcuserdata
Zeno.xcuserdatad
UserInterfaceState.xcuserstate 45KB
共 24 条
- 1
资源评论
mldxxxxll5
- 粉丝: 3287
- 资源: 770
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功