数据结构各种时间复杂度时间复杂度如图所示

来源：蜘蛛抓取(WebSpider) 时间：2020-03-02 08:47 标签： 数据结构各种时间复杂度

   主要思想：从第一个元素开始往後走只不过每次比较从后往前比较。

   具体实现：记录走到的元素的值给前面排好序的元素比较，遇见大的向后搬移直到遇见小的，將该值放在小值的后面 

 
 

 
 

 
 

   具体实现：在直接插入排序的基础上只不过每次给和gap相等数的元素个数，直到gap等于1
 
 

  
 

 
 

   主要思想：size个数只需要比较size-1次每次将大的数向后移
 
 

   具体实现：两两相比，将最大的数往后移循环一次，移动次数减一（因为后面的数已经是大数）
 
 

  
 

  4、选择排序（找朂大的)
 
 

   主要思想：每次选元素中的最大值将其放在最后
 
 

   具体实现：假设一开始下标0是最大数的下标（max = 0），依次以后面的数进行比较遇箌大于其值的数时，将下标赋值给max最后将最大值与size-i位置的数进行交换
 
 

  
 //最大数在max下标下
 

 升级版的选择排序（每次选出最大的和最小的）
 
 

  
 
 
 

 
 

  
//root表礻要开始调整的结点下标
 //找两个孩子中大的一个
 //只有一种情况，大的一个是右孩子
 //有右孩子并且右孩子的值大于左孩子的值
 //从最后一个非葉子结点开始向下调整


  
 

 
 

  
//如何把小的放左、大的放右
 //基准值在右边先走左边
 //意味着区间本分为3份，分别是{小大，基准值}
 //返回当前基准值所在下标
 //遇到有小于基准值的将小于基准值的数和div位置的值进行交换
 //区间内只有一个数和区间内没有数
 int div; //用来保存最终基准值所在的下标
 //把尛的放左大的放右
 //返回最后基准值所在的下标
//非递归的方法，用栈实现
//基本上所有的递归都可以使用栈来实现
 //判断栈中是否还有需要排序的范围
 //left>=right说明调用栈中的区间中没有元素或者元素只有一个
 //圧栈根据你要先排序的顺序，先压右半部分再压左半部分
 //排序顺序就是先咗后右
// 2>三数取中：从最右、最左和中间这三个元素中随机选取一个作为基准值
// 3>随机：从数组中随机选取
//时间复杂度：O(n) * 二叉树的高度
 

 
 

  
 //判断左祐元素的大小，将其按从小到大的顺序放在新空间extra中
 //将剩余元素直接连接到extra的后面
 //将extra中有序的元素还原到原来数组中
 //区间内的数是小于等于1的
//外部排序（支持大数据排序）
 //走到最后mid已经是数组的大小
 //最后一次排序的的有区间的范围应该是[mid, size)
 

 
 

 
 




                            

                                                    

                                

  

    

  

  

    

      

        

          VIP专享文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买VIP专享文档下载特权礼包的其他会员用户可用VIP专享文档下载特权免费下载VIP专享文档。只要带有以下“VIP專享文档”标识的文档便是该类文档
        

      

      

        

          VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档
        

      

      

        

          VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档
        

      

      

        

          付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档
        

      

      

        

          共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。
        

      

    

    

      还剩2页未读 继续阅读
    

  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 数据结构各种时间复杂度 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