| 5 | ) |
| 6 | |
| 7 | func RSelect(arr []int, n, i int) int { |
| 8 | pivot := rand.Intn(n) |
| 9 | v := arr[pivot] |
| 10 | left := 0 |
| 11 | |
| 12 | arr[pivot], arr[n-1] = arr[n-1], arr[pivot] |
| 13 | |
| 14 | for j := 0; j < n-1; j++ { |
| 15 | if arr[j] <= v { |
| 16 | arr[j], arr[left] = arr[left], arr[j] |
| 17 | left++ |
| 18 | } |
| 19 | } |
| 20 | |
| 21 | if left+1 >= n { |
| 22 | return arr[n-1] |
| 23 | } |
| 24 | |
| 25 | arr[left+1], arr[n-1] = arr[n-1], arr[left+1] |
| 26 | |
| 27 | j := left |
| 28 | |
| 29 | if j < 2 { |
| 30 | return arr[j] |
| 31 | } |
| 32 | |
| 33 | if j == i { |
| 34 | return arr[j] |
| 35 | } else if j > i { |
| 36 | return RSelect(arr[:j], j-1, i) |
| 37 | } else { |
| 38 | return RSelect(arr[j:], n-j, i-j) |
| 39 | } |
| 40 | } |