需求规划

  • 目标

开发一个排序算法的比较程序

  • 调用方式

从命令行指定输入的数据文件和输出的数据文件，并指定对应的排序算法。

  • 主要功能
  1. 获取并解析命令行输入
  2. 从对应文件中读取输入数据
  3. 调用对应的排序函数
  4. 将排序的结果输出到对应的文件中
  5. 打印排序所花费时间的信息
  • 程序结构

sorter 为项目根目录，其下包括 3 个文件夹 src, pkg, bin。

src 文件夹下存放程序的源码。

主程序是 sorter.go 。快速排序用 qsort.go 实现，冒泡排序用 bubblesort.go 实现。

代码实现

实现的过程根据程序结构分为主程序和 2 个排序算法。

主程序

主程序中主要实现的功能包括 3 个：

  • 命令行参数的解析
  • 读取输入文件
  • 写入输出文件

命令行参数的解析

flag 是用于快速解析命令行参数的包。

package mainimport ("flag""fmt")var infile *string = flag.String("i", "infile", "File contains values for sorting")var outfile *string = flag.String("o", "outfile", "File to receive sorted values")var algorithm *string = flag.String("a", "qsort", "Sort algorithm")func main()  {flag.Parse()if infile != nil {fmt.Println("infile =", *infile, "outfile =", *outfile, "algorithm =", *algorithm)}}

go run：go run 编译并直接运行程序，它会产生一个临时文件(但不会生成 .exe 文件)，直接在命令行输出程序执行结果，方便用户调试。

go build：go build 用于测试编译包，主要检查是否会有编译错误，如果是一个可执行文件的源码(即是 main 包)，就会直接生成一个可执行文件。

go install：go install 的作用有两步：第一步是编译导入的包文件，所有导入的包文件编译完才会编译主程序；第二步是将编译后生成的可执行文件放到 bin 目录下($GOPATH/bin)，编译后的包文件放到 pkg 目录下($GOPATH/pkg)。

因为本程序需要输入参数，所以不能直接用 go run 来跑，而是需要先编译出二进制程序。可以用 go build 来完成这个过程：

go build sorter.go

此时，会在同文件夹下生成一个 sorter 的可执行文件。通过运行该可执行文件来检验程序状态。

./sorter -i unsorted.dat -o sorted.dat -a bubblesort infile = unsorted.dat outfile = sorted.dat algorithm = bubblesort

读取输入文件

接着需要先从一个文件中把包含的内容读取到数组中，因此需要涉及如何操作文件。

输入文件的格式这里定义为纯文本文件，每一行是一个需要被排序的数字。

1233064364490

需要实现：

  • 逐行读取内容
  • 解析 int 类型数据
  • 添加到一个 int 类型的数组切片中
