Golang TDD实践报告：快速排序Quick Sort

古城微笑少年丶 2022-12-08 15:56 109阅读 0赞

### Golang TDD实践报告：快速排序Quick Sort 【阅读时间：约5分钟】 ###

*  0.项目需求
 *  1.编写符合项目输入输出的一个测试
 *  2.尝试运行测试
 *  3.先使用最少的代码来让失败的测试先跑起来
 *  4.编写足够的代码以使测试通过
 *  5.重构编写完整的代码以提高效率
 *  6.基准测试

> TDD是测试驱动开发（Test-Driven Development）的英文简称，是敏捷开发中的一项核心实践和技术，也是一种设计方法论。  
> TDD设计周期如下（假设项目需求已知）：
> 
> > ①编写符合项目输入输出的一个测试  
> > ②尝试运行测试  
> > ③先使用最少的代码来让失败的测试先跑起来  
> > ④编写足够的代码以使测试通过  
> > ⑤重构编写完整的代码以提高效率  
> > ⑥基准测试

在之前的C/C++编程中学习了许多有用的算法，比如排序算法。  
最近笔者在入门Golang的开发应用，在掌握基本语法后感觉还是缺少了些东西，于是想尝试通过TDD设计风格来逐步实现一个常用的排序算法——快速排序（Quick Sort）算法。

# 0.项目需求 #

项目需求：设计一个名为QuickSort的函数，实现快速排序算法。  
用法：给定一个长度（如L=10）的整数数组，调用QuickSort函数将其排序为数值从小到大的数组。

# 1.编写符合项目输入输出的一个测试 #

创建文件夹quicksort，将其作为项目目录。  
在 QuickSort\_test.go 中：

package quicksort
    
    import "testing"
    
    func TestQuickSort(t *testing.T) { 
    	arr0 := []int{ 1, 9, 2, 8, 3, 7, 4, 6, 5, 0}
    	arr1 := []int{ 1, 9, 2, 8, 3, 7, 4, 6, 5, 0}
    
    	got := QuickSort(arr1, 0, 9)
    	want := []int{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
    
    	for i := 0; i < 10; i++ { 
    		if got[i] != want[i] { 
    			t.Errorf("\n got %v\n want %v\n given %v", got, want, arr0)
    			break
    		}
    	}
    }

也上面的迭代可以改为更为简洁的形式，导入import "reflect"并使用reflect.DeepEqual(got, want)比较即可：

package quicksort
    
    import (
    	"reflect"
    	"testing"
    )
    
    func TestQuickSort(t *testing.T) { 
    	arr0 := []int{ 1, 9, 2, 8, 3, 7, 4, 6, 5, 0}
    	arr1 := []int{ 1, 9, 2, 8, 3, 7, 4, 6, 5, 0}
    
    	got := QuickSort(arr1, 0, 9)
    	want := []int{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
    
    	if !reflect.DeepEqual(got, want) { 
    		t.Errorf("\n got %v\n want %v\n given %v", got, want, arr0)
    	}
    }

# 2.尝试运行测试 #

在项目目录下，使用go test指令运行测试，报错信息如下：

[henryhzy@localhost quicksort]$ go test
    # github.com/user/quicksort [github.com/user/quicksort.test]
    ./QuickSort_test.go:9:2: undefined: QuickSort
    FAIL	github.com/user/quicksort [build failed]

# 3.先使用最少的代码来让失败的测试先跑起来 #

在 QuickSort.go 中：

package quicksort
    
    func QuickSort(arr []int, l, r int) ([]int){ 
        return arr
    }

再次在项目目录下，使用go test指令运行测试，报错信息如下：

[henryhzy@localhost quicksort]$ go test
    --- FAIL: TestQuickSort (0.00s)
        QuickSort_test.go:14: 
             got [1 9 2 8 3 7 4 6 5 0]
             want [0 1 2 3 4 5 6 7 8 9]
             given [1 9 2 8 3 7 4 6 5 0]
    FAIL
    exit status 1
    FAIL	github.com/user/quicksort	0.002s

# 4.编写足够的代码以使测试通过 #

在 QuickSort.go 中：

package quicksort
    
    func QuickSort(arr []int, l, r int) []int { 
    	Sort(arr, l, r)
    	return arr
    }
    
    func Sort(arr []int, l, r int) { 
    	if l >= r { 
    		return
    	}
    
    	i := Partition(arr, l, r)
    	Sort(arr, l, i-1)
    	Sort(arr, i+1, r)
    }
    
    func Partition(arr []int, l, r int) int { 
    	i, j, key := l, r, arr[l]
    
    	for i < j { 
    		for i < j && arr[j] > key { 
    			j--
    		}
    		arr[i] = arr[j]
    
    		for i < j && arr[i] < key { 
    			i++
    		}
    		arr[j] = arr[i]
    	}
    
    	arr[i] = key
    	return i
    }

在项目目录下，使用go test指令运行测试，提示正确的信息如下：

[henryhzy@localhost quicksort]$ go test
    PASS
    ok  	github.com/user/quicksort	0.002s

# 5.重构编写完整的代码以提高效率 #

考虑到每次递归调用Sort函数时，每个Sort函数都需要调用一次Partition函数，而事实上Partition函数可以融合到Sort函数中，从而减少函数调用的时间，提高了代码的运行效率。

在 QuickSort.go 中：

package quicksort
    
    func QuickSort(arr []int, l, r int) []int { 
    	Sort(arr, l, r)
    	return arr
    }
    
    func Sort(arr []int, l, r int) { 
    	if l >= r { 
    		return
    	}
    
    	i, j, key := l, r, arr[l]
    
    	for i < j { 
    		for i < j && arr[j] > key { 
    			j--
    		}
    		if i<j { 
    			arr[i] = arr[j]
    			i++
    		}
    		
    		for i < j && arr[i] < key { 
    			i++
    		}
    		if i<j { 
    			arr[j] = arr[i]
    			j--
    		}
    	}
    
    	arr[i] = key
    	Sort(arr, l, i-1)
    	Sort(arr, i+1, r)
    }

在项目目录下，使用go test指令运行测试，提示正确的信息如下：

[henryhzy@localhost quicksort]$ go test
    PASS
    ok  	github.com/user/quicksort	0.002s

# 6.基准测试 #

func BenchmarkQuickSort(b *testing.B) { 
    	arr:= [10]int{ 1, 9, 2, 8, 3, 7, 4, 6, 5, 0}
        for i := 0; i < b.N; i++ { 
            QuickSort(arr, 0, 9)
        }
    }

在项目目录下，使用“go test -bench=.”指令运行基准测试，其结果如下：

[henryhzy@localhost quicksort]$ go test -bench=.
    goos: linux
    goarch: amd64
    pkg: github.com/user/quicksort
    BenchmarkQuickSort 	 8373924	       162 ns/op
    PASS
    ok  	github.com/user/quicksort	1.505s