插入排序

[c]代码库

#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#define NOT_FOUND -1
 
int get_rand(int upbound) {
    //srand(time(0)); //srand=stdlib.h; time=time.h
    return (int)(ceil(rand()%upbound)); //ceil=math.h; rand=stdlib.h
}
 
int get_runtime() {
    return clock(); //time=time.h
}
 
int linear_search(int arr[], int len, int key) { //continuing finding
    int j=-1; int i;
    for (i=0;i<=len-1;i++) if (arr[i]==key) j=i;
    return j;
}
 
 
int better_search(int arr[], int len, int key) { //terminating after finding
    int i;
    for (i=len-1;i>=0;i--) if (arr[i]==key) break;
    return i;
}
 
int sentinel_linear_search(int arr[], int len, int key) { //preventing violation
    int last;
    last=arr[len-1];
    arr[len-1]=key;
 
    int i=0;
    while (arr[i]!=key) i++;
    if (i<(len-1)) return i;
    if (last==key) return len-1;
    else return -1; //check whether is it just the last
}

int main() {
	srand(time(0));
	int a[200000];
	for (int k=0;k<=190000;k++) {
		a[k+10]=get_rand(10);
		if (k==131072) a[k+10]=22;
	}
	printf("1. get random numbers\n");
	for (int randi=0;randi<=10;randi++) 
		printf("%d\n",get_rand(100));
	printf("2. LINEAR_SEARCH\n");
	int time1_S=clock();
	int result1=linear_search(a,190000,22);
	int time1_E=clock();
	printf("FOUND_RESULT=%d\n",result1);
	printf("TIME_ELAPSED_MS: %d\n",time1_E-time1_S);
	printf("3. BETTER_SEARCH\n");
	int time2_S=clock();
	int result2=better_search(a,190000,22);
	int time2_E=clock();
	printf("FOUND_RESULT=%d\n",result2);
	printf("TIME_ELAPSED_MS: %d\n",time2_E-time2_S);
	printf("4. SENTINEL_LINEAR_SEARCH\n");
	int time3_S=clock();
	int result3=sentinel_linear_search(a,190000,22);
	int time3_E=clock();
	printf("FOUND_RESULT=%d\n",result3);
	printf("TIME_ELAPSED_MS: %d\n",time3_E-time3_S);
	return 0;
}