6-11 求自定类型元素序列的中位数

字数统计: 1.3k字  | 阅读时长:约 5 分钟
总阅读量次


一道题把排序算法复习了个遍😂，最终复习到了堆排序。快到碗里来👇。

题面

原题链接(要不先去做一下？😏)，题面如下，

本题要求实现一个函数，求N个集合元素A[]的中位数，即序列中第⌊N/2+1⌋大的元素。其中集合元素的类型为自定义的ElementType。
函数接口定义：
ElementType Median( ElementType A[], int N );
其中给定集合元素存放在数组A[]中，正整数N是数组元素个数。该函数须返回N个A[]元素的中位数，其值也必须是ElementType类型。
裁判测试程序样例：

#include <stdio.h>
#define MAXN 10
typedef float ElementType;
ElementType Median( ElementType A[], int N );
int main ()
{
    ElementType A[MAXN];
    int N, i;
    scanf("%d", &N);
    for ( i=0; i<N; i++ )
        scanf("%f", &A[i]);
    printf("%.2f\n", Median(A, N));
    return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
3
12.3 34 -5
输出样例：
12.30

分析

　　首先，因为题目给定中位数位置为序列中第⌊N/2+1⌋大，所以不用考虑序列长度为奇为偶。
　　其次，因为涉及到排序，而又不能直接调用库里面的排序算法，so,就自己手写排序代码。

  • 第一次尝试冒泡排序😀，最后一组数据，大N超时🤔

    (PS:强迫症表示很难受。)

  • 第二次快速排序，结果如上上上，给的数据是反快速排序的😓

  • 第三次堆排序，AC😉😆
    **具体代码请转移至我的Github**。

下面复习(反正review和preview有个p的区别😏)一下堆排序

　　堆是一种数据结构，它是一颗完全二叉树，并且具备以下性质:

  • 每个节点的值都大于或等于其左右子节点，称为大顶堆;
  • 每个节点的值都小于或等于其左右子节点，称为小顶堆。

比如小顶堆

将之映射成数组V，有如下:

则对于数组有，索引为i的节点：
$ V[i]\leq V[2 \ast i+1]且 V[i] \leq V[2 \ast i+2]$ (1)(对于小顶堆)

堆排序算法描述如下:

  1. 将无序序列构造成小顶堆(最终数组为非严格降序排列，大顶堆反之)，如上图。
    • 具体构造过程如下:
    • 对每个根节点进行判定，如果其不满足小顶堆定义，则交换元素，直至满足**$(1)$**
  2. 将第一个元素与最后一个元素交换，将最小元素下沉到数组最后，调整堆结构，使其满足定义。
  3. 反复执行2过程，直到数组有序。

代码实现

C++代码实现：

void HeapAdjust(ElementType A[], int x, int len)
{
    ElementType temp = A[x];        // 保存根节点x
    // 从x节点的左子节点开始
    for(int j = 2 * x + 1; j < len; j = 2 * j + 1)    
    {
        if(j + 1 < len && A[j] > A[j + 1])    // ，滑向值小的节点
            j++;
        if(temp < A[j])            // 如果当前根节点小于子节点，则跳出循环
            break;
        A[x] = A[j];            // 子节点覆盖根节点
        x = j;                    // 此时子节点j变成根节点
    }
    A[x] = temp;                // 将x节点放在最终位置
}
ElementType HeapSort( ElementType A[], int N )
{
    // 构建初始堆，从第一个非叶子节点自底向上调整堆
    for(int i = N / 2 - 1; i >= 0; i--)
    {
        HeapAdjust(A, i, N);
    }
    // 堆调整、交换元素
    for(int i = N - 1; i > 0; i--)
    {
        // 元素下沉操作    
        ElementType temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        // 调整整个堆
        HeapAdjust(A, 0, i);
    }
}

时间复杂度

初始化堆

　　因为初始化堆是自底向上的，从最后一个非叶子节点开始调整堆(叶子节点不用调整😅)。可证明完全二叉树的最后一个非叶子节点的编号为$n/2-1$（$n$表示堆的元素总数量），这样从下至上，从右至左调整堆。
假设在第i层，二叉树高度为K,该层的节点数为**$2^{i-1}$,调整该层需要的比较次数为$k-i$**,
最后一个非叶子节点所在层数为$k-1$,则i的区间为$[1,k-1]$,每一层的比较次数:

$$s=2^{i-1}*(k-i)$$

所以初始化堆总的比较次数为：

$$　①　 S = \sum_{i=1}^{k-1}2^{i-1}\ast(k-i)$$

该等式两边$\ast$2，得：

$$　②　 2*S = \sum_{i=1}^{k-1}2^{i}\ast(k-i)$$

上两式$②　　-　①$ 得：

$$S = \sum_{i=1}^{k-1}2^{i} - (k-1)$$

由等比数列公式$\frac{a_{1}(q^{n}-1)}{q-1}$得

$$S = 2^{k}-k-1$$

k为二叉树的高度，$k=logn,2^{k}=2^{logn}=n$(对数恒等式),得到$S=n-logn-1$，所以初始化堆的时间复杂度为**$O(n)$**

调整堆

　　下沉元素时，每一次调整堆都是从根节点调整的，也就是从第1层到k-1层，比较次数$log(i)$,而一共要进行n-1次，所以总的比较次数$(n-1)logn$(可以参考一下https://www.programiz.com/dsa/heap-sort)，即$nlogn-logn$。所以调整堆的时间复杂度为**$O(nlogn)$**

空间复杂度

　　作为原地排序(原地排序指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序)的一员，其空间复杂度为$O(1)$。