测试2

算法 in Golang：Quicksort（快速排序）

Quicksort（快速排序）

  • 快速排序 O(nlog2^n)，比选择排序要快 O(n²)
  • 在日常生活中经常使用
  • 使用了 D & C 策略（分而治之）

使用 Quicksort 排序数组

  • 不需要排序的数组（也就是 Base Case 基线条件）：
    • []，空数组
    • [s]，单元素数组
  • 很容易排序的数组：
    • [a, b]，两个元素的数组，只需检查它们之间的大小即可，调换位置
  • 3 个元素的数组（例如 [23, 19, 35]）：
    • 使用 D & C 策略，简化至基线条件（Base case）

  1. 从数组中随便选一个元素，例如 35，这个元素叫做 pivot（基准元素）

  2. 找到比 pivot 小的元素，找到比 pivot 大的元素，这叫做分区：[23, 19], (35), []

  3. 如果左右两个子数组已排好序（达到基线条件），结果：左边 + [pivot] + 右边

  4. 如果左右两个子数组没排好序（没达到基线条件），那么：

    quicksort(左边) + [pivot] + quicksort(右边)

使用 Quicksort 排序数组的步骤

  1. 选择一个 pivot
  2. 将数组分为两个子数组：
    1. 左侧数组的元素都比 pivot 小
    2. 右侧数组的元素都比 pivot 大
  3. 在两个子数组上递归的调用 quicksort

创建项目

~/Code/go via 
    

  
内容来源于网络如有侵权请私信删除

  

  
        

      
文章来源: 博客园

  
      

      原文链接:
      
        https://www.cnblogs.com/QiaoPengjun/p/17461882.html
      
    

  

       
        

 
  标签：
                        GO
                                GO语言
                                GOLANG
              

        

         	
      
    
      
    
                

  


                
        	

    你还没有登录，请先登录或注册！
  


        
    
      
  • 还没有人评论，欢迎说说您的想法！
    • 
  


        
        


  

    
相关课程

  

  

    

      

                                              

            

  

    
    
                
       
      
       
    
  

  

    

      
        GO语言区块链开发-密码学
      
    

    

    	 
      3545
                 
      



  	9.8元 
  	      	 	    

  


          

                                                

            

  

    
    
                
       
      
       
    
  

  

    

      
        8天入门GO语言
      
    

    

    	 
      3127
                 
      



  	9.8元