中位数

　　　算法导论在第九章的9.3节中给出了一种最坏情况运行时间为O(n)的选择算法。该算法的基本思想是要保证对数组的划分是个好的划分。要达到这样的目的，我们就可以通过选择中位数来达到一个好的划分。

　　 (1)将所有的数n个以每5个划分为一组共组，将不足5个的那组忽略，然后用任意一种排序算法，因为只对5个数进行排序，所以任取一种排序法就可以了。将每组中的元素排好序再分别取每组的中位数，得到个中位数，把它们存储下来。

　　(2)取这个中位数的中位数，如果是偶数，就找它的2个中位数中较大的一个作为划分基准。（出自：风仲达）

　　　这样我们就可以得到中位数。然后可以把它应用到利用快排思想来求第K大数的算法中，就可以把那个算法的最坏运行时间变为O(n)。

中位数的代码：

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b)
{
    int tmp;
    tmp = *b;
    *b = *a;
    *a = tmp;
}

void inert_sort(int arr[], int left, int right)
{
    int i,j;
    for (i = left + 1; i <= right; i++)
    {
        int t = arr[i];
        j = i;
        while ((j > left) && (arr[j-1] > t))
        {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = t;
    }
}

int select_median(int arr[], int left, int right)
{
    int nTotal = right - left + 1;   //求总个数
    int nRemain = nTotal % 5;        //剩余那组的个数
    int nGroup = nTotal / 5;
    int i;

    int *median = (int *)malloc(sizeof(int)*(nGroup+1));  //用于存储[n/5]个中位数
    
    for (i = left; i <= right - nRemain; i+=5)
    {
        inert_sort(arr,i,i+4);
        median[i/5] = arr[i+2];   
    }
    inert_sort(arr,right-nRemain+1,right);
    median[i/5] = arr[right-nRemain+(nRemain+1)/2];
    
    inert_sort(median,0,nGroup-1);

    return median[(nGroup+1)/2-1];
}

int main()
{
    int arr[] ={9,10,6,8,12,3,2,11,20,13,16,12,18,17,16};
    int len = sizeof(arr)/sizeof(int);
    int i,nRet;

    //inert_sort(arr,0,len-1);

    nRet = select_median(arr,0,len-1);

    printf("median:%d
",nRet);
    for (i = 0; i < len; i++)
    {
        printf("%3d",arr[i]);
    }
    return 0;
}

2013/7/3 21:19