【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++的效率非常的高。