获取数组中的第N个值,仍使用代码说明,算法参考快速排序的思想,详见代码注释.

#include <stdio.h>#include <stdlib.h>#include <string.h>#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 ----------