求无序数组的中位数(c语言版本)

逃离我推掉我的手 2022-03-01 12:24 260阅读 0赞

在面试时，会经常被问道，如何求解一个无序数组的中位数？很多人往往都会第一感觉就是，先将该数组排序，然后找出最中间的那个数，但是这种思路通常的时间复杂度最好是O(nlogn)，更糟的情况下会到O(n^2)，并不是最优解，也就不能impressed面试官了。下面我们聊聊这个话题。

何为中位数？

中位数，就是数组排序后位于数组最中间位置的那个元素。当然，细分析的话，还要区分该数组的长度，如果该数组长度为n，若n为奇数，则中位数就是(n+1)/2位置上的数；若n为偶数，则中位数是n/2和n/2+1位置上的两个数的平均值，这里我们为了简单起见，就用n/2位置上的数代替吧。

现在我们考虑一个更一般的问题：

如何求解一个无序数组的第k小的数？

如果能求解出第k小的数，那么就能求出第k大的数(它对应第(n-k)+1小的数)，特别地，如果k为n/2或(n+1)/2的话，这就是我们要求的中位数。

关于这个问题，我发现在Allen Weiss的《数据结构与算法分析》一书中一直贯穿始终，特别是在第七章排序中，给出了时间复杂度为O(n)的解决方法，该解决方法，也就是一个"二分法"思想的快速排序思想的变体，但是比快速排序的实现更快更简单，因为它只需要对牵涉范围的那些子数组排序。

下面是我的源码实现，以作备忘。

//description: 查找无序数组中指定的第k小的数
    //date: 2019-03-21
    
    #include <stdio.h>
    #include <stdlib.h>
    
    void swap(int arr[], int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
    
    void quick_select(int arr[], int k, int s, int e){
        if(s > e || k < s || k > e){
            printf("invalid array range\n");
            return;
        }
    
        //这里随机将左边第一个元素设置为基准点
        int i, j, pivot = arr[s];
        if(s <= e){
            i = s;
            j = e;
            for(;;){
                while(arr[j] >= pivot && i<j){j--;}
                while(arr[i] <= pivot && i<j){i++;}
                if(i<j)
                    swap(arr, i, j);
                else
                    break;
            }
            //恢复pivot
            swap(arr, i, s);
    
            //继续进行下一轮迭代
            if(k<=i)
                quick_select(arr, k, s, i-1);
            else if(k>=i+1)
                quick_select(arr, k, i+1, e);
        }
    }
    
    //数组复制
    void copy_array(int arr[], const int barr[], int n){
        int i = 0;
        for(i=0; i<n; i++)
            arr[i] = barr[i];
    }
    
    int main(int argc, char** argv){
        int a[] = {12,4,3,67,900,22,28,9,61,53,23,12};
        int n = sizeof(a) / sizeof(int);
        int k = 4;
    
        int b[n];
        copy_array(b, a, n);
        int m = n%2==0 ? n/2 : (n+1)/2;
    
        //求第k小的数
        quick_select(a, k, 0, n-1);
        printf("the %d-th smallest number: %d\n", k, a[k-1]);
    
        for(int i=0; i<n; i++)
            printf("%d ", a[i]);
        printf("\n");
    
        //求解中位数
        quick_select(b, m, 0, n-1);
        printf("the median nuber(%d-th): %d\n", m, b[m-1]);
    
        for(int i=0; i<n; i++)
            printf("%d ", b[i]);
        printf("\n");
    
        return 0;
    }

这里给出了求解第4小和第6小的数的排序，因为数组长度为12，我就把6当做是该数组的中位数了。

运行截图如下：

![20190322160426533.png][]

[20190322160426533.png]: /images/20220301/7ef6631813d840a1948c8ac1081ae66f.png