算法记忆

在线 编译 地址 http://www.dooccn.com/cpp/#contact

二分查找

递归

注意 left<=right 的时候 binarySearch传入的是mid-1 和mid+1 ，不然死循环

#include <iostream>
using namespace std;
int binarySearch(int* a, int left,int right,int val){
    if(left<= right){
        int mid = (left+right)/2;
        if(a[mid]>val){
            return binarySearch(a,left,mid-1,val);
        }else if(a[mid]<val){
            return binarySearch(a,mid+1,right,val);
        }else{
            return mid;
        }
    }
    return -1;
}
int main()
{
    int a[] = {22,33,44,55,66,77};
    int val = 56;
    int x = binarySearch(a,0,5,val);
   cout <<x;
   return 0;
}

非递归

#include <iostream>
using namespace std;
int binarySearch(int* a, int left,int right,int val){
    while(left<= right){
            int mid = (left+right)/2;
        if(a[mid]>val){
            right = mid-1;
        }else if(a[mid]<val){
            left = mid+1;
        }else{
            return mid;
        }
    }
    return -1;
}
int main()
{
    int a[] = {22,33,44,55,66,77};
    int val = 55;
    int x = binarySearch(a,0,5,val);
   cout <<x;
   return 0;
}

堆排序

#include <iostream>
using namespace std;
// n =a.size()-1 
void adjust(int* a ,int cur,int n){
        while(2*cur+2 <= n){
            int index = a[2*cur+1]>a[2*cur+2]?2*cur+1:2*cur+2;
            if(a[cur]< a[index]){
                int tmp = a[cur];
                a[cur] = a[index];
                a[index] = tmp;
                cur = index;
            }else{
                break;
            }
            
        }
} 
int heapSort(int* a, int n){
    for(int i = n/2 ;i>=0;i--){
        //create big heap 
        adjust(a,i,n);
    }
    for(int i = n;i>=0;i--){
        int tmp = a[i];
        a[i] = a[0];
        a[0] = tmp;
        if(i-1>=0){
            adjust(a,0,i-1);
        }
    }
}
int main()
{
    int a[] = {22,113,454,232,565,11,34,55};   
     heapSort(a,7);
     for(int i=0;i<8;i++){
          cout <<a[i]<<endl;
     }
   return 0;
}

链表翻转

#include <iostream>
using namespace std;
// n =a.size()-1 
struct Node{
  int x;
  Node* next;
  Node(int val):x(val),next(NULL){}
};

Node* reverseLinkList(Node* pHead){
    if(!pHead) return NULL;
    Node* pBehind = NULL;
    Node* pFront = NULL;
    Node* p = pHead;
    while(p){
        pFront = p->next;
        p->next = pBehind;
        pBehind = p;
        p = pFront;
    }
    return pBehind;
}


int main()
{
    Node* node = new Node(1);
    node->next = new Node(3);
    node->next->next = new Node(5);
    Node* nodere = reverseLinkList(node);
    while(nodere){
        cout<<nodere->x<<endl;
        nodere = nodere->next;
    }
    return 0;
}