算法

快排

1. 先从数列中取出一个数作为基准数
2. 区分过程，将比这个数大的数全部放到它的右边，小于或等于它的数全放到左边
3. 再对左右区间重复第二步，直到各区间只有一个数

- (void)kuaipai:(NSMutableArray *)arr left:(NSInteger)left right:(NSInteger)right{
    if (left >= right) {
        return;
    }
    
    NSInteger i = left;
    NSInteger j = right;
    NSInteger key = [arr[left] integerValue];
    
    while (i < j) {
        while (i < j && key <= [arr[j] integerValue]) {
            j --;
        }
        arr[i] = arr[j];
        while (i < j && key >= [arr[i] integerValue]) {
            i ++;
        }
        arr[j] = arr[i];
    }
    
    arr[i] = [NSNumber numberWithInteger:key];
    [self kuaipai:arr left:left right:i-1];
    [self kuaipai:arr left:i+1 right:right];
}

冒泡排序

int m[]=[1,2,3,7,4,9];
int i,j,temp;

for (i=m.count; i>=0; i++) {
    for (j=0; j<=i; j++) {
        if (m[j+1] < m[j]) {
            temp = m[j];
            m[j] = m[j=1];
            m[j+1] = temp;
        ]
    }
}

二分查找

不用中间变量交换 a, b

a = 1   b = 2

a = a+b;  a=3 b=2
b = a-b;  a=3 b=1
a = a-b;  a=2 b=1

a = 1   b = 2

a = a^b;  
b = a^b;  
a = a^b;  

a = 1   b = 2

a = a*b;  a=2 b=2
b = a/b;  a=2 b=1
a = a/b;  a=2 b=1

单链表反转

循环算法

class Node {
    int value;
    Node next;
}

Node reverseList(Node head) {
    Node p1, p2, p3;
    if (head == null || hade.next == null) {
    return head;
    }
    
    p1 = head;
    p2 = head.next;
    
    while (p2!=null){
        p3 = p2.next;
        p2.next = p1;
        p1 = p2;
        p2 = p3;
    }
    
    head.next = null;
    head = p1;
    
    return head;
}

递归算法

class Node {
    int value;
    Node next;
}

public Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    Node nextNode = head.next;
    head.next = null;
    Node reverseRest = reverse(nextNode);
    nextNode.next = head;
    return reverseRest;
}