码农知识堂 - 1000bd
  •   Python
  •   PHP
  •   JS/TS
  •   JAVA
  •   C/C++
  •   C#
  •   GO
  •   Kotlin
  •   Swift

  • 数组排序（O（n的二次方））

    1.插入排序

    最简单的排序算法之一是插入排序（insertion sort)。插入排序由N-1趟〈 pass）排序组成。对于p=1到N-1趟，插入排序保证从位置0到位置p上的元素为已排序状态。插入排序利用了这样的事实:位置0到位置p-1上的元素是已经排过序的。下面表格显示了一个简单的数组在每一趟插入排序后的情况。

    初始状态34864513221移到位置
    p=1834645132211
    p=2834645132210
    p=3834516432211
    p=4832345164213
    p=5821323451644
    1. template<typename Comparable>
    2. void insertsort(vectorves)
    3. {
    4.     for(int i=1;isize()-1;i++)
    5.     {
    6.         Comparable tmp=ves[i];
    7.         for(int j=i;j>0&&tmp-1];j--)
    8.         ves[j]=ves[j-1];
    9.         a[j]=tmp;
    10.         
    11.  
    12.     }
    13. }

    2.插入排序实现STL sort

    在STL中，排序例程不采用由具有可比性的项所组成的数组作为单一的参数，而是接收一对迭代器来代表在某范围内的起始和终止标志。一个双参数排序例程使用一对迭代器，并假设所有的项都可以排序。而一个三参数排序例程有一个函数对象作为第三个参数。

    (1)我们必须编写一个双参数排序和一个三参数排序的例程。假定双参数排序调用三参数排序，同时使用less ( )作为第三个参数。

    (2)数组访问必须转换成迭代器访问。

    (3）原始代码需要创建tmp，在新代码中它将具有类型object。

    第一个观点最容易实现，因为模板类型参数(例如，泛型)对双参数排序来说都是iterator:然而，object不是一个泛型参数。我们可以通过编写一个辅助例程来解决这个问题。这个辅助例程将object作为另一个模板类型参数。

    1. emplate<typename Iterator>
    2. void insertsort(Iterator&begin,Iterator&end)
    3. {
    4.     if(end!=begin)
    5.     insertsort(begin,end,*begin);
    6. }
    7. template<typename Iterator,typename Object>
    8. void insertHelp(Iterator begin,Iterator end,
    9.                Object& obj)
    10.                {
    11.                  insertsort(begin,end,less());
    12.                }
      13.  

      这里的小窍门是在双参数排序中，*begin具有类型object，并且辅助例程具有所需要的第二个泛型的参数。现在双参数排序写完了，下面可以写三参数排序。但是，需要声明tmp为object类型，三参数排序只具有1terator和Comparator是泛型类型。因此我们不得不再次使用相同的技巧来得到一个四参数例程，将一个object类型的项作为第四个参数，仅仅是为添加一个辅助
       

      1. emplate<typename Iterator,typename Comparable,typename Obj>
      2. void insertsort(const Iterator&begin,const Iterator&end,
      3. Comparable&lessThan)
      4. {
      5.     if(begin!=end)
      6.     insertsort(begin,end,lessThan,*begin);
      7.     
      8. }
      9. template<typename Iterator,typename Comparable,typename Object>
      10. void insertsort(const Iterator&begin,const Iterator&end,Comparable
      11. lessThan,const Object&obj)
      12. {
      13.     Iterator j;
      14.     for( auto i=begin+1;j
      15.     {
      16.         obj tmp=*i;
      17.         for(j=p;j!=begin&&lessThan(tmp,*(j-1));j--)
      18.         *j=*(j-1);
      19.         *j=tmp;
      20.     }
      21.  
      22. }
       

       

      希尔排序
       

      背景：
       

      谢尔排序〈Shellsort）的名称源于它的发明者Donald Shell，该算法是冲破二次时间屏障的第一批算法之一，不过，直到它最初被发现的若干年后才证明了它的亚二次时间界。正如上节所提到的，它通过比较相距-一定间隔的元素来工作;各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后-趟排序为止。由于这个原因，谢尔排序有时也叫作缩减增量排序( diminishing increment sort)。
       

      谢尔排序使用一个序列^h{1} ^h{2}... ^h{n}叫作增量序列（increment sequence)。只要^h{1}= 1，任何增量序列都是可行的，不过，有些增量序列比另外一些增量序列更好（后面我们将讨论这个问题)。在使用增量h的一趟排序之后，对于每一个i我们有a[i]≤a[i + h](这里该不等式是有意义的):所有相隔h的元素都被排序。此时称文件是h排序的(he-sorted)。例如，下面显示了几趟排序后数组的情况。谢尔排序的一个重要性质(我们只叙述而不证明)是，一个^h{k}排序的文件(此后将是^h{k-1};排序的）保持它的^h{k}排序性。事实上，假如情况不是这样的话，那么该算法也就没什么意义了，因为前面各趟排序的成果会被后面各趟排序给打乱。
       

      初始状态81941196123517952858417515
      5排序之后35121128124175159658819495
      3排序之后28121135154158179475819695
      1排序之后11121517283541587581949596
       

      增量序列的一个流行（但是不好）的选择是使用Shell建议的序列:^h{i}=[N/2]和^h{k}=[h/2].下包含一个使用该序列实现谢尔排序的方法。后面我们将看到，存在一些递增的序列，它们对该算法的运行时间给出了重要的改进;即使是一个小的改变都可能剧烈地影响算法的性能
       

      1. void shellsort(vectorves)
      2. {
      3.     for(int gap=ves.size()/2;isize();gap/=2)
      4.     {
      5.         for(int i=gap;isize();i++)
      6.         {
      7.             Comparable tmp=ves[i];
      8.             for(int j=i;j>=gap&&tmp
      9.             ves[j]=ves[j-gap];
      10.             ves[j]=tmp;
      11.         }
      12.     }
      13. }
       

      最佳增量 为 Hibbzard增量 
       

      9*4^{i}-9*2^i+1
       

      4^i-3*2^i+1
      
                
                    
                

                
    13. 

                    相关阅读:
      
                    
C++17：variant                            
      
DayZ服务器一机多服的设置方法教程                            
      
Quicker快速开发，简单的网页数据爬取（示例，获取天眼查指定公司基础工商数据）                            
      
Postgresql源码（113）表达式JIT计算简单分析                            
      
Python读取NC格式数据绘制风场和涡度图                            
      
系统架构设计师（第二版）学习笔记----嵌入式系统及软件                            
      
JAVA-读取excel转成html 将excel表格转换为HTML文件格式 转成前端表格样式                            
      
SAP HANA Time Zone设置                            
      
ava异常处理面试题及答案                            
      
API 集成测试工具Hitchhiker 0.1.1 正式发布                            
      
                          
                
      14. 
                
    14. 
                    原文地址：https://blog.csdn.net/qq_62309585/article/details/127641449
                
      15. 

            
        

        
      
            
        
                
      • 
                    最新文章
                
        • 
                
      • 
                    
攻防演习之三天拿下官网站群                            
        
数据安全治理学习——前期安全规划和安全管理体系建设                            
        
企业安全 | 企业内一次钓鱼演练准备过程                            
        
内网渗透测试 | Kerberos协议及其部分攻击手法                            
        
0day的产生 | 不懂代码的"代码审计"                            
        
安装scrcpy-client模块av模块异常，环境问题解决方案                            
        
leetcode hot100【LeetCode 279. 完全平方数】java实现                            
        
OpenWrt下安装Mosquitto                            
        
AnatoMask论文汇总                            
        
【AI日记】24.11.01 LangChain、openai api和github copilot                            
        
                            
                
        • 
            
      

            
        
                
      • 
                    热门文章
                
        • 
                
      • 
                    
十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧！！！                            
        
奉劝各位学弟学妹们，该打造你的技术影响力了！                            
        
五年了，我在 CSDN 的两个一百万。                            
        
Java俄罗斯方块，老程序员花了一个周末，连接中学年代！                            
        
面试官都震惊，你这网络基础可以啊！                            
        
你真的会用百度吗？我不信 — 那些不为人知的搜索引擎语法                            
        
心情不好的时候，用 Python 画棵樱花树送给自己吧                            
        
通宵一晚做出来的一款类似CS的第一人称射击游戏Demo！原来做游戏也不是很难，连憨憨学妹都学会了！                            
        
13 万字 C 语言从入门到精通保姆级教程2021 年版                            
        
10行代码集2000张美女图，Python爬虫120例，再上征途                            
        
                            
                
        • 
            
      

        
      
    




    
    
    
    

      
    
      
        
      
            
      
                
      
                    Copyright © 2022 侵权请联系2656653265@qq.com   
                    京ICP备2022015340号-1
                
      
                
      
                    正则表达式工具
                    cron表达式工具
                    密码生成工具
                
      
                
      
                    
                    
      京公网安备 11010502049817号