【AcWing】快速排序的Go实现
快速排序的Go实现
这一部分参考了AcWing当中使用Go语言实现快速排序的题解：https://www.acwing.com/activity/content/code/content/296206/。
其中有很多部分非常值得参考，故写一个博客进行记录。
Code
package main
import "fmt"
func quick_sort(q []int, l, r int) {
if l >= r {
return
}
x := q[l+(r-l)/2]
i, j := l-1, r+1
for i < j {
for i++; q[i] < x; i++ {
}
for j--; q[j] > x; j-- {
}
if i < j {
q[i], q[j] = q[j], q[i]
}
}
quick_sort(q, l, j)
quick_sort(q, j+1, r)
}
func main() {
var n int
fmt.Scanf("%d", &n)
q := make([]int, n+5)
for i := 1; i <= n; i++ {
fmt.Scanf("%d", &q[i])
}
quick_sort(q, 1, n)
for i := 1; i <= n; i++ {
fmt.Printf("%d ", q[i])
}
return
}
- 首先，对于大部分只需要标准输入输出的算法题，只需要导入
fmt包即可，fmt可以完成标准的输入输出。使用fmt.Scanf("%d", &n)完成数组长度n的输入，使用fmt.scanf("%d, &q[i])来完成数组当中元素的输入。 - 其次，在创建长度为
n的数组时，可以使用Go当中的make方法，第一个参数是类型，即int[]，而第二个参数是长度，由于我使用的下标从1开始，因此此处创建数组的长度比n稍大，避免越界。 - 使用
fmt.Prinf("%d", q[i])完成数组的遍历输出。 - 在quick_sort部分，可以看到
i, j := l-1, r+1、q[i], q[j] = q[j], q[i]这样的语句，Go语言可以像Python那样一次为多个变量进行赋值，其中q[i], q[j] = q[j], q[i]直接完成了C++当中的swap操作。 for i++; q[i] < x; i++ {}操作直接等价于C++当中的do{i ++;} while(q[i] < x)，注意Go语言当中没有do... while...的用法，可以使用上述for循环进行替代，Go语言中只有for一种循环语句，但是它是非常灵活的。- 在快速排序选取哨兵结点时，必须使用
x := q[l+(r-l)/2]，否则会报错。 - 需要注意的是，在AcWing的OJ中，Go语言实现的快排执行时间来到了4900+ms，而C++版本实现的快排仅需要100+ms，差距非常大，说明C++的效率非常的高。