本文主要是介绍快速排序（单边、双边两种），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
无论是单边快排还是双边快排都需要注意以下一些关键点：
1.快排核心在于递归。
2.每回都需要选择一个基准元素，将该基准元素放置正确位置，并且将比其小的元素统统移到该位置左边，比其大的元素移到该元素右边。
3.防置完毕后需要拿到基准元素的位置，再分别对左右两边调用该方法进行递归。
双边快排：
1.1.需要注意边界问题，两个指针移动时也要判断i<j。
1.2.需要注意最后ij重合的位置，需要考虑这个位置和基准元素的大小关系，因为都有可能。
package mainimport "fmt"// 双边快排
func quickSort(arr []int, left int, right int) {if left < right {pos := partition(arr, left, right)quickSort(arr, left, pos-1)quickSort(arr, pos+1, right)}
}func partition(arr []int, left int, right int) int {i := leftj := rightpivot := arr[left]for i < j {for i < j && arr[i] <= pivot {i++}for i < j && arr[j] > pivot {j--}//i==j，或者真的需要交换，交换即可swap(arr, i, j)}pos := iif arr[pos] > pivot {pos--swap(arr, left, pos)} else {swap(arr, left, pos)}return pos
}func swap(arr []int, i int, j int) {if i != j {temp := arr[i]arr[i] = arr[j]arr[j] = temp}
}//func main() {
// arr := make([]int, 5)
// arr[0] = 2
// arr[1] = 1
// arr[2] = 4
// arr[3] = 3
// arr[4] = 5
// fmt.Println(arr)
// quickSort(arr, 0, len(arr)-1)
// fmt.Println(arr)
//}func main() {arr := make([]int, 8)arr[0] = 2arr[1] = 3arr[2] = 1arr[3] = 4arr[4] = 9arr[5] = 8arr[6] = 7arr[7] = 5fmt.Println(arr)quickSort(arr, 0, len(arr)-1)fmt.Println(arr)
}单边快排：
2.1.需要额外注意，基准元素只能先选最后一个位置，因为在遍历过程中，第一个元素（位置较小的元素）有可能与其他比基准元素小的元素发生交换，最后想把基准元素放到应该的位置上时，却发现基准元素被换到未知地方去了
2.2.基准元素自身位置不需遍历 ，最后pointer指向的位置一定是大于基准元素的（如果有的话，否则是基准元素自身），因为比基准元素小的都移动到比pointer低的位置了，交换即可。没有的话pointer也会指向基准元素自身，交换与否无影响。
package mainimport ("fmt"
)// 单边快排
func quickSort(arr []int, low int, high int) {if low < high {pos := partition(arr, low, high)quickSort(arr, low, pos-1)quickSort(arr, pos+1, high)}
}// 返回基准元素的position,并将基准元素放在正确位置
func partition(arr []int, low int, high int) int {//基准元素取最高，防止基准元素交换位置被交换的未知位置pivot := arr[high]pointer := low//<high,high不用遍历for i := low; i < high; i++ {if arr[i] <= pivot {//swaptemp := arr[i]arr[i] = arr[pointer]arr[pointer] = temp//指针后移pointer++}}//基准元素一到正确位置上temp := arr[pointer]arr[pointer] = arr[high]arr[high] = tempreturn pointer
}func main() {arr := make([]int, 5)arr[0] = 2arr[1] = 1arr[2] = 4arr[3] = 3arr[4] = 5fmt.Println(arr)quickSort(arr, 0, len(arr)-1)fmt.Println(arr)
}这篇关于快速排序（单边、双边两种）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
