package main import ( "fmt" "math/rand" "sort" "time" ) // 从小到大 func Order(arr []int, left, right int) { if left >= right { return } // 以 pivot 为轴，分别将小于、大于 pivot 的元素放在左右两边 leftIndex, rightIndex, pivot := left, right, arr[(left+right)/2] for leftIndex < rightIndex { // 从左边开始向右找一个大于等于 pivot 的元素 // 最差到 pivot 时跳出，且每次循环会重新选定 pivot，即必然会循环到 pivot，故无需 判断 leftIndex <= right for /*leftIndex < right &&*/ arr[leftIndex] < pivot { leftIndex++ } // 从右边向左找一个小于等于 pivot 的元素 for /*rightIndex > left &&*/ arr[rightIndex] > pivot { rightIndex-- } // 左侧的均已小于 pivot 且 右侧的均已大于 pivot 时跳出 if leftIndex >= rightIndex { break } // 避免元素值相等导致死循环 if arr[leftIndex] == arr[rightIndex] { leftIndex++ continue } // 交换这两个元素 arr[leftIndex], arr[rightIndex] = arr[rightIndex], arr[leftIndex] // fmt.Println(leftIndex, rightIndex, arr) } // 左边 Order(arr, left, rightIndex-1) // 右边 Order(arr, leftIndex+1, right) } func main() { rand.Seed(time.Now().UnixNano()) testData1 := make([]int, 0, 100000000) times := 100000000 for i := 0; i < times; i++ { val := rand.Intn(20000000) testData1 = append(testData1, val) } // arr := []int{9, 3, 5, 1, 6, 0, 2, 7, 4, 8} // arr := []int{9, 9, 9, 9, 9, 9, 9, 9, 9, 9} // Order(&arr, 0, len(arr)-1) // fmt.Println(arr) start := time.Now() Order(testData1, 0, len(testData1)-1) fmt.Println("single goroutine: ", time.Now().Sub(start)) if !sort.IntsAreSorted(testData1) { fmt.Println("wrong quick_sort implementation") } }