golang实现并发快速排序

雨点打透心脏的1/2处 2022-11-29 14:28 134阅读 0赞

# 理论 #

[单线程快速排序][Link 1]

从“单线程快速排序” 中我们可以看到。快排可以分为三个步骤

1.  将当前待排序序列分割为三个部分：低于基准的，等于基准的，高于基准的
2.  然后分别对 低于基准的序列 排序、高于基准的序列 排序，一直重复1、2两个步骤，知道不能再次分割\[也就是只剩下一个元素或者两个元素\]
3.  将三个部分合并为一个，那就是有序的了

# 单线程 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]

# 多线程 #

## 版本1 ##

package main
    
    import (
    	"fmt"
    	"math/rand"
    	"sync"
    	"time"
    )
    
    func QuickSort(arr []int)[]int{
        
    	length := len(arr)
    	if(length <= 1){
        
    		return arr;
    	}else{
        
    		var wg sync.WaitGroup
    		rand.Seed(time.Now().UnixNano())
    		base := arr[rand.Intn(length)] // 随机基准
    		low := make([]int, 0)
    		mid := make([]int, 0)
    		high := make([]int, 0)
    
    		for i := 0; i < length ; i++ {
        
    			if arr[i] < base {
        
    				low = append(low, arr[i])
    			}else if arr[i] == base {
        
    				mid = append(mid, arr[i])
    			}else{
        
    				high = append(high, arr[i])
    			}
    		}
    
    		wg.Add(2)
    		go func() {
        
    			low = QuickSort(low)
    			wg.Done()
    		}()
    		go func() {
        
    			high = QuickSort(high)
    			wg.Done()
    		}()
    
    		wg.Wait()
    
    		return append(append(low, mid...), high...)
    	}
    }
    
    func main() {
        
    
    	data := []int{
        3, 6, 23, 7, 2, 4, 9, 13}
    	fmt.Println(QuickSort(data))
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]  
从上面我们可以看出，虽然我们可以对 low和high快排并行开始，但是我们必须要等待它们切割完成之后才能合并，那有没有改进的方法呢？----- 我们可以使用管道来存储切割结果。

## 版本2 ##

### 简化版 ###

假设待排序序列为\[3, 1, 2\]，选取第一个元素作为基准序列  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 3]  
比起版本1。虽然版本2在合并的时候，也是要先合并完low，然后合并mid，然后合并high。但是在合并low的时候可以一边排序一边合并  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 4]

package main
    
    import (
    	"fmt"
    	"math/rand"
    	"time"
    )
    
    // 没有必要返回chan，
    func QuickSort(arr []int, channel chan int){
        
    	length := len(arr)
    
    	if(length <= 0){
        
    		close(channel)
    		return ;
    	}else if(length <= 1){
        
    		channel <- arr[0]
    		close(channel)
    		return
    	}else{
        
    		low := make([]int, 0)
    		mid := make([]int, 0)
    		high := make([]int, 0)
    
    		rand.Seed(time.Now().Unix())
    		base := arr[rand.Intn(length)]
    
    		for i := 0; i < length ; i++ {
        
    			if arr[i] < base {
        
    				low = append(low, arr[i])
    			}else if arr[i] == base {
        
    				mid = append(mid, arr[i])
    			}else{
        
    				high = append(high, arr[i])
    			}
    		}
    
    
    		left_chan := make(chan int)
    		go func() {
        
    			QuickSort(low, left_chan);
    		}()
    
    		right_chan := make(chan int)
    		go func() {
        
    			QuickSort(high, right_chan)
    		}()
    
    		for v := range left_chan {
        
    			channel <- v
    		}
    
    		for _, v := range mid {
        
    			channel <- v
    		}
    
    		for v := range right_chan {
        
    			channel <- v
    		}
    
    		close(channel)
    		return
    	}
    }
    
    func main() {
        
    	data := []int{
        3, 6, 23, 7, 2, 4, 9, 13}
    	channel := make(chan int)
    	go QuickSort(data, channel)
    	for v := range channel {
        
    		fmt.Println(v)
    	}
    }

优化：从上面可以看到，每调用一层快排，线程数量\*2，如果要排序的数组长度很长，因为管道会一直阻塞，所以线程会一直等待它的子线程们调用到最底层才会结束，也就是说，如果排序序列很长，那么运行着的线程会是很恐怖的大，因此这个地方需要优化下

package main
    
    import (
    	"fmt"
    	"math/rand"
    	"time"
    )
    
    /**
     * 作用：并发排序
     * 参数：
     *   arr 待排序数组
     *   channel： 结果管道
     *   level：   当前层级
     *	 threads： 线程总数
     * 返回值： 无
    */
    func QuickSort(arr []int, channel chan int, level int, threads int){
        
    	level = level * 2;//每加深一个级，多*2个线程
    	length := len(arr)
    
    	if(length <= 0){
        
    		close(channel)
    		return ;
    	}else if(length <= 1){
        
    		channel <- arr[0]
    		close(channel)
    		return
    	}else{
        
    		low := make([]int, 0)
    		mid := make([]int, 0)
    		high := make([]int, 0)
    
    		rand.Seed(time.Now().Unix())
    		base := arr[rand.Intn(length)]
    
    		for i := 0; i < length ; i++ {
        
    			if arr[i] < base {
        
    				low = append(low, arr[i])
    			}else if arr[i] == base {
        
    				mid = append(mid, arr[i])
    			}else{
        
    				high = append(high, arr[i])
    			}
    		}
    
    
    		left_chan := make(chan int, len(low))  // 注意这里必修加buffer。 否则会死锁。。为什么？？？？
    		right_chan := make(chan int, len(high))
    
    		if(level <= threads){
        //如果线程超过执行数量，顺序调用，否则并发调用
    			go QuickSort(low, left_chan, level, threads);
    			go QuickSort(high, right_chan, level, threads)
    		}else{
        
    			QuickSort(low, left_chan, level, threads);
    			QuickSort(high, right_chan, level, threads)
    		}
    
    		for v := range left_chan {
        
    			channel <- v
    		}
    
    		for _, v := range mid {
        
    			channel <- v
    		}
    
    		for v := range right_chan {
        
    			channel <- v
    		}
    
    		close(channel)
    		return
    	}
    }
    
    
    func main() {
        
    	data := []int{
        3, 6, 23, 7, 2, 4, 9, 13}
    	channel := make(chan int)
    	go QuickSort(data, channel, 1, 10)  // 这里必须是go，否则会一直阻塞，导致死锁
    	for v := range channel {
        
    		fmt.Println(v)
    	}
    }

[Link 1]: https://blog.csdn.net/zhizhengguan/article/details/104698957
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/9adfa62d5e4d49aa985d61b97e8d3d3e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/70af2d59490143f6acd141c3f092a4cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/af9252e97a70417299d8c19e1ace665f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/e7f99405d1354d889f5ef5fcd1d5f9b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/ae079ce160294aeba7b26c18498552db.png