最近在招IOS开发。发现好多IOS的开发，基础的东西比较差。都是在写一些页面啊，业务逻辑啊（自己也没有多厉害）
自己就想整理一些东西，都是用oc写的。也当自己复习一下吧，第一次写，有问题，还请见谅
插入排序
相关概念
将原有序列分为有序区和无序区，然后通过比较将无序区的数据插入到有序区里
v1.0
v1.0 普通插入排序
假设数组为a[0…n]
- 将原本的序列分为有序区和无序区，a[0…i-1]为有序区，a[i…n]为无序区
- 从无序区拿出第一个元素即：a[i],跟有序区末尾进行比较即：a[i-1]
- 若a[i-1]大于a[i]，则交换位置，然后继续向前比较，指导a[i-1]不大于a[i]为止
- 重复2~3步骤
-(void)insertionSort:(NSMutableArray*)data{
for(int i = 0 ; i < data.count ; i ++){
for(int j = i ; j > 0 && data[j] < data[j-1] ; j --){
NSNumber *t = data[j];
data[j] = data[j-1];
data[j-1] = t;
}
}
}
v2.0
v2.0 优化插入排序
普通版：每次都要和前一位比较，小的话进行交换，要有3次赋值操作，
优化后 ：
- 将原本的序列分为有序区和无序区，a[0…i-1]为有序区，a[i…n]为无序区
- 从无序区拿出第一个元素即：a[i],跟有序区末尾进行比较即：a[i-1] (到此步骤和v1.0一样)
- 若a[i-1]大于a[i]，则a[i-1]向后移动一位
- 重复步骤3，直到找到小于或等于a[i]的有序元素，将a[i]插入到该位置的下一个位置中
- 重复2~4步骤
可以看出优化后的步骤，每次减少了两次赋值，每次比较只是让有序数组的位置向后挪动一位
找到对应的位置后，再将无序的元素插入到指定位置
-(void)insertionSortToOptimize:(NSMutableArray*)data{
for (int i = 0 ; i < data.count ; i ++){
NSNumber * t = data[i];
int j ;
for(j = i ; j > 0 && t < data[j-1] ; j --){
data[j] = data[j-1];
}
data[j] = t;
}
}
思考：
如果我们前面的有序数组是按照顺序的，待插入的需要从有序区的末尾去找到自己对应的位置，那么我们是否可以对这个查找的过程进行优化呢？比如，二分查找！
v3.0
在2.0的基础上进行优化，采用二分查找法，向前面的有序数组进行查找并交换
-(void)insertionSortByBinarySearch:(NSMutableArray*)data{
for(int i = 0 ; i < data.count ; i ++){
NSNumber * t = data[i];
int left = 0;
int right = i -1;
int mid = 0;
while (left <= right) {
mid = (right - left)/2 +left;
if(t > data[mid])
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
for(int j = i ; j > left ; j --){
data[j] = data[j-1];
}
data[left] = t;
}
}
耗时比较
乱序数组(数据量大时)
| 耗时(毫秒) | v1.0 | v2.0 | V3.0 | 系统 |
|---|---|---|---|---|
| 1W数据 | 1361 | 741 | 694 | 9 |
| 5W数据 | 33978 | 18879 | 15443 | 50 |
通过表格可以看出，优化过后的2.0相比较1.0速度快了1倍，但是距离系统的排序相差还很多
思考：
如果是很少的数据量呢？插入排序会有什么效果
乱序数据(小数据量)
| 耗时(微秒) | v1.0 | v2.0 | V3.0 | 系统 |
|---|---|---|---|---|
| 10数据 | 7 | 3 | 3 | 11 |
| 20数据 | 11 | 7 | 7 | 16 |
| 50数据 | 47 | 25 | 25 | 29 |
通过表格测试数据可以看出，在数据量小的时候，插入排序还是有优势的
思考：
插入排序，相较其他的排序还有什么优点呢？（现在只有系统排序）只有数据量少的时候可用吗？
近似有序的数组
抽取整体数据抽取10条进行无序操作
| 耗时(毫秒) | V2.0 | v3.0 | 系统 |
|---|---|---|---|
| 1W数据 | 3 | 4 | 4 |
| 5W数据 | 11 | 15 | 15 |
| 10W数据 | 26 | 36 | 30 |
| 100W数据 | 241 | 473 | 320 |
通过数据我们可以发现在近似有序的数组进行排序的时候，插入排序还是很有优势的。
因为在近似有序的数组进行排序的时候，每次从无序区拿出数据进行比较的时候，只需要比较一次就可以了
从而插入排序
但是我们会发现v3.0的反而会比v2.0的耗时多一些。
这是因为在3.0我们使用了二分查找法，从而使每次比较的次数反而增加了
结论
在近似有序的数组进行排序的时候。插入排序会从 进化成
使用场景
我们会在哪些场景使用插入排序呢？
- 如果我们本地有1万个有序的列表。服务器会每秒发过来一条新数据进行排序，那么我们每次拿到新数据，加入到数组里进行排序的时候插入排序就有用武之地了！
网友评论