求解顺序统计量的7种方法

求解顺序统计量的7种方法 四.最坏情况为线性的选择算法（基于优化主元选择方法）

       在“三”中，我们讨论了一种基于随机主元选取的划分方法求解顺序统计量，但是该方法仍然具有一定的局限性和不稳定性，尽管是随机，但在遇到大数据、大样本处理时，很有可能因为运气不够好，划分的还是不够均匀，而导致算法所需要的时间复杂度过高。

        与其将这种随机性交给计算机来执行，不如在程序书写阶段就将其消灭在摇篮中，这也许就是一个优秀程序猿的职责（但还是改变不了我水平一般的事实）。

        《算法导论》中提出了一种以数组的中位数的中位数的中位数......一直递归查找中位数的方法选择该划分，部分原文如下：        

        将数组中的元素5个为一组（7个也可以，3个也可以，但时间复杂度却值得商榷），求取每一组中五个元素的中位数 ，即第3个元素（下标为2）。每次都可能出现不能整除的情况，因此要考虑剩下的不完整数组中的中位数情况，书中取的是较小的中位数（偶数情况）。

        这样递归求解，每次55分组，就可以很好地将整个数组的中位数求解出来，每次定位求解出的中位数在原数组中的位置，就可以得到相应的划分位置，沿该位置划分，其余 *** 作（比较K和P的大小和递归左右数组）和原随机法求解类似，不再赘述。这样得到的时间复杂度就是线性的，具体证明过程使用的是《算法导论》第四章4.3中讲解的《利用主方法求解递归式》，证明起来不难，只要知道一定会有至少3n/10-6个元素大于主元就可以，详情见《算法导论》。

        具体C语言代码如下：

#include 
#include 
#include 

//在线性时间复杂度情况下定位数组中第k个元素
int LinearOrderCount(int *array, int left, int right, int i);

//对选择出的主元递归调用返回主元
int FindPivot(int *array, int left, int right);

//定位主元
int LocatePivot(const int *array, int left, int right, int pivot);

//线性时间复杂度的划分
int LinearDivide(int *array, int left, int right);

//交换元素
void swap(int *num1, int *num2);

//选择排序
void SelectSort(int *array, int size);


//测试函数
int main(int argc, char *argv[]) {
    int array[20];
    srand((unsigned int) time(NULL));

    for (int i = 0; i < 20; i++) {
        array[i] = rand() % 171;
    }
    //打印数组内容
    for (int i = 0; i < 20; i++) {
        printf("%d ", array[i]);
    }
    int i = 10;
    printf("n第 %d 大的元素为 %d ", i, LinearOrderCount(array, 0, 19, i));
    SelectSort(array, 20);
    putc('n', stdout);
    for (int i = 0; i < 20; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}


//查找array中的第k个元素
int LinearOrderCount(int *array, int left, int right, int i) {
    if (left >= right) {
        return array[left];//只有一个元素 直接返回 说明查找的就是该元素
    }
    int pivot = LinearDivide(array, left, right);//查找pivot
    int k = pivot - left + 1;//计算pivot含有多少个元素
    if (k == i) {
        return array[pivot];//查找的就是该元素
    }
        //尾递归
        //在该划分的左边
    else if (k > i) {
        //优化尾递归为迭代 减少递归栈的空间
        return LinearOrderCount(array, left, pivot - 1, i);//一直向左
    } else {
        return LinearOrderCount(array, pivot + 1, right, i - k);//寻找在右边数组中的第k个元素 则就是整个数组中的第 i-k + k = i个元素
    }
}


//利用查找到的主元进行线性划分 处理数组
int LinearDivide(int *array, int left, int right) {

    int Pivot = FindPivot(array, left, right);
    int site = LocatePivot(array, left, right, Pivot);
    if (site == -1) {
        printf("The pivot is not exists.n");
    }
    swap(&array[site], &array[right]);//交换right和site的位置
    int pivot = array[right];
    //划分pivot左右两边的数据
    int i = left - 1, j = left;//令i为left-1开始 可以避免极端情况
    for (; j < right; j++) {
        //如果小于左元则和i交换 令i+1处永远都是大于主元的数据
        if (array[j] < pivot) {
            i++;
            swap(&array[j], &array[i]);
        }
    }

    swap(&array[i + 1], &array[right]);//不能直接拿pivot交换 而要改变right的数据
    return i + 1;//i+1则是pivot所在的位置
}






//在进行主元的划分与查找时 由于array是整个大数组 而应该使用left、right计算出的绝对下标进行拷贝
//而在查找主元的主元的时候就没有这样的要求了
//这是这个算法里最大的一个坑


//查找主元
int FindPivot(int *array, int left, int right) {
    int size = right - left + 1;
    int n = size / 5;
    int *MiddleArray = (int *) malloc(sizeof(int) * (n + 1));
    int MiddleSize = n + 1;
    int buf[5];
    //完整的组
    for (int i = 0; i < n; i++) {
        for (int k = i * 5 + left; k < 5 + i * 5 + left; k++) {
            //!!!!注意这里拷贝的内容一定是原数组的内容 不能是相对下标 而是绝对下标
            buf[k - i * 5 - left] = array[k];//利用临时数组计算
        }
        SelectSort(buf, 5);
        MiddleArray[i] = buf[2];//第三个数据 下标为2 选取5个数据的中位数
    }
    //解决不完全的组
    int count = 0;
    for (int i = n * 5 - 1; i < size; i++) {
        //!!!!注意这里拷贝的内容一定是原数组的内容 不能是相对下标 而是绝对下标
        buf[count++] = array[i + left];
    }
    SelectSort(buf, count);
    if (count != 0) {
        MiddleArray[n] = buf[(count - 1) / 2];
    } else {
        MiddleSize--;//没有该组
    }
    if (n == 0) {
        return MiddleArray[n];
    } else {
        return FindPivot(MiddleArray, 0, MiddleSize - 1);
    }
}



//定位主元要注意定位的是在left和right区间中的绝对位置 而不是仅仅是在这个区间的相对位置

int LocatePivot(const int *array, int left, int right, int pivot) {
    for (int i = left; i <= right; i++) {
        if (array[i] == pivot) {
            return i;
        }
    }
    return -1;//查找失败
}


void SelectSort(int *array, int size) {
    for (int i = 0; i < size; i++) {
        int min = array[i];
        int min_site = i;
        int j;
        for (j = i; j < size; j++) {
            if (array[j] < min) {
                min = array[j];//记录最小元素
                min_site = j;//记录最小元素的下标
            }
        }
        //交换两者元素完成选择排序 改进则为堆排序
        array[min_site] = array[i];
        array[i] = min;
    }
}


//交换两个元素
void swap(int *num1, int *num2) {
    int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

        尽管算法思想很简单，但是要真正把代码写出来，还是需要一点功夫的。关键就在于对主元的中位数递归查找过程中产生的绝对下标和相对下标问题，第一次查找中位数，将数据按照原始数组中的绝对值下标拷贝到相对下标的buf临时数组中，而接下来的递归调用就无需关心了。因为要保证查找的主元一定是在left到right规定的范围内，不能越界，否则划分就不具有任何意义，还会导致程序出错。 

         程序运行结果如下：

        感谢大家的指正！