首页 > 代码库 > 顺序统计量（选择问题）
顺序统计量（选择问题）
顺序统计量（选择问题）
定义
在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素，例如，在一个元素集合中，最小值是第一个顺序统计量（i = 1），最大值是第n个顺序统计量（i = n）。
查找最小值
在一个有n个元素的集合中，需要做多少次比较才能确定其最小元素呢？一个简单的思路就是：依次遍历集合中的每个元素，并记录当前最小的元素，在下面的排序中，假设该集合元素存放在数组A中，且A.length = n。
MINIMUM(A)
min = A[1]
for i = 2 to A.length
if min < A[i]
min = A[i]
return min
当然，最大值也可以进行n-1次比较找出来
同时找到最大最小值
最简单的方法就是分别独立地找出最大值和最小值，这各需要n-1次比较，共需要2n – 2次比较，事实上，只需要最多3*floor(n/2)（floor()函数是向下取整的意思）次比较就可以同时找出最大最小值。具体方法是记录已知的最大最小值，但并不是将每一个输入元素与当前的最小值和最大值进行比较—这样做的代价是每个元素都需要2次比较，而是对输入元素成对地进行处理，首先，将一对输入元素相互进行比较，然后把较小的元素与当前最小值进行比较，把较大的值与当前最大值进行比较，这样，两个元素一共需要3次比较。
如何设定已知的最大值和最小值依赖于n是奇数还是偶数，如果n是奇数，就将最小值和最大值的初值设置为第一个元素的值，然后成对地处理余下的元素。如果n是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后与n是奇数的情况一样，成对地处理余下的元素。
如果n是奇数，那么共进行3*（n-1）/2次比较，如果n是偶数，则先进行一次初始比较，然后进行3(n-2)/2次比较，共进行3n/2-2次比较，因此，不管哪一种情况，总的比较次数至多是3*floor(n/2)次。
期望为线性时间的选择算法
一般选择问题看起来要比找出最小值这样的问题更难，但是，这两个问题的渐近运行时间却是相同的：θ(n)。下面是一种解决选择问题的分治算法，与快速排序一样，将输入数组进行递归划分，但与快速排序算法不同的是，快速排序会递归处理划分的两边，而RANDOMIZED_SELECT只处理划分的一边，快速排序的期望运行时间为θ(nlgn)，而RANDOMIZED_SELECT的期望运行时间为θ(n)，这里，假设输入数据都是互异的。
伪代码
//i是要选择的第几个最大值，k则是通过分区后得到该主元为第几个最大值
RANDOMIZED_SELECT(A, p, r, i)
if p == r
return A[p]
q = RANDOMIZED_PARTITION(A, p, r);
k = q - p + 1
if k == i
return A[q]
else if i < k
return RANDOMINZE_SELECT(A, p, q-1, i)
else
return RANDOMIZED_SELECT(A, q+1, r, i - k)
性能分析
RANDOMIZED_SELECT的最坏情况运行时间为θ(n2)，即使是找最小元素也是如此，因为在每次划分时可能极不走远地总是按余下元素中最大的进行划分，而划分操作需要θ(n)时间，但是该算法是随机划分的，所以不存在一个特定的会导致出现最坏情况的输入数据。
该算法的期望运行时间为θ(n)，具体证明参考《算法导论》P121
C语言代码实现
#include<stdio.h>#include<stdlib.h>#include<time.h> void randomized_select(int *array, int begin, int end, int position);int randomized_partion(int *array, int begin, int end);int partion(int *array, int begin, int end);void swap(int *array, int p, int q);void quicksort(int *array, int begin, int end); main(){ int array[]={23,3,35,5,7,28,34,45,73,21,9,33,64}; int i, k; printf("排序前的数组：\n"); for (i = 0; i < 13; i++) printf("%d\t",array[i]); putchar(‘\n‘); putchar(‘\n‘); quicksort(array, 0, 11); printf("排好序的数组：\n"); for (i = 0; i < 13; i++) printf("%d\t",array[i]); for(k = 1; k <= 13; k++){ putchar(‘\n‘); printf("\n由小到大排序，排在第%d位的数为: ",k); randomized_select(array, 0, 12, k); } putchar(‘\n‘);} void swap(int *array, int p, int q){ int temp; temp = array[p]; array[p] = array[q]; array[q] = temp;} int randomized_partion(int *array, int begin, int end){ //temp是一个随机数，用来选择主元的位置 int piviot_position, temp; srand((unsigned int) time(NULL));//srand函数用参数值对随机数发生器进行初始化，此处使用当天的当前时间作为随机数产生器的种子 temp = rand() % (end - begin ); piviot_position = temp + begin; swap(array, begin, piviot_position); return partion(array, begin, end);} int partion(int *array, int begin, int end){ //选择第一个元素作为主元 int piviot; int last, ptr; piviot = array[begin]; for (last = begin, ptr = begin + 1; ptr <= end; ptr++){ if (array[ptr] <= piviot){ swap(array, ++last, ptr); } } swap(array, last, begin); return last;} void randomized_select(int *array, int begin, int end, int position){ //number的值就是主元在排好序的数组中的位置 int piviot_position; int number; if (begin == end){ printf("%d\n", array[begin]); return; } piviot_position = randomized_partion(array, begin, end); number = piviot_position - begin + 1; if (number == position) printf("%d\n", array[piviot_position]); else if (position < number) randomized_select(array, begin, piviot_position-1, position); else randomized_select(array, piviot_position+1, end, position - number);} void quicksort(int *array, int begin, int end){ int medium; if (begin < end){ medium = partion(array, begin, end); quicksort(array, begin, medium-1); quicksort(array, medium+1, end); }}