任给一组数字(整数), 如何快速求得中间值.

zerozero_nine

首先想到是排序后取中间值, 有没有更好的算法?
从快速排序的结构看, 应该可以在不用完全排序便可求得中间值.

cellar

中间值是什么意思啊？
比如
1 2 3 4，那中间值是几啊？2.5吗？

yuxh

基于快速排序的不完全排序实现

1. #include <time.h>;
   
2. 
   
3. void swap(int *ary, int i, int j)
   
4. {
   
5.     int t;
   
6.     t = ary[i]; ary[i] = ary[j]; ary[j] = t;
   
7. }
   
8. 
   
9. int middle(int *ary, int num)
   
10. {
    
11.     int low, high, elem, begin, end;
    
12. 
    
13.     begin = 0; end = num;
    
14.     while( begin < end ) {
    
15.         elem = ary[begin];
    
16.         low = begin;
    
17.         high = end;
    
18.         while(ary[++low] < elem && low < high);
    
19.         while(ary[--high] >; elem && high >;= low);
    
20.         while(low < high) {
    
21.             swap(ary, low, high);
    
22.             while(ary[++low] < elem && low < high);
    
23.             while(ary[--high] >; elem && high >;= low);
    
24.         }
    
25.         swap(ary, begin, high);
    
26. 
    
27.         if(high >; num / 2)
    
28.             end = high;
    
29.         else if(high < num / 2)
    
30.             begin = high + 1;
    
31.         else
    
32.             break;
    
33.     }
    
34. 
    
35.     return ary[high];
    
36. }
    
37. 
    
38. int main(int argc, char *argv[])
    
39. {
    
40.     int i, ary[100], num, result;
    
41. 
    
42.     num = atoi(argv[1]);
    
43.     srand(time(NULL));
    
44.     printf("Arry :");
    
45.     for(i = 0; i < num; i++) {
    
46.        ary[i] = rand() % 100;
    
47.        printf("%d  ", ary[i]);
    
48.     }
    
49.     printf("\n");
    
50. 
    
51.     result = middle(ary, num);
    
52. 
    
53.     printf("Last Arry :");
    
54.     for(i = 0; i < num; i++)
    
55.        printf("%d  ", ary[i]);
    
56.     printf("\n");
    
57. 
    
58.     printf("Result :%d\n", result);
    
59. }
    

复制代码

zerozero_nine

谢谢yuxh.
比如说, 快速排序第一次二分后, 如二分的轴已经接近中位, 会不会作一两次选择排序, 便求得中位值? 有没有相关的算法?

yuxh

一次二分以后，就算接近中位，但不是中位，也没法很快得到中位值的，只能说中位值在某个半区中(那个半区中的数都没排序，你知道哪个是中位值？)

zerozero_nine

如果只差一个位便到中位, 只需在较多的一组中选最大值或最小值便是, 但以上是很理想的情形.

yuxh

你的想法是错误的，和最大最小值没有关系

zerozero_nine

Quick sort 找了一次 pivot 后, pivot 的一边总比另一边大, 中间值必在较多的那边, 如果pivot的位置接近中位附近, 只需在较多的那边求几次最大值或最小值便已找到中间值.

yuxh

如偏移中间n个数，那就要找第n个大(小)的数，这个开销是不确定的。。。