当前位置：首页 > 资讯 > 技术文档

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

时间：2020-01-31 16:01 编辑：来源：阅读：
扫一扫，手机访问

摘要：Java经典排序算法之插入排序

[b]一、算法原理 [/b] 插入排序法：所谓插入排序法乃是将一个数目插入该占据的位置。假设我们输入的是 “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”排序因此完成了。 [img]http://files.jb51.net/file_images/article/201704/201745150817986.jpg?20173515833[/img] ps:读者也可以自己打开下面的链接，自己设定要排序的数组，进行排序演练直接插入排序动画[url=http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/insertsort.htm]演示[/url] 所谓插入排序法，就是检查第i个数字，如果在它的左边的数字比它大，进行交换，这个动作一直继续下去，直到这个数字的左边数字比它还要小，就可以停止了。插入排序法主要的回圈有两个变数：i和j，每一次执行这个回圈，就会将第i个数字放到左边恰当的位置去。 [b]二、算法描述[/b] 1、从第一个元素开始，该元素可以认为已经被排序。 2、取出下一个元素，在已经排序的元素序列中从后向前扫描。 3、如果该元素（已排序）大于新元素，则将该元素移到下一位置。 4、重复步骤3，直到找到已排序的元素小于或者大于新元素的位置。 5、将新元素插入到该位置。 6、重复步骤2。 [b]三、效率分析[/b] 如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况如下。最好情况：序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。直接插入排序属于稳定的排序，最坏时间复杂度为O(n^2)，最好时间复杂度为O(n)，空间复杂度为O(1)。插入排序的赋值操作是比较操作的次数加上(n-1)次。因此，插入排序不适合对于数据量比较大的排序应用。 [b]四、代码实现[/b]

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); 
  } 
 
}

[b]五、运行结果[/b]

初始关键字：   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语言Lang包下常用的工具类介绍
下一篇：java实现获取用户的MAC地址

资讯排行榜
更多>>