数据库实现原理#2(获取第N个值)
获取数组中的第N个值,仍使用代码说明,算法参考快速排序的思想,详见代码注释.
10年的民丰网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。成都全网营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整民丰建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。成都创新互联公司从事“民丰网站设计”,“民丰网站推广”以来,每个客户项目都认真落实执行。
#include
#include
#include
#include "../pub/pub.h"
//tmparr : 待处理的数组
//counter : 数组元素个数
//n : 从小到大排列,第n个数字(从0开始计数)
static int quicksort_nth_recursion(int tmparr[],int counter,int n)
{
//DEBUG : 数组信息
//print_array(tmparr,counter);
//任意取一个值,找到该值的位置
int pos = 0;
int randompos = rand() % counter;
//把选定的值移到第一个位置
swap(tmparr,0,randompos);
for(int i=1;i < counter;i++)
{
//从1开始遍历,如遍历的元素小于选定的值,则把pos加一并吧该值移到pos所在的位置
//循环完成后,小于随机选择值的数会在pos的左边,大于等于选择值的在pos的右边
if(tmparr[i] < tmparr[0])
{
//如果遍历
swap(tmparr,++pos,i);
}
}
//printf("value = %d,counter = %d,target = %d,pos = %d\n",tmparr[0],counter,n,pos);
//把选定的值移到它该在的地方
swap(tmparr,pos,0);
if(pos == n)
return tmparr[pos];
//递归处理
if(pos < n)//在右边的数组中
quicksort_nth_recursion(tmparr+(pos+1),counter-(pos+1),n-(pos+1));
else//在左边的数组中
quicksort_nth_recursion(tmparr,pos,n);
}
void main(void)
{
//参数:第1个/中间/最后一个
int pos[3] = {1,0,0};
int result = 0,counter = 0;
int arr[] = {4,10,25,100,53,103,50,40,77,9,5,1,65,19,60,51,500};
counter = sizeof(arr)/sizeof(int);
pos[1] = (counter+1)/2;//中位数
pos[2] = counter;//最大值
for(int i = 0;i < 3;i++)
{
result = quicksort_nth_recursion(arr,counter,pos[i]-1);
printf("---------- The No.%d result is %d ----------\n",pos[i],result);
}
printf("------------------------------------------------------------\n");
int arr2[1<<16];
srand(38838);
for(int i=0;i < 1<<16;i++)
{
arr2[i] = rand();
}
counter = sizeof(arr2)/sizeof(int);
pos[1] = (counter+1)/2;
pos[2] = counter;
for(int i = 0;i < 3;i++)
{
result = quicksort_nth_recursion(arr2,counter,pos[i]-1);
printf("---------- The No.%d result is %d ----------\n",pos[i],result);
}
}
运行输出
helloworld@DESKTOP-BRAEUTR /d/yunpan/Work/Z-SRC/sort
$ /d/tmp/test.exe
---------- The No.1 result is 1 ----------
---------- The No.9 result is 50 ----------
---------- The No.17 result is 500 ----------
------------------------------------------------------------
---------- The No.1 result is 0 ----------
---------- The No.32768 result is 16541 ----------
---------- The No.65536 result is 32767 ----------
网站题目:数据库实现原理#2(获取第N个值)
网页地址:http://scyanting.com/article/pdjeed.html