原地算法:是一种使用小的,固定数量的额外之空间来转换资料的算法。当算法执行时,输入的资料通常会被要输出的部份覆盖掉。

范例:冒泡排序、选择排序、插入排序、希尔排序

(1)冒泡排序:

冒泡排序算法的原理如下:
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
冒泡排序OC代码如下:
for (int i = ; i<result.count; i++) {
for (int j = ; j<result.count--i; j++) {
NSInteger left = [result[j] integerValue];
NSInteger right = [result[j+] integerValue];
if (left<right) {
[result exchangeObjectAtIndex:j withObjectAtIndex:j+];
}
}
}
NSLog(@"%@",result);

(2)选择排序--不稳定排序

选择排序算法的原理如下:
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
①初始状态:无序区为R[..n],有序区为空。
②第1趟排序
在无序区R[..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[]交换,使R[..]和R[..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时,当前有序区和无序区分别为R[..i-]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区
选择排序的OC代码如下:
NSMutableArray *sortArray = [NSMutableArray arrayWithObjects:@"", @"", @"", @"", nil];
for (NSInteger i = ; i < sortArray.count; i++) {
NSInteger k = i;
for (NSInteger j = i + ; j < sortArray.count; j++) {
//这一步我做错了,我的初始条件是 j = i, 没有考虑到,第一个元素 跟第二个元素对比就可以了,没有必要每次都第一个跟第一个开始对比
NSInteger jValue = [sortArray[j] integerValue];
NSInteger kValue = [sortArray[k] integerValue];
if (jValue < kValue) {
k = j;
}
}
[sortArray exchangeObjectAtIndex:i withObjectAtIndex:k];
}
NSLog(@"--%@---", sortArray);

(3)插入排序--稳定排序

插入排序算法的原理:
算法设计有很多方法。插入排序使用的是增量(incremental)方法;在排好子数组A[..j-]后,将A[j]插入,形成排好序的子数组A[..j];
步骤
⒈从有序数列和无序数列{a2,a3,…,an}开始进行排序;
⒉处理第i个元素时(i=,,…,n),数列{a1,a2,…,ai-}是已有序的,而数列{ai,ai+,…,an}是无序的。用ai与ai-,a i-,…,a1进行比较,找出合适的位置将ai插入;
⒊重复第二步,共进行n-i次插入处理,数列全部有序。
思路
假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a[…k]是局部有序的,保证了插入过程的正确性.
插入排序算法的OC代码如下:
NSMutableArray *sortArray = [NSMutableArray arrayWithObjects:@"", @"", @"", @"", @"", @"", nil];
for (NSInteger i = ; i < sortArray.count; i++) {
  //从第一个开始跟第0个比较,所以 i= 1
if (sortArray.count <) {
break;
}
for (NSInteger j = i; j > ; j--) {
NSInteger rightV = [sortArray[j] integerValue];
NSInteger leftV = [sortArray[j - ] integerValue];
if (rightV < leftV) {
[sortArray exchangeObjectAtIndex:j withObjectAtIndex:j -];
}else {
break;
}
}
}
NSLog(@"--%@---", sortArray);
 

最新文章

  1. Atitit &#160;从 RGB 到 HSL 或 HSV 的转换
  2. Eclipse快捷键/快捷操作汇总
  3. go tool proof
  4. hdu Pie
  5. 1.6.6 De-Duplication(重复数据删除)
  6. nginx 日志管理
  7. NuGet学习笔记——初识NuGet及快速安装使用
  8. HTML输出 一 控制列背景颜色
  9. Android开发——自动生成Android屏幕适配的dimens.xml文件
  10. Java工具类:获取long型唯一ID
  11. mybatis0204 一对多查询
  12. Android应用开发学习之Toast消息提示框
  13. windows环境中mysql忘记root密码的解决办法
  14. HDU 4777 Rabbit Kingdom
  15. vue.js开发环境搭建以及创建一个vue实例
  16. git学习——Github关联(2)
  17. 二叉树与AVL树
  18. kafka 幂等生产者及事务(kafka0.11之后版本新特性)
  19. 按PEP8风格自动排版Python代码
  20. oracle:TNS:监听程序无法分发客户机连接

热门文章

  1. Mysql—数据库管理与表管理
  2. 用户和组的权限管理/特殊权限和ACL(个人笔记)
  3. Matplotlib 日期格式转换
  4. fiddler---Fiddler工具详细介绍
  5. 1. java 基本规则
  6. linux下C/C++编译时系统搜索 include 和 链接库 文件路径的指定
  7. 使用appium过程中常遇到的坑以及解决方案
  8. day6_logging模块
  9. 消息中间件(二)MQ使用场景
  10. Python else