找出未排序整数数组的中位数

题目- 中位数 #

给定一个未排序的整数数组，找到其中位数。

中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第 N/2 个数。

示例 #

给出数组[4, 5, 1, 2, 3]， 返回 3

给出数组[7, 9, 4, 5]，返回 5

分析 #

简单的思路就是先排序，然后根据中位数规则取中位数

想想，能不能不排序直接取中位数？或者排序的同时取中位数。

排序可以用哪些方法？ 参考：常见排序算法的时间复杂度,空间复杂度

Just Try #

请你自动动手试一下：在线编程环境

想想有没有其他思路？

想想时间和空间复杂度，能否优化一下

真的做不到么？

let you think， think makes you happy!

参考答案 #

选择排序的实现如下：

function algorithm(arr){
  let  k=0;
  for(let i=0; i< Math.ceil(arr.length/2); i++){
    for(let j=i+1; j< arr.length; j++){
      if(arr[i] > arr[j]){
        k = arr[j]
        arr[j] = arr[i]
        arr[i] = k
      }
    }
  }
  if(arr.length%2==0)
    return arr[arr.length/2-1]
  if(arr.length%2==1)
    return arr[Math.floor(arr.length/2)]
}
function main(param) {
  console.show("参数：" + param, "结果：" + algorithm(param))
  console.show(testPerformance(algorithm, param))
}
main([4, 5, 1, 2, 3])
main([7, 9, 4, 5])

这种双重循环的代码唯一的缺点就是时间复杂度高，只是外层循环减少了一半而已，时间复杂度o(n/2*log(n))，应该有更好的办法来做

请你自动动手试一下：在线编程环境

冒泡排序 #

function algorithm(arr){
  let  k=0;
  for(let i=0; i< Math.ceil(arr.length/2); i++){
    for(let j=0; j< arr.length-i; j++){
      if(arr[j] > arr[j+1]){
        k = arr[j+1]
        arr[j+1] = arr[j]
        arr[j] = k
      }
    }
  }
  if(arr.length%2==0)
    return arr[arr.length/2-1]
  if(arr.length%2==1)
    return arr[Math.floor(arr.length/2)]
}

快速排序 #

快速排序的思想和中位数的概念有类似，参考快排

function algorithm(arr){
  if(arr.length <= 1) return arr
  let j = arr[0]
  let tmp = [[],[],[j]];
  arr.forEach((k,i)=>{
    if(k>j){
      tmp[1].push(k)
    }
    if(k<j){
      tmp[0].push(k)
    }
   if(k==j && i!=0){
      tmp[2].push(k)
    }
  })
  return algorithm(tmp[0]).concat(tmp[2]).concat(algorithm(tmp[1]))
}
function main(param) {
  console.show("参数：" + param, "结果：" + JSON.stringify(algorithm(param)))
  testPerformance(algorithm, param)
}
main([5,1,2,3,4,5,9,8,3,8]);