有一个已经有序的数据序列,要求在这个已经排好序的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法。
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序。
如下图所示:
算法描述
一般来说,具体算法描述如下:
1.从第一个元素开始,该元素可以认为已经被排序
2.取出下一个元素,在已经排序的元素序列中从前向后扫描
3.如果该元素小于某个有序序列中的某个元素a,将该元素插入a之前,该元素以后元素后移
4.重复步骤2~3
Java代码实现如下:
private static void insertSort(int[] a){ for(int i= 1;i<a.length;i++){ for(int j = 0;j<i;j++){ //将a[i]插到有序数列a[0]~a[i-1]中,从前向后扫描; if(a[i]<a[j]){ backMove(j,i,a); //a[j]~a[i-1]中元素后移 break; } } System.out.print("第"+ i +"趟插入排序:"); print(a); System.out.println(); } //插入排完序后; print(a); } private static void backMove(int start,int end,int[] a){ int temp = a[end]; for(int i = end;i>start;i--){ a[i] = a[i-1]; } a[start] = temp; } private static void print(int[] a) { for(int i:a) System.out.print(i+" "); }
该算法的变种:
根据上述算法描述的第2步
1.插入元素可以从数据的末尾开始取:
这样代码实现较容易些,但移动的元素较多;
2.从已排好序的序列的下一个元素取,但从已排好的序列从后向前扫描。这样上述算法描述第3步就变成:如果该元素大于扫描的某个元素a,插入a元素之后;
3.如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序(或者二分插入排序或者折半插入排序)。
插入排序中,总是先寻找插入位置,然后在实行挪动和插入过程;寻找插入位置采用顺序查找的方式(从前向后或者从后向前),既然需要插入的数组已经是有序的,那么可以采用二分查找方法来寻找插入位置,提高算法效率,但算法的时间复杂度仍为O(n2)。
根据以上变种总结:
1.取插入的元素有两种方式:
(1)取下一个元素;
(2)取数列最后一个元素;
2.扫描有序序列已获取插入元素的位置有三种方式:
(1)从前向后扫描;
(2)从后向前扫描;
(3)二分查找;
一般插入方式为(1)(1),称为简单插入排序;优化插入方式为(1)(3),称为二分查找排序(二分查找排序即二分插入排序,实质即插入思想)。
算法复杂度
通过以上代码,很容易知道,时间复杂度度为O(n^2)。是稳定排序。
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。本文将深入探讨C语言实现的插入排序及其相关知识点。 首先,理解插入排序...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
### 插入排序Java代码详解 #### 一、插入排序简介 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,...
**插入排序**是一种基础且广泛使用的排序算法,尤其在数据量较小或者部分有序的情况下表现出较高的效率。它基于分治法的思想,将一个大问题分解成若干小问题来解决。在这个场景中,我们讨论的是如何使用分治法的思想...
此案例难度系数4,属于Scratch高级编程,插入排序相对而言比选择排序和冒泡排序理解起来要难一点,但是还是相对简单的排序,尤其是对少量元素排序的时候,效率较高;综合考查说话、随机数、无限循环(条件循环)、...
21、折半插入排序 22、21、折半插入排序 22、冒泡排序 21、折半插入排序 22、冒泡排序 23、快速排序 21、折半插入排序 22、冒泡排序 23、快速排序 24、简单选择排序 21、折半插入排序 22、冒泡排序 23、快速排序 24...
### 插入排序详解 #### 一、插入排序概述 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上通常采用in-...
### 数据结构之直接插入排序详解 #### 一、引言 在计算机科学中,排序算法是数据处理中不可或缺的一部分,而直接插入排序是一种简单直观的排序方法。它的工作原理类似于我们手动排序一组卡片的方式——每次从未...
本实验涉及了六种常见的排序算法:泡泡排序、直接插入排序、折半插入排序、希尔排序、直接选择排序,并且对每种排序算法进行了性能分析,包括统计执行时间、比较次数和交换次数。这些数据被保存在TXT文件中,便于...
本文将详细讲解六种经典的排序算法——合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合提供的文件名(sort.c、set.c、main.c、set.h、sort.h)推测出每个文件可能包含的代码实现。 1. **合并...
下面将详细讲解这7种排序算法:快速排序、归并排序、插入排序、选择排序、冒泡排序、堆排序以及希尔排序。 1. **快速排序**:由C.A.R. Hoare提出的,采用分治策略。基本思想是选取一个基准元素,通过一趟排序将待...
根据提供的文件信息,我们可以深入探讨几种经典的排序算法:冒泡排序、直接插入排序、快速排序以及希尔排序。这些算法在数据结构与算法课程中是非常重要的基础内容,它们各自有着独特的特性和应用场景。 ### 1. ...
### 数据结构:直接插入排序算法解析 #### 一、引言 在计算机科学领域,排序是一种常见的操作,用于将一组无序的数据按照特定的顺序排列。插入排序是一种简单直观的排序算法,它的工作原理类似于人们手工排序扑克...
本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**: 插入排序是一种简单的...
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
### 数据结构之折半插入排序 #### 知识点概览 1. **折半插入排序的基本概念** 2. **折半插入排序算法原理** 3. **折半插入排序的时间复杂度分析** 4. **折半插入排序的空间复杂度分析** 5. **折半插入排序与普通...
在本文中,我们将深入探讨四种经典的排序算法:插入排序、选择排序、基数排序和冒泡排序,以及它们在C++语言中的实现。 **插入排序(Insertion Sort)** 插入排序是一种简单直观的排序算法,它的工作原理类似于我们...
### 直接插入排序与希尔排序的比较 #### 一、概述 本篇文章将通过一组具体的数据集(8个整数)对直接插入排序(Direct Insertion Sort)和希尔排序(Shell Sort)这两种排序方法进行深入分析和比较。这两种排序...