学步园

第一题求最小值、最大值和均值显然不用排序，只需要扫描一遍数组即可。关于中值，换个思路思考，就是找排好序的数组中的index为N/2的数，所以方法出来了

方法一：先对数组进行排序，然后直接得到arr[N/2]即为索求的中位数，时间复杂度为O(nlgn)，在这里面如果调用库函数qsort的花费的时间会比自己去写一个排序函数花费更多的时间，qsort最好情况为O(nlgn),所以可以用其他一些严格O(nlgn)的排序算法，比如归并排序，堆排序等等。自己去实现qsort的话，双向的扫描会比单向扫描效率更高，且会避免所有元素相同造成的效率低下。自己实现的双向qsort对于100000个－1000000－－－－1000000中的随机数大概花费20ms, 而库函数大约花费30ms

方法二：很显然，我们只是想求数组中第N/2大的数，其他的数排不排好序对结果没有影响，而我们的方法一显然做了很多的无用功，那么怎么快速寻找数组中第K大的数呢，对，方法很多的，最有效的方法就是利用快速排序的思想，快速选择，比如我们要找第1000大的数，所以0－999的数只要比它小就行了，没必要对他们排序，讲到这里是不是茅塞顿开了，这种方法网上资料很多，利用这种方法对相同的100000个数进行处理，花费时间<10 ms，时间复杂度大约为O(n)

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

#define MAXLINE 100000

#define TEST 2
/*
 * qsort function
 */
int cmp(const void *a,const void *b)
{
	int *c = (int*)a;
	int *d = (int*)b;
	return *c - *d;
}

/*
 * method No_02   first sort,and then you can get middle value by list[N/2]
 */
void my_qsort(int *list,int left,int right){
	if(left >= right)
		return ;
	int key = list[left];
	int i = left,j = right+1;
	int temp;
	while(i<j)
	{
		do{
			i++;
		}while(i<=right && list[i]<key);

		do{
			j--;
		}while(list[j] > key);

		if(i>j)
			break;
		temp = list[j];
		list[j] = list[i];
		list[i] = temp;
	}
	list[left] = list[j];
	list[j] = key;

	my_qsort(list,left,j-1);
	my_qsort(list,j+1,right);
}

int mid_value(int *list,int N)
{
	my_qsort(list,0,N-1);
	return list[N/2];
}
/*
 * method No_03 by using the method of the qsort
 */
int qselect(int *list, int left,int right,int index)
{
	if(left == right)			
		return list[left];
	int key = list[left];
	int i = left, j = right+1;
	int temp;
	while(i<j){
		do{
			i++;
		}while(i<=right && list[i] < key);

		do{
			j--;
		}while(list[j] > key);

		if(i > j)
			break;
		temp = list[j];
		list[j] = list[i];
		list[i] = temp;
	}
	list[left] = list[j];
	list[j] = key;

	if(j==index)
		return list[j];
	else if(j < index)
	{
		return qselect(list,j+1,right,index);
	}
	else{
		return qselect(list,left,j-1,index);
	}
}




int
main(void)
{
	int *list;
	list = (int*)malloc(sizeof(int)*MAXLINE);

	FILE *fp = fopen("data.in","r");
	if(fp == NULL)
	{
		perror("fopen file error !");
		return EXIT_FAILURE;
	}
	int i = 0;
	while(i<MAXLINE && fscanf(fp,"%d",&list[i])==1)i++;
	fclose(fp);
#if TEST == 1                                       
    clock_t start = clock();                      // 100000 elements consuming 30ms
	qsort(list,MAXLINE,sizeof(list[0]),cmp);
	clock_t end = clock();
	printf("method No_1: consuming time is %d ms,and the mid_value is %d\n",(end-start)/(CLOCKS_PER_SEC/1000),list[MAXLINE/2]);
#endif

#if TEST==2
    clock_t start = clock();                      // 100000 elements consuming 20ms
	int value = mid_value(list,MAXLINE);
	clock_t end = clock();
	printf("method No_1: consuming time is %d ms,and the mid_value is %d\n",(end-start)/(CLOCKS_PER_SEC/1000),value);
#endif
	
#if TEST==3
	clock_t start = clock();                     // 100000 elements consuming <10 ms  , and sometimes it consums 0ms
	int value = qselect(list,0,MAXLINE-1,MAXLINE/2);
	clock_t end = clock();
	printf("method No_2: consuming time is %d ms,and the mid_value is %d\n",(end-start)/(CLOCKS_PER_SEC/1000),value);
#endif
	return EXIT_SUCCESS;
}