Selection algorithm
选择问题即第k小元素问题。
解决该问题的基本思想与快速排序算法相同，通过选择基元进行划分，从而知道第k小元素在哪里。
原始数据使用随机函数生成。
采用结构化程序设计，可以很容易改为从标准输入或文件读入数据，只需要修改函数getData即可。
数据个数由宏定义给出，也可以轻松地改为输入。
算法有递归与非递归两种过程，非递归过程是正解。
/* * 问题描述：从N个数中，选出第k小（排序后排在第k个位置）的元素。 * * 选择问题法程序 * */#include#include #include #define N 7void getData(int [], int);void result_output(int []);int selectmink1(int a[], int low, int high, int k);int selectmink2(int a[], int low, int high, int k);int split(int a[], int low, int high);int main(void){ int a[N], k, r; getData(a, N); /* 获得数据放入数组a中 */ printf("datas: \n"); result_output(a); scanf("%d", &k); if(k >= 0 && k <= N-1) { r = selectmink1(a, 0, N - 1, k); printf("result=%d\n", r); r = selectmink2(a, 0, N - 1, k); printf("result=%d\n", r); } else printf("input error: k=%d\n", k); return 0;}int selectmink1(int a[], int low, int high, int k){ int middle; middle = split(a, low, high); if(middle == k) return a[k]; else if(middle < k) return selectmink1(a, middle+1, high, k); else /* if(middle > k) */ return selectmink1(a, low, middle-1, k);}int selectmink2(int a[], int low, int high, int k){ int middle; for(;;) { middle = split(a, low, high); if(middle == k) return a[k]; else if(middle < k) low = middle+1; else /* if(middle > k) */ high = middle-1; }}int split(int a[], int low, int high){ int part_element = a[low]; for (;;) { while (low < high && part_element <= a[high]) high--; if (low >= high) break; a[low++] = a[high]; while (low < high && a[low] <= part_element) low++; if (low >= high) break; a[high--] = a[low]; } a[high] = part_element; return high;}void getData(int d[], int n){ time_t t; srand((unsigned) time(&t)); /* 设置随机数起始值 */ int i; for(i=0; i < n; i++) d[i] = rand() % 100; /* 获得0-99之间的整数值 */}void result_output(int a[]){ int i; for (i = 0; i < N; i++) printf("%d ", a[i]); printf("\n");}
关键代码（正解）：
// 非递归选择问题算法程序int selectmink2(int a[], int low, int high, int k){ int middle; for(;;) { middle = split(a, low, high); if(middle == k) return a[k]; else if(middle < k) low = middle+1; else /* if(middle > k) */ high = middle-1; }}