LeetCode学习_day1:原地算法
2024-10-19 00:18:29
原地算法:是一种使用小的,固定数量的额外之空间来转换资料的算法。当算法执行时,输入的资料通常会被要输出的部份覆盖掉。
范例:冒泡排序、选择排序、插入排序、希尔排序
(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);
最新文章
- Atitit &#160;从 RGB 到 HSL 或 HSV 的转换
- Eclipse快捷键/快捷操作汇总
- go tool proof
- hdu Pie
- 1.6.6 De-Duplication(重复数据删除)
- nginx 日志管理
- NuGet学习笔记——初识NuGet及快速安装使用
- HTML输出 一 控制列背景颜色
- Android开发——自动生成Android屏幕适配的dimens.xml文件
- Java工具类:获取long型唯一ID
- mybatis0204 一对多查询
- Android应用开发学习之Toast消息提示框
- windows环境中mysql忘记root密码的解决办法
- HDU 4777 Rabbit Kingdom
- vue.js开发环境搭建以及创建一个vue实例
- git学习——Github关联(2)
- 二叉树与AVL树
- kafka 幂等生产者及事务(kafka0.11之后版本新特性)
- 按PEP8风格自动排版Python代码
- oracle:TNS:监听程序无法分发客户机连接