go|快速排序

每次都找一个枢纽(下面代码用数组的最后一个),将它放到正确的位置,再把这个枢纽位置的俩边进行递归。

func quickSort(arr []int, l, r int) { if l < r { mid := partionSort(arr, l, r) quickSort(arr, l, mid[0]-1) quickSort(arr, mid[0]+1, r) } }func partionSort(arr []int, l, r int) [2]int { // 快速排序 target := arr[r] less := l - 1 // 作为小区间 more := r + 1 // 作为大区间 index := l for index < more { if arr[index] < target { // 如果数比目标数小 less = less + 1 swap(arr, less, index) index = index + 1 } else if arr[index] > target { // 如果数是比目标数大 more = more - 1 swap(arr, more, index) } else { // 等于 index = index + 1 } } return [2]int{less + 1, more} }func swap(arr []int, l, r int) { // 交换数组中的俩个数 if l == r || l < 0 || r < 0 || l >= len(arr) || r >= len(arr) { return } arr[l], arr[r] = arr[r], arr[l] }

【go|快速排序】

    推荐阅读