java数据结构之插入排序

插入排序就是把当前待排序的元素插入到一个已经排好序的列表里面。 一个非常形象的例子就是右手抓取一张扑克牌，并把它插入左手拿着的排好序的扑克里面。

插入排序的最坏运行时间是O(n2)， 所以并不是最优的排序算法。

如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。

如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是Θ(n2)。

简单例子：

public class Demo6 { 

  public static void main(String[] args) {
    //定义一个整型数组
    int[] nums = new int[]{4,3,-1,9,2,1,8,0,6};
    //打印没有进行排序的数组
    System.out.println("没有排序之前的结果:" + Arrays.toString(nums));
    for(int index=0; index<nums.length; index++) {
     //获得需要插入的数值
     int key = nums[index];
     //取得下标值
     int position = index;
      /循环比较之前排序好的数据，找到合适的地方插入
     while(position >0 && nums[position-1] > key) {
      nums[position] = nums[position-1];
      position--;
     }
     nums[position] = key;
    }
    //打印排序后的结果
    System.out.println("排序后的结果:" + Arrays.toString(nums));
   }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Java实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    Java实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是EightAlgorithms.java文件,代码如下: import java.util.Arrays; /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ public class EightAlgorithms { //插入排序:时间复杂度o(n^2) p

  • Java直接插入排序算法实现

    序:一个爱上Java最初的想法一直没有磨灭:"分享我的学习成果,不管后期技术有多深,打好基础很重要". 工具类Swapper,后期算法会使用这个工具类: 复制代码 代码如下: package com.meritit.sortord.util; /** * One util to swap tow element of Array *  * @author ysjian * @version 1.0 * @email ysjian_pingcx@126.com * @QQ 6466337

  • java插入排序 Insert sort实例

    复制代码 代码如下: //直接插入排序void DirectInsertionSort(int* arr, int nLen){    int i, j;    for (i=1; i<nLen; i++)    {        int temp = arr[i];        for (j=i-1; j>=0; j--)        {            if (temp < arr[j])                arr[j+1] = arr[j];         

  • Java排序算法总结之插入排序

    本文实例讲述了Java插入排序方法.分享给大家供大家参考.具体分析如下: 有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到插入排序法.本文主要介绍的是插入排序的java实现.   插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据.比较和交换的时间复杂度为O(n^2),算法自适应,对于数据已基本有序的情况,时间复杂度为O(n),算法稳定,开销很低.算法适合于数据已基本有序或者数据量

  • java实现插入排序算法

    java实现插入排序算法

    1.算法概念. 每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序. 2.算法思想. 假设待排序的记录存放在数组R[1..n]中.初始时,R[1]自成1个有序区,无序区为R[2..n].从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区. public static void insertSort(int[] array) { int len = array.length; for (int i = 1; i < len;

  • java直接插入排序示例

    java直接插入排序示例

    影响排序效率的一般从3个方面比较:数据比较的次数,数据移动的次数,内存空间占用的大小.我们就冒泡排序.选择排序.插入排序.快速排序做一个总的比较.一般情况下不会使用冒泡排序算法,因为它的比较次数和移动次数在几种排序算法中都是最多的,它的唯一好处是算法简单,易于理解,所以在数据量很小的时候它会有些应用价值.选择排序在比较次数上和冒泡排序一样,都是n的平方,但它把交换的次数降低到了最低,所以在数据量很小且交换数据相对于比较数据更加耗时的情况下,可以应用选择排序.在大多数情况下,当数据量比较小或基本上

  • Java实现插入排序实例

    本文实例讲述了Java实现插入排序的方法.分享给大家供大家参考.具体实现方法如下: import java.util.Arrays; /** * 算法名称: 插入排序 * 最佳效率O(n):最糟效率O(n²)与冒泡.选择相同,适用于排序小列表 * 若列表基本有序,则插入排序比冒泡.选择更有效率. * @author L.Eric * */ public class insertionSorting { public static void main(String[] args) { //定义一个

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • Java经典排序算法之二分插入排序详解

    Java经典排序算法之二分插入排序详解

    一.折半插入排序(二分插入排序) 将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较,即可得到折半插入排序算法.在处理A[i]时,A[0]--A[i-1]已经按关键码值排好序.所谓折半比较,就是在插入A[i]时,取A[i-1/2]的关键码值与A[i]的关键码值进行比较,如果A[i]的关键码值小于A[i-1/2]的关键码值,则说明A[i]只能插入A[0]到A[i-1/2]之间,故可以在A[0]到A[i-1/2-1]之间继续使用折半比较:否则只能插入A[i-1/2]到A[i-1]之间,故可

  • Java数据结构及算法实例：插入排序 Insertion Sort

    /** * 选择排序的思想: * 每次循环前,数组左边都是部分有序的序列, * 然后选择右边待排元素,将其值保存下来 * 依次和左边已经排好的元素比较 * 如果小于左边的元素,就将左边的元素右移一位 * 直到和最左边的比较完成,或者待排元素不比左边元素小 */ package al; public class InsertionSort { public static void main(String[] args) { InsertionSort insertSort = new Insert

随机推荐