`

数据结构-排序: 插入排序(直接插入排序法)

阅读更多

数据结构-排序: 插入排序(直接插入排序法)

插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
 本节介绍两种插入排序方法:直接插入排序和希尔排序。
1.直接插入排序的基本思想
直接插入排序(Straight Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程 中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。
把a[i]插入到a[0],a[1],...,a[i-1]之中的具体实施过程为:先把a[i]赋值给变量t,然后将t依次与a[i-1],a[i- 2],...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t 赋值给a[j+1].

2、第i-1趟直接插入排序:
 通常将一个记录R[i](i=2,3,…,n-1)插入到当前的有序区,使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。
 排序过程的某一中间时刻,R被划分成两个子区间R[1..i-1](已排好序的有序区)和R[i..n](当前未排序的部分,可称无序区)。
 直接插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1..i-1]中适当的位置上,使R[1..i]变为新的有序区。因为这种方法每次使有序区增加1个记录,通常称增量法。
 插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理,此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置,须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。

一趟直接插入排序方法

1.简单方法

 首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1);然后将R[k..i-1]中的记录均后移一个位置,腾出k位置上的空间插入R[i]。
注意:
 若R[i]的关键字大于等于R[1..i-1]中所有记录的关键字,则R[i]就是插入原位置。

2.改进的方法
  一种查找比较操作和记录移动操作交替地进行的方法。
具体做法:
 将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1,i-2,…,1)的关键字进行比较:
 ① 若R[j]的关键字大于R[i]的关键字,则将R[j]后移一个位置;
②若R[j]的关键字小于或等于R[i]的关键字,则查找过程结束,j+1即为R[i]的插入位置。
 关键字比R[i]的关键字大的记录均已后移,所以j+1的位置已经腾空,只要将R[i]直接插入此位置即可完成一趟直接插入排序。

直接插入排序算法

1.算法描述

using System;
using System.Collections.Generic;
using System.Text;

namespace ExInsertionSorter
{
public class InsertionSorter
{
public void Sort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int t = arr[i];
int j = i;
while ((j > 0) && (arr[j - 1] > t))
{
arr[j] = arr[j - 1];//交换顺序
--j;
}
arr[j] = t;
}
}
static void Main(string[] args)
{
int[] array = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
InsertionSorter i = new InsertionSorter();
i.Sort(array);
foreach (int m in array)
Console.WriteLine("{0}", m);
}
}
}

4、直接插入排序的效率分析
(1)时间复杂度
从时间分析,首先外层循环要进行n-1次插入,每次插入最少比较一次(正序),移动两次;最多比较i次,移动i+2次(逆序)(i=1,2,…,n- 1)。若分别用Cmin ,Cmax 和Cave表示元素的总比较次数的最小值、最大值和平均值,用Mmin ,Mmax 和Mave表示元素的总移动次数的最小值、最大值和平均值,则上述直接插入算法对应的这些量为:
Cmin=n-1 Mmin=2(n-1)
Cmax=1+2+…+n-1=(n2-n)/2 Mmax=3+4+…+n+1=(n2+3n-4)/2
Cave=(n2+n-2)/4 Mmax=(n2+7n-8)/4
因此,直接插入排序的时间复杂度为O(n2)。

由上面对时间复杂度的分析可知,当待排序元素已从小到大排好序(正序)或接近排好序时,所用的比较次数和移动次数较少;当待排序元素已从大到小排好序(逆序)或接近排好序时,所用的比较次数和移动次数较多,所以插入排序更适合于原始数据基本有序(正序)的情况.

插入法虽然在最坏情况下复杂性为O(n2),但是对于小规模输入来说,插入排序法是一个快速的排序法。许多复杂的排序法,在规模较小的情况下,都使用插入排序法来进行排序,比如快速排序。

(2)空间复杂度
首先从空间来看,它只需要一个元素的辅助空间,用于元素的位置交换O(1)

(3)稳定性:
插入排序是稳定的,因为具有同一值的元素必然插在具有同一值得前一个元素的后面,即相对次序不变.

(4)结构的复杂性及适用情况

插入排序是一种简单的排序方法,他不仅适用于顺序存储结构(数组),而且适用于链接存储结构,不过在链接存储结构上进行直接插入排序时,不用移动元素的位置,而是修改相应的指针。

2.哨兵的作用
 算法中引进的附加记录R[0]称监视哨或哨兵(Sentinel)。
  哨兵有两个作用:
  ① 进人查找(插入位置)循环之前,它保存了R[i]的副本,使不致于因记录后移而丢失R[i]的内容;
  ② 它的主要作用是:在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0),因为R[0].key和自己比较,循环判定条件不成立使得查找循环结束,从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。
注意:
  ① 实际上,一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。
   【例】单链表中的头结点实际上是一个哨兵
  ② 引入哨兵后使得测试查找循环条件的时间大约减少了一半,所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法,要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技,而应该深刻理解并掌握这种技巧。

给定输入实例的排序过程

 设待排序的文件有8个记录,其关键字分别为:49,38,65,97,76,13,27,49。为了区别两个相同的关键字49,后一个49的下方加了一下划线以示区别。其排序过程见【动画模拟演示

算法分析

1.算法的时间性能分析

 对于具有n个记录的文件,要进行n-1趟排序。
各种状态下的时间复杂度:
┌─────────┬─────┬──────┬──────┐
│ 初始文件状态 │ 正序 │ 反序 │无序(平均) │
├─────────┼─────┼──────┼──────┤
│ 第i趟的关键 │ 1 │ i+1 │ (i-2)/2 │
│ 字比较次数 │ │ │ │
├─────────┼─────┼──────┼──────┤
│总关键字比较次数 │ n-1 │(n+2)(n-1)/2│ ≈n2/4 │
├─────────┼─────┼──────┼──────┤
│第i趟记录移动次数 │ 0 │ i+2 │ (i-2)/2 │
├─────────┼─────┼──────┼──────┤
│总的记录移动次数 │ 0 │(n-1)(n+4)/2│ ≈n2/4 │
├─────────┼─────┼──────┼──────┤
│时间复杂度 │ 0(n) │ O(n2) │ O(n2) │
└─────────┴─────┴──────┴──────┘
注意:
 初始文件按关键字递增有序,简称"正序"。
  初始文件按关键字递减有序,简称"反序"。

2.算法的空间复杂度分析
 算法所需的辅助空间是一个监视哨,辅助空间复杂度S(n)=O(1)。是一个就地排序。

3.直接插入排序的稳定性
 直接插入排序是稳定的排序方法。

分享到:
评论

相关推荐

    数据结构-排序算法的实现(代码+报告)

    - **定义**:直接插入排序是一种简单的排序算法,它的工作原理是构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 - **时间复杂度**:最好情况下的时间复杂度为O(n),最坏情况下...

    数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序等等

    根据提供的文件信息,我们可以深入探讨几种经典的排序算法:冒泡排序、直接插入排序、快速排序以及希尔排序。这些算法在数据结构与算法课程中是非常重要的基础内容,它们各自有着独特的特性和应用场景。 ### 1. ...

    数据结构学习总框架(精华版).pdf

    - **排序算法**:冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。 - **查找算法**:顺序查找、折半查找、二叉树查找等。 **5.4 分治法** - 定义:将大问题分解为小问题,分别...

    数据结构讲义

    - 定义:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,然后逐步减小增量,再进行排序。 - 时间复杂度:取决于增量序列的选择。 - **起泡排序** - 定义:通过重复地走访过要排序的列表,一次...

    数据结构知识要点

    在编程和算法设计中,理解并熟练运用数据结构至关重要,因为正确的数据结构选择直接影响程序的性能和可维护性。以下是关于数据结构的一些关键知识点: 1. 基本概念: - 数据:数据是信息的最小单位,如数字、字符...

    第十章 排序作业及答案数据结构

    1. 排序算法比较次数:在给定的题目中,如果表R已经按键值递增顺序排列,直接插入排序的比较次数最少。这是因为直接插入排序在最好情况下只需比较一次即可将新元素插入到正确位置。 2. 稳定性:稳定排序算法指的是...

    数据结构教程-英文原版

    - 排序算法:快速排序、归并排序、冒泡排序、插入排序、选择排序等,以及时间复杂度分析。 - 搜索算法:二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等。 - 动态规划:解决最优化问题,如背包问题、最长...

    数据结构期末复习

    ### 数据结构期末复习知识点 #### 第一章 绪论 1. **数据结构定义**: - 定义:数据结构是指相互之间存在一种或多种特定关系的数据元素的集合及其该集合中数据元素之间的关系组成的整体。 - 包含三个方面: - ...

    数据结构PPT----排序算法集合(sort )

    在IT领域,排序算法是数据结构与算法中的基础部分,对于高效处理大量数据至关重要。本文主要探讨了排序算法中的几种经典方法,包括直接插入排序、折半插入排序以及希尔排序。 首先,排序定义是为了将一个数据序列...

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

    根据给定文件的信息,本文将深入探讨C语言中的两种经典排序方法:插入排序法与冒泡排序法。这两种方法在实际编程中应用广泛,对于理解数据结构与算法的基础概念至关重要。 ### 一、冒泡排序法 #### 1.1 基本原理 ...

    直接插入排序C++代码 VS实现

    直接插入排序是一种简单...总的来说,直接插入排序是一种基础且实用的排序算法,理解其工作原理和实现方式对学习数据结构和算法非常有帮助。在实际编程中,根据不同的应用场景选择合适的排序算法是提高程序效率的关键。

    数据结构学习---排序

    1. **直接插入排序**: 直接插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。在这个过程中,如果新元素小于前一个元素,就...

    数据结构与算法分析答案

    - 排序算法:如冒泡排序、插入排序、选择排序、归并排序、快速排序等,关注稳定性、平均和最坏情况下的效率。 3. C语言实现: - C语言的特点:低级特性,高效,直接操作内存,适合编写系统级程序和算法实现。 - ...

    java基础数据结构-排序算法

    - **Shell排序**:通过先将整个待排序的记录分割成为若干子序列分别进行直接插入排序,最后再对整个序列进行一次直接插入排序。时间复杂度取决于增量序列的选择。 - **归并排序**:也是一种分治算法,将数组分成两...

    数据结构中个各种排序法

    在计算机科学中,排序是数据处理的一个重要环节,它涉及到对一组...以上内容介绍了排序的基本概念、分类、关键术语以及直接插入排序的原理和示例。掌握这些知识有助于理解和实现不同的排序算法,提高数据处理的效率。

    cpp-AlgorithmsC各种基础算法数据结构的C语言实现

    - 排序算法:如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等,它们在处理大量数据时有着不同的效率和适用场景。 - 搜索算法:包括线性搜索、二分搜索等,二分搜索在有序数组中的查找效率非常高。 ...

    《数据结构》教学大纲

    - 难点:直接插入排序、二分插入排序、希尔排序等算法的具体实现。 #### 四、教学内容、课时安排 - **第一章 绪论**(3学时): - 数据结构的基本概念。 - 抽象数据类型的表示与实现。 - 算法及其分析方法。 - ...

    数据结构:排序的运用

    1、 掌握直接插入排序、折半插入排序、冒泡排序、快速排序和归并排序等排序算 法的思想。 2、 实现直接插入排序、折半插入排序、冒泡排序、快速排序和归并排序等排序算 法的编程应用。 二、 问题描述 实现数据的折半...

    算法导论习题解答

    - 优先队列:基于堆实现的一种数据结构,支持高效的插入和删除最大(最小)元素操作。 - **快速排序** - 描述:采用分治策略的高效排序算法。 - 性能分析:平均情况下具有O(n log n)的时间复杂度。 - 随机版本:...

Global site tag (gtag.js) - Google Analytics