golang实现线性查找算法（BFPRT）

func BFPRT(arr []int, idx int) int {
   remain := arr
   for {
      medians := remain
      for {
         var temp []int
         for i:=0;i<len(medians);i+=5 {
            up := i+5
            if up > len(medians) {
               up = len(medians)
            }
            quicksort(medians[i:up])
            temp = append(temp, medians[i+(up-i-1)/2])
         }
         medians = temp
         if len(medians) == 1 {
            break
         }
      }

      p := swap(remain, medians[0])

      if p+1 == idx || len(remain) == 1 {
         return medians[0]
      } else if p+1 > idx {
         remain = remain[:p+1]
      } else {
         idx -= p + 1
         remain = remain[p+1:]
      }
   }
}

func quicksort(arr []int) {
   if len(arr) <= 1 {
      return
   }
   p := swap(arr, arr[0])
   arr[0], arr[p] = arr[p], arr[0]
   if p >=len(arr) -1{
      p = len(arr) - 2
   }
   quicksort(arr[:p+1])
   quicksort(arr[p+1:])
}

func swap(arr []int, p int) int {
   i, j := 0, len(arr) - 1
   for i<=j {
      if arr[i] <= p {
         i++
      } else {
            arr[i], arr[j] = arr[j], arr[i]
            j--
      }
   }
   return j
}

如果有bug欢迎评论区指出批评。谢谢！

golang实现线性查找算法（BFPRT）

原文：https://www.cnblogs.com/lianghucheng/p/15098189.html