title: 2017-10-18控制流
tags: binsearch else-if, shellsort, insertsort
grammar_cjkRuby: true
else-if 折半查找binsearch
将待查找数据先和中间进行比较，如果待查找数据等于中间数据则直接返回，如果小于中间数则继续在前一半数据中进行判断，如果大于中间数则继续在后一半数据中进行判断。重复进行循环，直至搜索完数据。
/***********************/
//章节：第三章else-if
//内容：binsearch
/***********************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<sys/stat.h>
#include<time.h>
#define MAX_ELEMENT 10000
#define LOOP 200000
int binsearch(int x,int v[],int n);//x is the element to search for ,n the length
int binsearch2(int x,int v[],int n);
int main(void){
int testdate[MAX_ELEMENT];
int index; //index of element to search for
int n = 200; //element to search for
int i;
clock_t time_taken;//其实就是一个长整型，clock（）返回程序运行的滴答数，要得到秒数则除以CLOCKS_PER_SEC
for(i = 0;i < MAX_ELEMENT; ++i){
testdate[i]=i;
//printf("%d\n", testdate[i]);
}
for(i = 0,time_taken = clock();i < LOOP;++i){
index = binsearch(n,testdate,MAX_ELEMENT);
}
time_taken = clock() - time_taken;
if(index < 0)
printf("Element %d is not found in \n",n);
else
printf("Element %d is found at the index %d\n", n,index);
printf("binsearch() took %lu clocks[%lu seconds]\n",time_taken,time_taken/CLOCKS_PER_SEC);
for(i = 0,time_taken = clock();i < LOOP;++i){
index = binsearch2(n,testdate,MAX_ELEMENT);
}
time_taken = clock() - time_taken;
if(index < 0)
printf("Element %d is not found in \n",n);
else
printf("Element %d is found at the index %d\n", n,index);
printf("binsearch2() took %lu clocks[%lu seconds]\n",time_taken,time_taken/CLOCKS_PER_SEC);
}
int binsearch(int x,int v[],int n){
int low,mid,high;
low = 0;
high = n-1;
while(low <= high){
mid = (low+high)/2;
if(x < v[mid])
high = mid - 1;
else if (x > v[mid])
low = mid + 1;
else
return mid;
}
return -1;
}
int binsearch2(int x,int v[],int n){
int low,mid,high;
low = 0;
high = n-1;
mid = (low+high)/2;
while(low <= high && x != v[mid]){
if(x < v[mid])
high = mid -1;
else
low = mid + 1;
mid = (low+high)/2;
}
if (x == v[mid])
return mid;
else
return -1;
}
插入排序
希尔排序
/***********************/
//章节：第三章控制流
//内容：shellsort，insertsort
/***********************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<sys/stat.h>
void insertsort(int a[],int n){
int i,j,tmp;
for(i = 1; i < n;i++){
tmp = a[i];
for(j = i-1;j >= 0&&a[j] > tmp;j--)
a[j+1] = a[j];
a[j+1] = tmp;
}
}
void shellsort(int a[],int n){
int i,j,gap,tmp;
for(gap = n/2 ; gap > 0 ; gap /= 2){
for(i = gap; i < n; i++){
tmp = a[i];
for(j = i - gap; j >= 0&&a[j] > tmp; j-=gap)
a[j+gap] = a[j];
a[j+gap] = tmp;
}
}
}
int main(void){
int a[]={1,2,5,10,4,9,1,8},b[]={1,2,5,10,4,9,1,8};
int n,i;
n = 8;
insertsort(a,n);
for(i=0;i<n;i++){
printf("%d\n",a[i]);
}
printf(">>>>>>>>>>>>\n");
shellsort(b,n);
for(i=0;i<n;i++){
printf("%d\n",b[i]);
}
}