BFPRT算法-Golang

这个BFPRT算法找逻辑Bug找了两天

注意点:

  1. 在找中位数的时候对传入的数组进行排序,这里使用直接插入排序,因为元素个数最多为5,插排常数项极低
    1. 注意:这里不是nums[j] > nums[i]而是for j = i - 1; j >= start && nums[j] > temp; j--,因为后面会对nums[i]造成修改
  2. 找中位数数组的中位数medianOfMedians返回的是最终的中位数的值,我们使用这个值进行Partition,自己这里还一直将其当做返回的索引用,导致越界
  3. BFPRT函数调用自己的时候,参数一定要对应,自己在写的时候直接将k传入了start