1.fabnaci数列算法
####递归实现
long diguiFabnaci(n){
if(n < 1) return -1;
if (n == 1 || n == 2) {
return 1;
}
return diguiFabnaci(n - 1) + diguiFabnaci(n - 2);
}
####for循环实现
long forFabnaci(n){
if(n < 1) return -1;
if (n == 1 || n == 2) {
return 1;
}
long f1 = 1l;
long f2 = 1l;
long f = 0l;
for (int i = 0; i < n - 2; i ++) {
f = f1 + f2;
f1 = f2;
f2 = f;
}
return f;
}
2、交换两个数的值
####方式一(中间数）
c = a;
a = b;
b= c;
####方式二（^）
a = a^b
b= b^a
a = a^b
(a^=b^=a^=b)
####方式三(求和)
a = a + b
b = a - b
a = a - b
(a = a + b - (b = a))
3、堆排序
堆排序复杂度分析：
堆排序运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。在构建堆的过程中，对每个终端节点最多进行两次比较操作，因此整个排序堆的时间复杂度为O(n)。
在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间，并需要取n-1次堆顶记录，因此总体来说，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始数据的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。在这性能上显然要远远好过于冒泡、选择、插入的O(n2)的时间复杂度了。
空间复杂度上，它只有一个用来交换的暂存单元，也是非常不错。不过由于记录的比较和交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。
另外，由于初始构建堆排序需要的比较次数较多，因此，它不适合待排序序列个数较少的情况。
堆排序代码：
- (void)heapSort:(NSMutableArray *)list
{
NSInteger i ,size;
size = list.count;
//找出最大的元素放到堆顶
for (i= list.count/2; i>=0; i--) {
[self createBiggesHeap:list withSize:size beIndex:i];
}
while(size > 0){
[list exchangeObjectAtIndex:size-1 withObjectAtIndex:0]; //将根(最大) 与数组最末交换
size -- ;//树大小减小
[self createBiggesHeap:list withSize:size beIndex:0];
}
NSLog(@"%@",list);
}
- (void)createBiggesHeap:(NSMutableArray *)list withSize:(NSInteger) size beIndex:(NSInteger)element
{
NSInteger lchild = element *2 + 1,rchild = lchild+1; //左右子树
while (rchild < size) { //子树均在范围内
if (list[element]>=list[lchild] && list[element]>=list[rchild]) return; //如果比左右子树都大，完成整理
if (list[lchild] > list[rchild]) { //如果左边最大
[list exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
element = lchild; //循环时整理子树
}else{//否则右面最大
[list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
element = rchild;
}
lchild = element * 2 +1;
rchild = lchild + 1; //重新计算子树位置
}
//只有左子树且子树大于自己
if (lchild < size && list[lchild] > list[element]) {
[list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
}
}
4、冒泡排序优化
(void)logArrayFunctionNice {
int count = 0;
int forcount = 0;
BOOL flag = YES;
NSMutableArray * arr = @[@16,@1,@2,@9,@7,@12,@5,@3,@8,@13,@10].mutableCopy;
for (int i = 0; i < arr.count && flag; i++) {
forcount++;
flag = NO;
for (int j = (int)arr.count-2; j > i; j--) {
count++;
if (arr[j] < arr[j+1]) {
[arr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
flag = YES;
}
}
[self logArr:arr];
}
NSLog(@"循环次数：%d",forcount);
NSLog(@"共%d次比较",count);
}
//打印
16 13 1 2 9 7 12 5 3 8 10
16 13 12 1 2 9 7 10 5 3 8
16 13 12 10 1 2 9 7 8 5 3
16 13 12 10 9 1 2 8 7 5 3
16 13 12 10 9 8 1 2 7 5 3
16 13 12 10 9 8 7 1 2 5 3
16 13 12 10 9 8 7 5 1 2 3
16 13 12 10 9 8 7 5 3 1 2
16 13 12 10 9 8 7 5 3 2 1
16 13 12 10 9 8 7 5 3 2 1
循环次数：10
共45次比较
网友评论