Commit6dda558

committed

add code

1 parent8a79009 commit6dda558Copy full SHA for 6dda558

File tree

+81

-1

lines changed

+81

-1

lines changed

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -77,7 +77,7 @@`
`77`	`77`
`78`	`78`	`##面试资源`
`79`	`79`
`80`		`-另外面试还看了大概 100 本书，强烈推荐 🌝`
	`80`	`+分享一些计算机的经典书籍，大部分对面试应该都有帮助，强烈推荐 🌝`
`81`	`81`
`82`	`82`	`[我看过的 100 本书](https://github.com/greyireland/awesome-programming-books-1)`
`83`	`83`

Lines changed: 7 additions & 0 deletions

Lines changed: 47 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,47 @@`
	`1`	`+package sort`
	`2`	`+`
	`3`	`+funcHeapSort(a []int) []int {`
	`4`	`+// 1、无序数组a`
	`5`	`+// 2、将无序数组a构建为一个大根堆`
	`6`	`+fori:=len(a)/2-1;i>=0;i-- {`
	`7`	`+sink(a,i,len(a))`
	`8`	`+}`
	`9`	`+// 3、交换a[0]和a[len(a)-1]`
	`10`	`+// 4、然后把前面这段数组继续下沉保持堆结构，如此循环即可`
	`11`	`+fori:=len(a)-1;i>=1;i-- {`
	`12`	`+// 从后往前填充值`
	`13`	`+swap(a,0,i)`
	`14`	`+// 前面的长度也减一`
	`15`	`+sink(a,0,i)`
	`16`	`+}`
	`17`	`+returna`
	`18`	`+}`
	`19`	`+funcsink(a []int,iint,lengthint) {`
	`20`	`+for {`
	`21`	`+// 左节点索引(从0开始，所以左节点为i*2+1)`
	`22`	`+l:=i*2+1`
	`23`	`+// 有节点索引`
	`24`	`+r:=i*2+2`
	`25`	`+// idx保存根、左、右三者之间较大值的索引`
	`26`	`+idx:=i`
	`27`	`+// 存在左节点，左节点值较大，则取左节点`
	`28`	`+ifl<length&&a[l]>a[idx] {`
	`29`	`+idx=l`
	`30`	`+}`
	`31`	`+// 存在有节点，且值较大，取右节点`
	`32`	`+ifr<length&&a[r]>a[idx] {`
	`33`	`+idx=r`
	`34`	`+}`
	`35`	`+// 如果根节点较大，则不用下沉`
	`36`	`+ifidx==i {`
	`37`	`+break`
	`38`	`+}`
	`39`	`+// 如果根节点较小，则交换值，并继续下沉`
	`40`	`+swap(a,i,idx)`
	`41`	`+// 继续下沉idx节点`
	`42`	`+i=idx`
	`43`	`+}`
	`44`	`+}`
	`45`	`+funcswap(a []int,i,jint) {`
	`46`	`+a[i],a[j]=a[j],a[i]`
	`47`	`+}`

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,26 @@`
	`1`	`+package sort`
	`2`	`+`
	`3`	`+import (`
	`4`	`+"reflect"`
	`5`	`+"testing"`
	`6`	`+)`
	`7`	`+`
	`8`	`+funcTestHeapSort(t*testing.T) {`
	`9`	`+typeargsstruct {`
	`10`	`+a []int`
	`11`	`+}`
	`12`	`+tests:= []struct {`
	`13`	`+namestring`
	`14`	`+argsargs`
	`15`	`+want []int`
	`16`	`+}{`
	`17`	`+{"",args{a: []int{7,8,9,2,3,5}}, []int{2,3,5,7,8,9}},`
	`18`	`+}`
	`19`	`+for_,tt:=rangetests {`
	`20`	`+t.Run(tt.name,func(t*testing.T) {`
	`21`	`+ifgot:=HeapSort(tt.args.a);!reflect.DeepEqual(got,tt.want) {`
	`22`	`+t.Errorf("HeapSort() = %v, want %v",got,tt.want)`
	`23`	`+}`
	`24`	`+})`
	`25`	`+}`
	`26`	`+}`

Comments

(0)