`
jiangzhenghua
  • 浏览: 602851 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

插入排序算法

 
阅读更多

插入排序 Insertion Sort
     插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i] 又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤ L[i]騆[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j 1]时为止。
  简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种,这里只介绍直接插入排序,折半插入排序留到“查找”内容中进行。
  图1演示了对4个元素进行直接插入排序的过程,共需要(a),(b),(c)三次插入。

图1 对4个元素进行插入排序
在下面的插入排序算法中,为了写程序方便我们可以引入一个哨兵元素L[0],它小于L[1..n]中任一记录。所以,我们设元素的类型 ElementType中有一个常量-∞,它比可能出现的任何记录都小。如果常量-∞不好事先确定,就必须在决定L[i]是否向前移动之前检查当前位置是否为1,若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时,就将L[i]放入L[0]中,这样也可以保证在适当的时候结束第i 遍处理。下面的算法中将对当前位置进行判断。
算法如下:
    /**
     *插入排序(WHILE循环实现)
     *@paramsrc待排序数组
     */
    void doInsertSort1(int[] src)
    {
       int len=src.length;
       for(int i=1;i<len;i )
       {  
           int temp=src[i];
           int j=i;
          
           while(src[j-1]>temp)
           {
              src[j]=src[j-1];
              j--;
              if(j<=0)
                  break;
           }
           src[j]=temp;
           printResult(i 1,src);
       }
    }
    /**
     *插入排序(FOR循环实现)
     *@paramsrc待排序数组
     */
    void doInsertSort2(int[] src)
    {
       int len=src.length;
       for(int i=1;i<len;i )
       {
           int j;
           int temp=src[i];
           for(j=i;j>0;j--)
           {
              if(src[j-1]>temp)
              {
                  src[j]=src[j-1];
                 
              }else//如果当前的数,不小前面的数,那就说明不小于前面所有的数,
                   //因为前面已经是排好了序的,所以直接通出当前一轮的比较
                  break;
           }
           src[j]=temp;
           printResult(i,src);
       }

分享到:
评论

相关推荐

    C语言_插入排序法和冒泡排序法

    - **插入排序**:同样也是稳定的排序算法,相等元素的相对位置不会改变。 ### 四、应用场景 - **冒泡排序**:适用于小规模数据或者几乎已经排序的数据。 - **插入排序**:适用于小规模数据,或者是数据已经部分...

    Java直接插入排序算法源码

    总的来说,Java中的直接插入排序算法是一个直观易懂的排序方法,虽然在效率上不敌更高级的排序算法,但它在理解和实现上相对简单,对于初学者来说是很好的学习材料。通过阅读和实践这个源代码,你可以深入理解排序...

    插入排序算法c++实现

    综上所述,"插入排序算法c++实现"涉及到C++基础语法、数组与指针操作、循环和条件控制、排序算法原理、性能分析以及良好的编程习惯等多个方面。通过实践这个项目,开发者不仅可以深入理解插入排序算法,还能提升C++...

    直接插入排序法

    直接插入排序法~~~~~内部排序

    使用C语言写的直接插入排序算法

    ### 使用C语言实现的直接插入排序算法 #### 算法概述 本篇文章将详细介绍一个使用C语言编写的直接插入排序算法。直接插入排序是一种简单的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序...

    希尔排序,直接插入排序,折半插入排序算法.

    综上所述,希尔排序、直接插入排序和折半插入排序都是常见的排序算法。它们各有特点,适用于不同场景下的数据排序需求。希尔排序通过增加子序列的插入排序来提高效率;直接插入排序简单直观,但效率较低;而折半插入...

    插入排序法JAVA代码

    以下是一个简单的Java插入排序算法实现: ```java public class InsertionSort { public static void insertionSort(int[] array) { for (int i = 1; i ; i++) { int key = array[i]; int j = i - 1; // 将比...

    C语言实现的插入排序

    在这个示例中,`insertion_sort`函数实现了插入排序算法,`print_array`函数用于打印数组。主函数`main`中,我们创建了一个数组并调用`insertion_sort`对其进行排序,最后打印排序结果。 插入排序的时间复杂度在...

    插入排序法

    在压缩包中的"插入排序法"可能包含了一个或多个实现插入排序的C++源文件,用于演示和练习如何在实际编程中应用这个算法。通过阅读和运行这些代码,你可以更深入地理解插入排序的运作机制,并提升编程能力。

    c语言 插入排序法

    c语言基本插入排序法c语言基本插入排序法c语言基本插入排序法c语言基本插入排序法

    亂數用插入排序法 C++

    本主题聚焦于“亂數用插入排序法”,即使用插入排序算法对随机生成的数字序列进行排序。插入排序是一种简单直观的排序算法,适用于小规模或部分有序的数据集。以下是关于“亂數用插入排序法”的详细解释。 插入排序...

    插入排序算法C语言程序.zip

    总的来说,这个"插入排序算法C语言程序"项目提供了一个实践插入排序算法的机会,可以帮助开发者加深对排序算法的理解,尤其是在C语言环境下如何实现和优化排序算法。通过分析和运行代码,可以更好地掌握插入排序的...

    数据结构 直接插入排序的算法源程序

    ### 数据结构:直接插入排序算法解析 #### 一、引言 在计算机科学领域,排序是一种常见的操作,用于将一组无序的数据按照特定的顺序排列。插入排序是一种简单直观的排序算法,它的工作原理类似于人们手工排序扑克...

    zhijiecharupaixu.rar_插入排序_插入排序算法

    这个压缩包“zhijiecharupaixu.rar”包含的资源是关于直接插入排序算法的实现和相关资料。 直接插入排序的基本思想是:假设数组中有n个元素,已知前i个元素是有序的,现在要把第i+1个元素插入到已排序的序列中,使...

    冒泡,选择,插入排序算法c语言实现

    冒泡排序算法选择排序算法插入排序c语言实现

    直接插入排序-算法领域中直接插入排序算法详解与Python实现

    使用场景及目标:帮助读者理解直接插入排序算法的内部机制,学会在实际编程中使用Python实现该算法。 其他说明:文中提供了Python实现的直接插入排序算法代码,读者可以通过实践加深对该算法的理解。同时,对于算法...

    经典插入排序算法(c/c++语言)

    插入排序是一种基础且重要的排序算法,它的工作原理类似于人们整理扑克牌的过程。在这个教程中,我们将深入探讨插入排序在C/C++语言中的实现,并理解其背后的逻辑和效率。 ### 插入排序概述 插入排序是一种简单直观...

    堆排序与直接插入排序算法的比较

    堆排序与直接插入排序算法的比较 堆排序和直接插入排序是两种常用的排序算法,分别具有不同的时间和空间复杂度。本文将通过对两种排序算法的实现和比较,分析它们的优缺点,并讨论在不同场景下的应用。 1.1 功能...

    C#实现插入排序算法

    本文将深入探讨C#语言中实现插入排序算法的方法,以及其在升序和降序排序中的应用。 插入排序是一种简单直观的排序算法,它的基本思想是将待排序的数据元素看作是一个有序序列,每次将一个待排序的记录,按其关键字...

    c语言中的插入排序法PPT课件.pptx

    插入排序法是一种简单的排序算法,它通过比较待排序元素与已排序元素的大小,插入到合适的位置,以达到排序的目的。插入排序法的时间复杂度为O(n^2),空间复杂度为O(1)。 知识点二:插入排序法的实现步骤 插入排序...

Global site tag (gtag.js) - Google Analytics