码农知识堂 - 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. 

                    相关阅读:
      
                    
【数据结构与算法】树、二叉树的概念及结构(详解)                            
      
国信证券笔试题总分120分                            
      
学成在线第五天                            
      
【汉字识别】基于模板匹配实现汉字精准识别附Matlab代码                            
      
mac配置hdc                            
      
这是我见过最详细的Linux学习分享了，面面俱到，相见恨晚呐                            
      
Docker 第十三章 ： Docker 三剑客之 Swarm（服务管理命令）                            
      
城市群（Megalopolis）/城际（inter-city）OD相关研究即Open Access数据集调研                            
      
Vue中如何扩展⼀个组件                            
      
数据结构(C语言版)严蔚敏-＞排序                            
      
                          
                
      14. 
                
    14. 
                    原文地址：https://blog.csdn.net/qq_62309585/article/details/127641449
                
      15. 

            
        

        
      
            
        
                
      • 
                    最新文章
                
        • 
                
      • 
                    
沪漂五周年了：我越来越迷茫了                            
        
Agentic Skill Routing 实战：别再把所有 Skill 塞进 AI Agent 上下文                            
        
MySQL-Seconds_behind_master的精度误差                            
        
[MAF预定义ChatClient中间件-03]CachingChatClient——利用缓存省钱省时间                            
        
AI的至暗历史：从万众期待到被政府撤资，AI的两次死亡徘徊                            
        
Agent OS ：五种驯服不确定性的范式                            
        
PortSwigger SQL注入LAB11                            
        
数据库即时编译JIT                            
        
[Begin]AI Learn Data Day 0                            
        
深度学习进阶（二十七）现代 LLM 的核心架构设计其二：SwiGLU                            
        
                            
                
        • 
            
      

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

        
      
    




    
    
    
    

      
    
      
        
      
            
      
                
      
                    小工具
                    小游戏
                
      

                
      
                    Copyright © 2022 侵权请联系2656653265@qq.com   
                    京ICP备2022015340号-1
                
      
              
                
      
                    
                    
      京公网安备 11010502049817号