After ten years of development, only this Java development system is left
>>> 
The principle of quick sorting will not be described in detail. The focus here is how to use coroutines to improve quick sorting. Speed:
Quick sort uses the idea of divide and conquer. Here the array/slice is divided into two parts. The left part is smaller than the sentinel and the right part is larger than the sentinel. Then the quick sort function is executed recursively. There is a very important point here. The factor is that if a coroutine is used to execute the recursive call, the left half of the array and the right half of the array are passed in as parameters respectively, so there is no need to consider data synchronization issues. The effect is like one coroutine calling 2, two coroutines calling 4, and 4 calling 8. The time complexity will be significantly reduced.
What is the difference between using thread quick sorting and using coroutine quick sorting? Due to system limitations, the creation of threads is limited. Once the array length is large, the speed will be significantly reduced, but coroutines will not , tested a 1 million random number array, and the sorting time was only about 10ms.
The test is as follows:
package main
import "math/rand"
import "fmt"
import "time"
func quickSort(values []int,left,right int){
temp:=values[left]
p:=left
i ,j:=left,right
for i<=j{
for j>=p && values[j]>=temp{
j--
}
if j>=p{
values[p]=values[j]
p=j
}
for i<=p && values[i]<=temp{
i++
}
if i<=p{
values[p]=values[i]
p=i
}
}
values [p]=temp
if p-left>1{
quickSort(values,left,p-1)
//go quickSort(values,left,p-1)
}
if right-p>1{
quickSort(values,p+1,right)
//go quickSort(values,p+1,right)
}
}
func QuickSort(values []int){
quickSort(values,0,len(values)-1)
}
func main(){
ceshi := make([]int,10000)
for i:=0 ; i<100; i++ {
ceshi[i]=rand.Intn(100)
}
start_time :=time.Now ()
QuickSort(ceshi)
end_time :=time.Since(start_time)
fmt.Println("after sort",ceshi)
fmt.Println("count time ",end_time)
}
The time when coroutine is used is about 1ms, and when coroutine is not used, it takes effect at 40ms. One thing that is not rigorous here is that the two times are different. random array, there will be a little difference, but it is an order of magnitude difference.
Conclusion, using coroutines for quick sorting can significantly improve the speed of quick sorting.
微信扫一扫打赏
支付宝扫一扫打赏
