package main import ( "fmt" ) func QuickSort(src []int, first, last int) { flag := first left := first right := last if first >= last { return } for first < last { //从最右边开始向前找比选取的标记值小的数字,然后进行交换,并记下标记值的新index for first < last { if src[last] >= src[flag] { last -= 1 continue } else { tmp := src[last] src[last] = src[flag] src[flag] = tmp flag = last break } } //从最左边开始向后查找比选取的标记值大的数字,然后进行交换,并记下标记值的新index for first < last { if src[first] <= src[flag] { first += 1 continue } else { tmp := src[first] src[first] = src[flag] src[flag] = tmp flag = first break } } } QuickSort(src, left, flag-1) QuickSort(src, flag+1, right) } func main() { src := []int{5, 8, 1, 7, 9, 5, 2, 3, 9, 12, 24} QuickSort(src, 0, len(src)-1) fmt.Println(src) }
快速排序是经典8大排序中比较常用的排序,时间复杂度为O(nlgn),且不用像merge sort一样,需要额外的空间,是一种原地排序。
有疑问加站长微信联系(非本文作者)
![](https://static.golangjob.cn/static/img/footer.png?imageView2/2/w/280)