查找和排序

     首先我承认我算法那部分是真的很烂,但是经典常用的还是有必要记一记的.

 

     折半查找法,需要在有序的集合中才起作用.其核心是,每次获取折半中元素,对比,大于小于,继续折半...一直到折半值等于要查找的元素.贴下代码:

#include <stdio.h>

int main(){
    int fbnqq[]={0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};

    int i=0,n;
    scanf("%d",&n);
    getchar();

    int head = 0, tail = sizeof(fbnqq)/sizeof(int)-1, mid = (head + tail) / 2;
    while(head <= tail){
        if(fbnqq[mid] == n){
            printf("find num in index:%d\n", mid);
            break;
        }
        if(n < fbnqq[mid])
            tail = mid - 1;
        else
            head = mid + 1;
        if(head > tail)
            printf("num not found! %d-%d\n",head > mid ? fbnqq[mid] : fbnqq[mid-1], head > mid ? fbnqq[mid+1] : fbnqq[mid]);
        mid = (head + tail) / 2;
    }
    return 0;
}

       

      快速排序,其核心是分而治之,选头尾和枢纽元,然后就在枢纽元两边交换,效果像这样 head | pivot | tarl ,然后递归下去,返回条件是头小于尾即可.贴下代码:

#include <stdio.h>
#include <time.h>

void QuickSort(int array[],int head,int tarl);

int main(int argc,char **argv){
    int array[1000];

    srand((unsigned)time(NULL));
    int j=1000;
    while(j--)
        array[j] = rand() % 1000;

    QuickSort(array, 0, sizeof(array) / sizeof(int) -1);

    int *i = array;
    while(i != (int *)(&array + 1))
        printf("%d->", (i++)[0]);
    printf("\n");
    return 0;
}

void QuickSort(int array[],int head,int tarl){
    if (head < tarl){
        int pivot = (head + tarl) / 2;
        int tmp_head = head, tmp_tarl = tarl;
        while(tmp_head < tmp_tarl){
            while((tmp_head < pivot) && (array[tmp_head] <= array[pivot]))
                tmp_head++;
            while((tmp_tarl > pivot) && (array[tmp_tarl] >= array[pivot]))
                tmp_tarl--;
            if(tmp_head == pivot)
                pivot = tmp_tarl;
            else if(tmp_tarl == pivot)
                pivot = tmp_head;
            int tmp_value = array[tmp_head];
            array[tmp_head] = array[tmp_tarl];
            array[tmp_tarl] = tmp_value;
        }
        QuickSort(array, head, pivot - 1);
        QuickSort(array, pivot + 1, tarl);
    }
}