`
yuanzher
  • 浏览: 30731 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

【转】插入排序(I)Insert Sort

阅读更多

插入排序(I)

直接插入排序

  直接插入排序是一种最简单的排序方法,它的基本操作是将一个记录插入到已排好的有序的表中,从而得到一个新的、记录数增1的有序表。

  当前元素的前面元素均为有序,要插入时,从当前元素的左边开始往前找(从后往前找),比当前元素大的元素均往右移一个位置,最后把当前元素放在它应该呆的位置就行了。

直接插入排序过程实例

  比如对 21、25、49、25、16、8这些数排序:

 

                    

直接插入排序分析

  移动、比较的次数可作为衡量时间复杂性的标准。

  最优情况:如果原始的输入序列为正序:

  比较次数:n-1

  移动次数:0

  最差情况:如果原始的输入序列为逆序:

  比较次数:(n+2)(n-1)/2

  移动次数:(n+4)(n-1)/2

  所以直接插入排序的时间复杂度为O(n2)。

 

直接插入排序代码

复制代码
typedef int ElemType;
//假设记录类型为int,并且记录关键字就是其本身
void InsertSort(ElemType A[], int n)
{
    ElemType x;
    for(int i=1;i<n;++i)
    {
        x=A[i];
        int j=i-1;
        while(A[j]>x)
        {
            A[j+1]=A[j];
            j--;
        }
        A[j+1]=x;
    }
}
复制代码

 

其他插入排序

  直接插入排序算法在n比较小的时候很好,但是当n增大了以后就不宜采用直接插入排序。

  在直接插入排序的基础上,从减少“比较”和“移动”这两种操作的次数着眼,可得到下列插入排序的算法。

折半插入排序

  由于插入的基本操作是在一个有序的表中进行查找和插入,所以其中这个“查找”操作可以利用折半查找来实现。

  折半插入排序仅减少了关键字间的比较次数,而记录的移动次数不变。因此,折半插入排序的时间复杂度仍为O(n2)。

2-路插入排序

  2-路插入排序是在折半插入排序的基础上再改进之,目的是减少排序过程中移动记录的次数,但为此需要n个记录的辅助空间。

  具体做法是:另设一个同类型的数组d,将第一个元素复制过去,将这个第一个元素看做在排好序的序列中处于中间位置的记录(并且一直把它作为此标准),然后把d看做一个循环向量,设置两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。插入元素时,先将当前元素和d[0]比较,如果该元素比d[0]小,则插入到d[0]之前的有序表中,如果比d[0]大,则插入到d[0]之后的有序表中。

  在2-路插入排序中,移动记录的次数约为n2/8,并且当第一个元素是待排序记录中关键字最小或最大的记录时,2-路插入排序就完全失去了它的优越性

 

表插入排序

复制代码
#define SIZE 100  //静态链表容量
typedef struct
{
    Rcd rc;        //记录项
     int next;        //指针项
}SLNode;        //表结点类型
typedef struct
{
    SLNode r[SIZE];    //0号元素为表头结点
    int length;        //链表当前长度
}SLinkListType;        //静态链表类型
复制代码

 

  以上述静态链表类型作为待排序记录序列的存储结构,并且,为了插入方便起见,设数组中下标为0的结点为表头结点,并令表头结点记录的关键字为最大整数。

  则表插入排序的过程描述如下:首先将静态链表中数组下标为1的结点和表头结点构成一个循环链表,然后依次将下标为2至n的结点按记录关键字非递减有序插入到循环链表中。

  表插入排序的时间复杂度仍是O(n2)。

  表插入排序的结果只是求得一个有序链表,只能对它进行顺序查找,不能进行随机查找。为了能实现有序表的折半查找,需要对记录进行重新排列。

  重排记录的做法:顺序扫描有序链表,将链表中第i个结点移动至数组的第i个分量中。

分享到:
评论

相关推荐

    JAVA插入排序 insert sort

    for(int i=0;i;i++) { String temp = strArray[i]; while(i&gt;0 && (Integer.parseInt(temp) &gt; Integer.parseInt(strArray[i-1]))) { strArray[i] = strArray[i-1]; i--; } strArray[i] = ...

    插入排序(Insert Sort).md

    在B站讲插入排序的笔记,需要的同学可以免费下载

    03_insert_sort_插入排序算法_

    插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。本文将深入探讨插入排序的基本思路、代码实现以及时间复杂度分析。 ### ...

    C语言实现的插入排序

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

    插入排序 插入排序示例

    这段代码首先定义了一个`insert_sort`函数,用于实现插入排序算法。该函数接受两个参数:一个指向整型数组的指针`d`和一个整型变量`n`,表示数组的长度。接下来是对插入排序算法的具体实现过程的解析: - **外层...

    java插入排序 Insert sort实例

    1. 直接插入排序(Direct Insertion Sort) 直接插入排序的基本思想是,每次将一个待排序的记录,按其关键字大小插入到前面已经排序的子序列中的适当位置,直到全部记录插入完成为止。在Java中,直接插入排序的实现...

    C#,插入排序算法(Insert Sort Algorithm)的源代码与数据可视化

    常见的四种排序算法是:简单选择排序、冒泡排序、插入排序和快速排序。其中的快速排序的优势明显,一般使用递归方式实现,但遇到数据量大的情况则无法适用。实际工程中一般使用“非递归”方式实现。本文搜集发布四种...

    Python实现的插入排序,冒泡排序,快速排序,选择排序算法示例

    本文实例讲述了Python实现的插入排序,冒泡...def insert_sort(list): for i in range(len(list)): Key = list [i] #待插入元素 j = i - 1 while(Key &lt; list&gt;= 0): list[j+1] = list[j] #后移元素 list[j] = Key

    用java实现插入排序InsertSort

    用java实现插入排序InsertSort 用java实现插入排序InsertSort用 java实现插入排序InsertSort

    经典排序算法,有选择排序,冒泡排序,交换排序,谢尔排序,插入排序基数排序

    插入排序(Insert Sort) 插入排序是一种简单直观的排序算法,其工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只...

    插入排序和归并排序的实现java

    这里我们将深入探讨两种常见的排序算法:插入排序(Insertion Sort)和归并排序(Merge Sort),它们都是在Java环境下实现的。 **插入排序**是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序...

    直接插入排序

    直接插入排序(Straight Insertion Sort)是一种简单直观的排序算法。它的基本思想是将一个待排序的数据元素插入到一个已经排好序的序列中,使得这个序列仍然保持有序状态。这种排序方式类似于我们在玩扑克牌时对...

    插入排序C++实现

    网上有很多讲插入排序的算法,但大多数都没有提供完整的程序,于是我在业余时间参考网上资料写了一个插入排序的完整C++实现,在VC6.0++编译通过,大家打开压缩文件点击sort.dsw文件打开即可编译运行,代码也有详解的...

    常用算法 2分法插入排序

    2分法插入排序(Binary Insertion Sort)是一种基于插入排序的算法,它结合了二分查找的策略来优化传统插入排序的过程。在传统插入排序中,我们需要将一个新元素与已排序的序列逐个比较,找到合适的位置插入。而2分...

    递归实现插入排序实验报告

    在递归实现插入排序的过程中,主要涉及两个函数:`InsertionSort` 和 `Insert`。`InsertionSort` 是主函数,负责调用自身来处理递归过程。它的基本思想是将数组分为两部分,前 `n-1` 个元素已经排好序,然后将第 `n`...

    直接插入和选择排序算法

    直接插入排序(Insertion Sort)是一种简单的排序算法,其工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上通常采用in-place排序(即只需用到O(1)的...

    插入排序法C程序实现

    根据给定的信息,我们可以提取并总结出以下几个关键的IT知识点: ...以上就是根据给定文件内容所整理出的关键IT知识点,包括折半查找的不同实现方法、直接插入排序法的具体实现以及排序算法在实际应用中的结合使用。

    选择排序-插入排序-快速排序-冒泡排序

    在C语言环境下,快速排序.c、insert_sort.c、select_sort.c和maopao_sort.c这四个文件分别对应快速排序、插入排序、选择排序和冒泡排序的源代码实现,读者可以通过阅读和学习这些代码来加深对这些排序算法的理解。

    C++排序算法之插入排序源码

    ### C++ 排序算法之插入排序源码详解 #### 一、概述 本文将详细介绍一个基于 C++ 的插入排序算法实现。插入排序是一种简单直观的排序方法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后...

    插入排序算法(动态数组实现)

    插入排序算法(动态数组实现) printf("--------插入排序算法的实现--------\n"); printf("输入数组的大小length:\n"); int length=0;... insert_sort(array,length); free(array);//释放动态数组空间

Global site tag (gtag.js) - Google Analytics