中位数

#include<stdio.h>

#define maxn 1000

int a[maxn];

// 快速排序函数
void quickSort(int l, int r) {
  if (l >= r) {   // 递归结束条件：区间只有一个元素或区间为空
    return;
  }
  int i = l, j = r, pivot = a[l]; // 定义左右指针和枢轴元素
  while (i < j) { // 左右指针相遇时退出循环
    while (i < j &&
           a[j] >= pivot) {    // 右指针向左移动，找到第一个小于枢轴元素的元素
      j--;
    }
    a[i] = a[j];    // 将该元素赋值给左指针所在位置
    while (i < j &&
           a[i] <= pivot) {    // 左指针向右移动，找到第一个大于枢轴元素的元素
      i++;
    }
    a[j] = a[i];    // 将该元素赋值给右指针所在位置
  }
  a[i] = pivot;   // 将枢轴元素放到最终正确的位置上
  quickSort(l, i - 1);    // 对左半部分区间递归进行快排
  quickSort(i + 1, r);    // 对右半部分区间递归进行快排
}

int main() {
  int n, x, i;
  scanf("%d%d", &n, &x);  // 输入数组长度和要插入的元素
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]); // 输入原始数组
  }

  quickSort(0, n - 1);    // 对原始数组进行排序

  int cnt = 0;    // 记录插入次数
  while (a[(n - 1) / 2] !=
         x) {   // 当中位数不等于要插入的元素时循环
    if (a[(n - 1) / 2] > x) {  // 如果中位数大于要插入的元素
      for (int k = n; k > (n + 1) / 2;
           k--) { // 将中位数及其右边的元素全部向右移动一位
        a[k] = a[k - 1];
      }
      a[(n + 1) / 2] = x;    // 将要插入的元素放到新的中间位置
    } else {    // 如果中位数小于要插入的元素
      for (int k = n; k >= (n + 1) / 2;
           k--) {    // 将中位数及其右边的元素全部向右移动一位
        a[k] = a[k - 1];
      }
      a[(n - 1) / 2] = x;    // 将要插入的元素放到新的中间位置
    }
    cnt++;  // 插入次数加1
    n++;    // 数组长度加1
    quickSort(0, n - 1);    // 对新的数组进行排序
  }

  printf("%d\n", cnt);

  return 0;
}