Java经典排序算法之插入排序

一、算法原理

插入排序法:所谓插入排序法乃是将一个数目插入该占据的位置。

假设我们输入的是 “53,27,36,15,69,  42” 我们从第二个数字开始,这个数字是27,我们的任务只要看看27有没有正确的位置,我们的做法是和这个数字左边的数字来比,因此我们比较27和53,27比53小,所以我们就交换27和53,原来的排列就变成了“27, 53, 36, 15, 69, 42 ”

接下来,我们看第3个数字有没有在正确的位置。这个数字是36,它的左边数字是53,36比53小,所以我们将36和53交换,排列变成了 “27,36, 53, 15, 69, 42 "我们必须继续看36有没有在正确的位置,36的左边是27,27比36小,36就维持不动了,这时候排序还是“27, 36, 53, 15, 69, 42 "。

再来看第四个数字,这个数字是15,我们将15和它左边的数字相比,都比15大,所以就将15一路往左移动,这时候排序变成了 “15, 27, 36, 53, 69, 42 ”。

再来看第五个数字,这个数字是69,我们将69和它左边的数字相比,都比69小,所以就69维持不动了,这时候排序变成了 “15, 27, 36, 53, 69, 42 ”

最后,我们检查第六个数字,这个数字是42,42必须往左移,一直移到42的左边是36为止,所以我们的排列就变成了 “15, 27, 36, 42 ,53, 69”排序因此完成了。

ps:读者也可以自己打开下面的链接,自己设定要排序的数组,进行排序演练
直接插入排序动画演示

所谓插入排序法,就是检查第i个数字,如果在它的左边的数字比它大,进行交换,这个动作一直继续下去,直到这个数字的左边数字比它还要小,就可以停止了。插入排序法主要的回圈有两个变数:i和j,每一次执行这个回圈,就会将第i个数字放到左边恰当的位置去。

二、算法描述

1、从第一个元素开始,该元素可以认为已经被排序。
2、取出下一个元素,在已经排序的元素序列中从后向前扫描。
3、如果该元素(已排序)大于新元素,则将该元素移到下一位置。
4、重复步骤3,直到找到已排序的元素小于或者大于新元素的位置。
5、将新元素插入到该位置。
6、重复步骤2。

三、效率分析

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况如下。
最好情况:序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。
最坏情况:序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。
直接插入排序属于稳定的排序,最坏时间复杂度为O(n^2),最好时间复杂度为O(n),空间复杂度为O(1)。
插入排序的赋值操作是比较操作的次数加上(n-1)次。
因此,插入排序不适合对于数据量比较大的排序应用。

四、代码实现

public class InsertSortTest {
  public static void InsertSort(int[] source) {
    int i, j;
    int insertNode;// 要插入的数据
    // 从数组的第二个元素开始循环将数组中的元素插入
    for (i = 1; i < source.length; i++) {
      // 设置数组中的第2个元素为第一次循环要插入的数据
      insertNode = source[i];
      j = i - 1;
      // 如果要插入的元素小于第j个元素,就将第j个元素向后移
      while ((j >= 0) && insertNode < source[j]) {
        source[j + 1] = source[j];
        j--;
      }
      // 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
      source[j + 1] = insertNode;
      System.out.print("第" + i + "趟排序:");
      printArray(source);
    }
  } 

  private static void printArray(int[] source) {
    for (int i = 0; i < source.length; i++) {
      System.out.print("\t" + source[i]);
    }
    System.out.println();
  } 

  public static void main(String[] args) {
    int source[] = new int[] { 53, 27, 36, 15, 69, 42 };
    System.out.print("初始关键字:");
    printArray(source);
    System.out.println("");
    InsertSort(source); 

    System.out.print("\n\n排序后结果:");
    printArray(source);
  } 

}

五、运行结果

初始关键字:   53 27 36 15 69 42 

第1趟排序: 27 53 36 15 69 42
第2趟排序: 27 36 53 15 69 42
第3趟排序: 15 27 36 53 69 42
第4趟排序: 15 27 36 53 69 42
第5趟排序: 15 27 36 42 53 69 

排序后结果: 15 27 36 42 53 69

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

(0)

相关推荐

  • 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直接插入排序示例

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

  • 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算法起步之插入排序实例

    趁着过年这段时间,我将算法导论这本书看了一遍,感觉受益匪浅.着这里也根据算法导论中所涉及到的算法用java实现了一遍.第一篇我们就从排序开始,插入排序的原理很简单,就像我们玩扑克牌时一样.如果手里拿的牌比他前一张小,就继续向前比较,知道这张牌比他前面的牌打时候就可以插在他的后面.当然在计算机中我们相应的也需要将对比过的牌向后移一位才可以.这里直接给出算法,相信很多程序员都感觉有些程序比我们的自然语言都要好理解. 复制代码 代码如下: public class Sort { public void

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

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

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

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

  • Java实现插入排序实例

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

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

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

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

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

  • 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];         

随机推荐