适用于:对少量元素排序较为有效,如n<=15
最好情况:正序(不需要移动)
最差情况:反序(需要移动n*(n-1)/2个元素)
直接先上java代码:
public class InsertSortTest { public static void insertSort(int[] array) { if (array == null || array.length < 2) { return; } for (int i = 1; i < array.length; i++) { int currentValue = array[i]; int position = i; for (int j = i - 1; j >= 0; j--) { if (array[j] > currentValue) { array[j + 1] = array[j]; position -= 1; } else { break; } } array[position] = currentValue; } } public static void main(String[] args) { int[] array = { 3, -1, 0, -8, 2, 1 }; System.out.println(java.util.Arrays.toString(array)); insertSort(array); System.out.println(java.util.Arrays.toString(array)); } }
原理(摘自 http://lib.csdn.net/article/datastructure/31546 ):
类似于多人排序一手扑克牌,开始时,我们左手为空且桌子上的牌面向下,然后我们每次从桌上拿一张牌插入左手上正确的位置,我们从右到左将它与已在手中的牌进行比较,拿在左手的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌。
图 2-1
下面来写伪代码INSERTION-SORT,参数是一个数组A[1..n],长度为n,用A.lenth来表示。该算法排序输入的数:算法在数组A中重排这些数,在任何时候,最多只有其中常数个数字存储在数组外面,在过程INSERTION-SORT结束时,输入数组A包含排序好的输出序列。
INSERTION-SORT(A)
for j = 2 to A.lenth key = A[j] //Insert A[j] into the sored sequence A[1..j-i]. i = j - i while i >0 and A[i] >key A[i +1] = A[i] i = i - 1 A[i + 1] =key
图2-2表明对A = [5,2,4,6,1,3]。该算法如何工作。下标j指出正被插入到手中的“当前牌”,在for循环的每次迭代的开始,包含元素A[1..j-i]的子数组构成了当前排序好的左手中的牌,剩余的子数组A[j+1..n]对应于仍在桌子上的牌堆。事实上元素A[1..j-1]就是原来在位置1到j-1的元素,现在已按序排列。我们把A[1..j-1]的这些性质 形式的表示为一个循环不变式。
图 2-2
循环不变式主要用来理解算法的正确性。关于循环不变式我们必须证明三条性质:
初始化:循环的第一次迭代之前,它为真。
保持:如果循环的某次迭代之前它为真,那么下次迭代之前它仍为真。
终止:在循环终止时,不变式为我们提供了一个有用的性质,该性质有助于证明算法的正确性。
这个类似于数学归纳法。f(1),f(n-1),f(n)。
初始化: A[1]只有一个元素,是排序好的,成立。
保持: for循环中第4~7行将A[j-1]A[j-2]A[j-3]等向右移一个位置,直到找到A[j]的适当位置第8行将A[j]的值插入到该位置。这时子数组A[1..j]有原来A[1..j]中的元素组成,单已按序排列。成立
终止: 最后研究在循环终止时发生了什么。导致循环终止的条件是j>A.length = n。因为每次迭代j增加1,那么必有j=n+1.在循环不变式的表述中将j用n+1替换,我们有:子数组A[1..n]由原来在A[1..n]中的元素组成,但已按序排序。因此算法正确。
伪代码的约定:
--缩进表示块结构。
--while、for、repeat-unti等循环结构以及if-else等条件结构与C、C++、java、Python和Pascal中的那些结构具有类似的解释。不像某些c++、java和pascal中的情况,在本算法章节中的情况,退出循环后,循环计数器保持其值。因此紧接在一个for循环后,循环计数器的值就是第一个超出for循环界限的那个值。本例中循环终止时j=A.lenth+1,当for循环迭加时用to,迭减时用downto。当循环计数器以大于1的改变时,该改变量跟在可选关键词by之后。
--“//”后面部分是注释。
--形如i=j=e的多重赋值将表达式e的值赋给变量i和j;等价于j=e后跟i=j;
--变量(i、j、key)是局部的给定过程的。若无显式说明,我们不使用全局变量。
--数组元素通过“数组名[下标]”的形式访问。记号“..”用于表示数组中值得一个范围。
--复合数据通常被组织成对象,对象由属性组成。如A.length,我们把表示一个数组或对象的变量看做指向表示数组或对象的数据的一个指针。对于某个对象x的所有属性f,赋值y=x导致y.x等于x.y。换句话说在赋值x=y后x和y指向相同的对象。我们的属性记号可以“串联”。如果y=x.y,那么x.f.g与y.g相同
--我们按值把参数传给过程:被调用过程接收其参数自身的副本。如x=y对调用过程是不可见的,然而x.y=3却是可见的。类似的,数组通过指针来传递,结果指向数组的一个指针被传递,而不是整个数组,单个数组的元素的改变对调用过程是可见的。
--一个return语句立即将控制返回到调用过程的调用点。大多数return语句也将一个值传递回调用者,我们的伪代码允许在单一的return语句返回多个值
--布尔运算符“and”和“or”都是短路的。如“x and y”,首先求x,如果x为FALSE,那么表达式不可能为TRUE,所以不再求y。如“x != NIL and x.f=y”,我们不必担心当x = NIL时我们试图求值x.f将会发生什么情况。
--error表示一被调用的过程情况不对而出现一个错误。调用过程负责处理该错误,所以我们不用说明将采取什么行动。
相关推荐
本话题主要探讨六种内部排序算法:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序以及堆排序。这六种排序算法各有优劣,适用于不同的场景,接下来我们将逐一进行详细阐述。 1. **直接插入排序**: 直接...
算法基础:冒泡排序;直接插入排序;希尔排序;快速排序;堆排序;归并排序;基数排序_Algorithm
插入排序是一种简单直观的排序算法,它的工作原理类似于我们平时整理扑克牌。首先,将数组分为已排序和未排序两部分,每次从未排序的部分取出一个元素,插入到已排序部分的正确位置。这个过程会不断重复,直到所有...
插入排序是一种基础且直观的排序算法,尤其适合小型数据集或部分有序的数据。它的核心思想是将待排序的数组分为两个部分:已排序区域和未排序区域。算法从第二个元素开始,每次都将未排序区域的一个元素插入到已排序...
常见算法八种常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序、快速排序、归并排序、堆排序和LS_calgorithms
八种常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序、快速排序、归并排序、堆排序和LST基数排_EightAlgorithms
java8中经典排序算法:插入排序、堆排序,选择排序、希尔排序,基数排序、冒泡排序、归并排序、快速排_Arithmetic
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
在本文中,我们将深入探讨四种经典的排序算法:插入排序、选择排序、基数排序和冒泡排序,以及它们在C++语言中的实现。 **插入排序(Insertion Sort)** 插入排序是一种简单直观的排序算法,它的工作原理类似于我们...
本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**: 插入排序是一种简单的...
1. **直接插入排序**:直接插入排序是最基础的排序算法之一。它的工作原理是将待排序的元素逐个与已排序的部分进行比较,找到合适的位置插入。这种算法对于小规模或部分有序的数据集表现较好,但对于大规模无序数据...
冒泡排序、插入排序、选择排序、希尔排序、归并排序、快速排序和堆排序是七大基础的计算机算法,它们各自有着不同的特点和适用场景。 一、冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法。它重复地遍历要...
java可运行排序算法:①插入排序、②冒泡排序、③选择排序、④学生学号按照成绩高低排序的一个简单实例。在java工程项目的源文件src中建立Array包,可运行这四个.java文件,便于对java中的排序算法及数组结构进一步...
本文将详细探讨十种经典的排序算法在C++中的实现,分别是冒泡排序、桶排序、计数排序、堆排序、插入排序、合并排序、快速排序、基数排序、选择排序和希尔排序。 1. **冒泡排序**:冒泡排序是最简单的排序算法之一,...
排序算法汇总P: 冒泡排序快速排序直接选择排序插入排序希尔排序 堆排序........
在初学C语言时,比较重要的知识点就是排序算法,这里提供了一种插入排序算法的实现路径,供广大学习者参考。
十个基础排序算法:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、桶排序、计数排_SortAlgorithm
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
本资源包含了几种基本的排序算法,如冒泡排序、选择排序和插入排序,这些都是理解和学习算法的基础。 **冒泡排序**是最基础的排序算法之一,它通过重复遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把...