\u4e0a\u4ee3\u7801\uff0c\u5199\u4e86\u4e2a\u901f\u5ea6\u6bd4\u8f83\u7a0b\u5e8f\u6765\u719f\u6089\u719f\u6089golang<\/p>\n\n\n\n
package main\n\nimport \"fmt\"\nimport \"math\/rand\"\nimport \"sort\"\nimport \"time\"\nimport \"reflect\"\nimport \"runtime\"\n\nfunc merge(nums []int, mid int){\n\t\/\/fmt.Println(\"merge been called\")\n\t\/\/print_slice(nums)\n\tlength := len(nums)\n\tp1 := 0\n\tp2 := mid\n\tp := 0\n\ttmp := make([]int,length)\n\tfor p1<mid&&p2<length {\n\t\tif nums[p1]<nums[p2] {\n\t\t\ttmp[p] = nums[p1]\n\t\t\tp1++\n\t\t\tp++\n\t\t}else {\n\t\t\ttmp[p] = nums[p2]\n\t\t\tp2++\n\t\t\tp++\n\t\t}\n\t}\n\tfor p1<mid {\n\t\ttmp[p] = nums[p1]\n\t\tp1++\n\t\tp++\n\t}\n\tfor p2<length {\n\t\ttmp[p] = nums[p2]\n\t\tp2++\n\t\tp++\n\t}\n\t\/\/fmt.Printf(\"p=%v p1=%v p2=%v mid=%v length=%v\\n\",p,p1,p2,mid,length)\n\t\/\/fmt.Print(\"nums:\")\n\t\/\/print_slice(nums)\n\t\/\/fmt.Print(\"tmp:\")\n\t\/\/print_slice(tmp)\n\tcopy(nums,tmp)\n\t\n\t\/\/fmt.Println(\"merge done\")\n}\n\nfunc merge_sort_normal(nums []int){\n\tlength := len(nums)\n\tif length==1 {\n\t\treturn\n\t}\n\tmid := length\/2\n\tmerge_sort_normal(nums[:mid])\n\tmerge_sort_normal(nums[mid:])\n\tmerge(nums,mid)\n}\n\nfunc print_slice(nums []int){\n\tfmt.Print(\"[\")\n\tfor _,x:=range nums {\n\t\tfmt.Printf(\"%v \",x)\n\t}\n\tfmt.Printf(\"] len=%v cap=%v\\n\",len(nums),cap(nums))\n}\n\nfunc merge_sort_parallel_recursion(nums []int,c chan bool){\n\t\/\/print_slice(nums)\n\tlength := len(nums)\n\tif length==1 {\n\t\tc<-true\n\t\treturn\n\t}\n\tmid := length\/2\n\tnc := make(chan bool)\n\tgo merge_sort_parallel_recursion(nums[:mid],nc)\n\tgo merge_sort_parallel_recursion(nums[mid:],nc)\n\t<-nc\n\t<-nc\n\tmerge(nums,mid)\n\tc<-true\n}\n\nfunc merge_sort_parallel(nums []int){\n\tc := make(chan bool)\n\tgo merge_sort_parallel_recursion(nums,c)\n\t<-c\n}\n\nfunc quick_sort_normal(nums []int){\n\n\tlength := len(nums)\n\tif length<=1 {\n\t\treturn\n\t}\n\t\/\/fmt.Println(\"enter\")\n\t\/\/print_slice(nums)\n\tval := nums[0]\n\tp1 := 0\n\tp2 := length-1\n\tt := 0\n\tfor p1<=p2 {\n\t\tfor ;p1<=p2;p2-- {\n\t\t\tif nums[p2]<val {\n\t\t\t\tbreak\n\t\t\t}\n\t\t}\n\t\tif p1<=p2 {\n\t\t\tnums[p1] = nums[p2]\n\t\t\tt = p2\n\t\t\t\/\/p1++\n\t\t}\n\t\tfor ;p1<=p2;p1++ {\n\t\t\tif nums[p1]>val {\n\t\t\t\tbreak\n\t\t\t}\n\t\t}\n\t\tif p1<=p2 {\n\t\t\tnums[p2] = nums[p1]\n\t\t\tt = p1\n\t\t\t\/\/p2--\n\t\t}\n\t}\n\tnums[t] = val\n\t\/\/print_slice(nums)\n\t\/\/fmt.Printf(\"p1=%v p2=%v\\n\",p1,p2)\n\tquick_sort_normal(nums[:t])\n\tquick_sort_normal(nums[t+1:])\n\t\/\/fmt.Println(\"done\")\n}\n\n\nfunc quick_sort_parallel_recursion(nums []int, c chan bool){\n\t\/\/print_slice(nums)\n\tlength := len(nums)\n\tif length<=1 {\n\t\tc<-true\n\t\treturn\n\t}\n\tval := nums[0]\n\tp1 := 0\n\tp2 := length-1\n\tt := 0\n\tfor p1<=p2 {\n\t\tfor ;p1<=p2;p2-- {\n\t\t\tif nums[p2]<val {\n\t\t\t\tbreak\n\t\t\t}\n\t\t}\n\t\tif p2>=p1 {\n\t\t\t\/\/fmt.Printf(\"nums[%v] = nums[%v]\\n\",p1,p2)\n\t\t\tnums[p1] = nums[p2]\n\t\t\tt = p2\n\t\t\t\/\/p1++\n\t\t}\n\t\tfor ;p1<=p2;p1++ {\n\t\t\tif nums[p1]>val {\n\t\t\t\tbreak\n\t\t\t}\n\t\t}\n\t\tif p1<=p2 {\n\t\t\t\/\/fmt.Printf(\"nums[%v] = nums[%v]\\n\",p2,p1)\n\t\t\tnums[p2] = nums[p1]\n\t\t\tt = p1\n\t\t\t\/\/p2--\n\t\t}\n\t}\n\tnums[t] = val\n\n\tnc := make(chan bool)\n\tgo quick_sort_parallel_recursion(nums[:t],nc)\n\tgo quick_sort_parallel_recursion(nums[t+1:],nc)\n\t\/*\n\tif p2>=0{\n\t\tgo quick_sort_parallel_recursion(nums[:p2],nc)\n\t}else{\n\t\tgo quick_sort_parallel_recursion([]int{},nc)\n\t}\n\t\n\tif p2+1<length{\n\t\tgo quick_sort_parallel_recursion(nums[p2+1:],nc)\n\t}else{\n\t\tgo quick_sort_parallel_recursion([]int{},nc)\n\t}\n\t*\/\n\t\n\t<-nc\n\t<-nc\n\tc<-true\n}\n\n\nfunc quick_sort_parallel(nums []int){\n\tc := make(chan bool)\n\tgo quick_sort_parallel_recursion(nums,c)\n\t<-c\n}\n\n\nfunc main(){\n\tnum := 1000000\n\tv := make([]int, num)\n\tfor i:=0;i<num;i++ {\n\t\tv[i] = rand.Intn(num)\n\t}\n\n\tbaseline := make([]int,num)\n\tcopy(baseline,v)\n\tsort.Ints(baseline)\n\n\tfuncs := []func([]int){sort.Ints,merge_sort_normal,merge_sort_parallel,quick_sort_normal,quick_sort_parallel}\n\n\tfor i,f := range funcs{\n\t\ttmp := make([]int,num)\n\t\tcopy(tmp,v)\n\t\tstart_time := time.Now()\n\t\tf(tmp)\n\t\ttime_elapsed := time.Since(start_time)\n\t\tcorrect := true\n\t\tfor j:=0;j<num;j++{\n\t\t\tif baseline[j]!=tmp[j]{\n\t\t\t\tcorrect = false\n\t\t\t\tbreak\n\t\t\t}\n\t\t}\n\t\tname := runtime.FuncForPC(reflect.ValueOf(f).Pointer()).Name() \n\t\tfmt.Printf(\"%v\\t%-50v%15v\\t%v\\n\",i,name,time_elapsed,correct)\n\t}\n}<\/code><\/pre>\n\n\n\n\u5728\u6211\u7535\u8111\u4e0a\u7684\u8fd0\u884c\u7ed3\u679c\u4e3a<\/p>\n\n\n\n
0 sort.Ints 155.7437ms true\n1 main.merge_sort_normal 117.5517ms true\n2 main.merge_sort_parallel 419.6172ms true\n3 main.quick_sort_normal 73.3922ms true\n4 main.quick_sort_parallel 120.0331ms true<\/code><\/pre>\n\n\n\n\u8fd8\u662f\u633a\u51fa\u4e4e\u6211\u610f\u6599\u7684\uff0c\u4e00\u4e2a\u662f\u6ca1\u60f3\u5230\u5feb\u6392\u53ef\u4ee5\u505a\u5230\u6bd4\u5185\u7f6e\u7684sort.Ints\u8981\u5feb\u3002\u53e6\u4e00\u4e2a\u6ca1\u60f3\u5230\u5e76\u884c\u7248\u672c\u6bd4\u914d\u666e\u901a\u7248\u672c\u8981\u6162\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e0a\u4ee3\u7801\uff0c\u5199\u4e86\u4e2a\u901f\u5ea6\u6bd4\u8f83\u7a0b\u5e8f\u6765\u719f\u6089\u719f\u6089golang \u5728\u6211\u7535\u8111\u4e0a\u7684\u8fd0\u884c\u7ed3\u679c\u4e3a \u8fd8\u662f\u633a\u51fa\u4e4e\u6211\u610f\u6599\u7684\uff0c\u4e00\u4e2a\u662f… \u7ee7\u7eed\u9605\u8bfb go\u8bed\u8a00\u5f52\u5e76\u6392\u5e8f\u548c\u5feb\u6392\u901f\u5ea6\u7684\u6d4b\u8bd5<\/span><\/i><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":{"0":"post-198","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"hentry","6":"category-uncategorized","7":"h-entry","9":"h-as-article"},"_links":{"self":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts\/198","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=198"}],"version-history":[{"count":2,"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts\/198\/revisions"}],"predecessor-version":[{"id":200,"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts\/198\/revisions\/200"}],"wp:attachment":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=198"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=198"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=198"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}