func readValues(infile string)(values []int, err error) {file, err := os.Open(infile) // 打开文件if err != nil {fmt.Println("Failed to open the input file ", infile)return}defer file.Close() // 确保使用结束后关闭文件br := bufio.NewReader(file) // 开始读文件values = make([]int, 0) // 创建数组切片for {line, isPrefix, err1 := br.ReadLine() // 逐行读取if err1 != nil { // 文件终止检查if err1 != io.EOF {err = err1}break}if isPrefix {fmt.Println("A too long line, seems unexpected.")return}str := string(line) // 转换字符数组为字符串value, err1 := strconv.Atoi(str) // 把字符串转为整型if err1 != nil {err = err1return }values = append(values, value) // 向数组切片中追加新读入的数字}return }

读文件涉及到的标准库包括了：

  • bufio : “实现缓冲的I/O”
  • io : 它实现了一系列非平台相关的 IO 相关接口和实现，比如提供了对 os 系统相关的 IO 功能的封装。在进行流式读写时，会用到。
  • os：提供了对操作系统功能的非平台相关访问接口。提供的功能包括文件操作、进程管理等。
  • strconv：字符串与基本数据类型互转的能力。

写入输出文件

数据处理结束后，将排序结果输出到另一个文本文件。

func writeValues(values []int, outfile string) error {file, err := os.Create(outfile) // 创建写入文件if err != nil {fmt.Println("Failed to create the output file", outfile)return err}defer file.Close() // 即时关闭文件for _, value := range values { // 遍历数组切片的元素str := strconv.Itoa(value) // 把整型变为字符串file.WriteString(str + "") //每行回车}return nil}

排序算法实现

2 个排序算法分别在 qsort.go 和 bubblesort.go 中实现。

bubblesort.go

package bubblesortfunc BubbleSort(values []int)  {flag := truefor i := 0; i < len(values)-1; i++  {flag = truefor j := 0; j < len(values)-i-1; j++ {if values[j] > values[j + 1] {values[j], values[j+1] = values[j+1], values[j]flag = false}}if flag == true {break}}}

在实现模块时，同时配以单元测试文件。

bubblesort_test.go

package bubblesortimport "testing"func TestBubbleSort1(t *testing.T) {values := []int{5, 4, 3, 2, 1}BubbleSort(values)if values[0] != 1 || values[1] != 2 || values[2] != 3 || values[3] != 4 || values[4] != 5 {t.Error("BubbleSort() failed. Got", values, "Expected 1 2 3 4 5")}}func TestBubbleSort2(t *testing.T) {values := []int{5, 5, 3, 2, 1}BubbleSort(values)if values[0] != 1 || values[1] != 2 || values[2] != 3 || values[3] != 5 || values[4] != 5 {t.Error("BubbleSort() failed. Got", values, "Expected 1 2 3 5 5")}}func TestBubbleSort3(t *testing.T) {values := []int{5}BubbleSort(values)if values[0] != 5 {t.Error("BubbleSort() failed. Got", values, "Expected 5")}}

qsort.go

文件形式结构与 bubblesort 相同

package qsortfunc quickSort(values []int, left, right int){temp := values[left]p := lefti, j := left, rightfor i <= j {for j >= p && values[j] >= temp {j--}if j >= p {values[p] = values[j]p = j}if values[i] <= temp && i <= p {i++}if i <= p {values[p] = values[i]p = i}}values[p] = tempif p - left > 1 {quickSort(values, left, p-1)}if right - p > 1 {quickSort(values, p+1, right)}}func QuickSort(values []int)  {quickSort(values, 0, len(values)-1)}

qsort_test.go

package qsortimport "testing"func TestQuickSort1(t *testing.T) {values := []int{5, 4, 3, 2, 1}QuickSort(values)if values[0] != 1 || values[1] != 2 || values[2] != 3 || values[3] != 4 || values[4] != 5 {t.Error("QuickSort() failed. Got", values, "Expected 1 2 3 4 5")}}func TestQuickSort2(t *testing.T) {values := []int{5, 5, 3, 2, 1}QuickSort(values)if values[0] != 1 || values[1] != 2 || values[2] != 3 || values[3] != 5 || values[4] != 5 {t.Error("QuickSort() failed. Got", values, "Expected 1 2 3 5 5")}}func TestQuickSort3(t *testing.T) {values := []int{5}QuickSort(values)if values[0] != 5 {t.Error("QuickSort() failed. Got", values, "Expected 5")}}

模块组合到主程序中

import ("awesomeProject/src/algorithms/bubblesort""awesomeProject/src/algorithms/qsort"  )values, err := readValues(*infile)if err == nil {t1 := time.Now()switch *algorithm {case "qsort":qsort.QuickSort(values)case "bubblesort":bubblesort.BubbleSort(values)default:fmt.Println("Sorting algorithm", *algorithm, "is either unknown or unsupported.")}t2 := time.Now()fmt.Println("The sorting process costs", t2.Sub(t1), "to complete.")writeValues(values, *outfile)} else {fmt.Println(err)}

需要在源码中操作的内容全部完成。

构建与执行

构建过程分为 4 个部分：

  • 设置好 GOPATH
  • go build
  • go test
  • go install
echo $GOPATH// 测试编译包，主要检查是否会有编译错误go build algorithm/qsortgo build algorithm/bubblesort// 对模块进行单元测试go test algorithm/qsortgo test algorithm/bubblesort// 编译导入的包文件，将编译后生成的可执行文件放到 bin 目录下($GOPATH/bin)，编译后的包文件放到 pkg 目录下($GOPATH/pkg)。go install algorithm/qsortgo install algorithm/bubblesort// 测试编译包,可执行文件的源码(即是 main 包)，就会直接生成一个可执行文件，在当前文件夹。go build sorter// 编译导入的包文件，将编译后生成的可执行文件放到 bin 目录下($GOPATH/bin)go install sorter

一切顺利，可以在 src 的同一级目录下看到 2 个目录 bin 和 pkg，其中：

  • pkg 目录下放的是 bubblesort.a 和 qsort.a
  • bin 目录下放置的是 sorter 的二进制可执行文件

因为 sorter 接受的是一个文件格式的输入，所以需要准备这样的一个文件。

可以在 sorter 所在的 bin 目录内创建一个 unsorted.dat 文本文件，格式同前面示范的文本。结果文件 sorted.dat 会由程序自动创建，因此不需要事先创建。

执行

cd binlscat unsorted.dat./sorter -i unsorted.dat -o sorted.dat -a qsort infile = unsorted.dat outfile = sorted.dat algorithm = qsort./sorter -i unsorted.dat -o sorted.dat -a bubblesort infile = unsorted.dat outfile = sorted.dat algorithm = bubblesortcat sorted.dat

通过上面的代码执行，可以看到正确排序的结果，程序完整开发完成。