1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| func quickSort(arr []int) { _quickSort(arr, 0, len(arr)-1) }
func _quickSort(arr []int, left, right int) { if left < right { pivot := partition(arr, left, right) _quickSort(arr, left, pivot-1) _quickSort(arr, pivot+1, right) } }
func partition(arr []int, left, right int) int { i, j, pivot := left, right, arr[left] for { for i < j && arr[j] > pivot { j-- }
for i < j && arr[i] <= pivot { i++ }
if i < j { arr[i], arr[j] = arr[j], arr[i] } else { break } }
arr[i], arr[left] = arr[left], arr[i] return i }
|