Java 直接插入排序的三种实现

直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

设数组为a[0…n-1]。

1. 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1

2. 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。

3. i++并重复第二步直到i==n-1。排序完成。

下面给出严格按照定义书写的代码（由小到大排序）：

void Insertsort1(int a[], int n)
{
 int i, j, k;
 for (i = 1; i < n; i++)
 {
  //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
  for (j = i - 1; j >= 0; j--)
   if (a[j] < a[i])
    break;
  //如找到了一个合适的位置
  if (j != i - 1)
  {
   //将比a[i]大的数据向后移
   int temp = a[i];
   for (k = i - 1; k > j; k--)
    a[k + 1] = a[k];
   //将a[i]放到正确位置上
   a[k + 1] = temp;
  }
 }
}

这样的代码太长了，不够清晰。现在进行一下改写，将搜索和数据后移这二个步骤合并。即每次a[i]先和前面一个数据a[i-1]比较，如果a[i] > a[i-1]说明a[0…i]也是有序的，无须调整。否则就令j=i-1,temp=a[i]。然后一边将数据a[j]向后移动一边向前搜索，当有数据a[j]<a[i]时停止并将temp放到a[j + 1]处。

void Insertsort2(int a[], int n)
{
 int i, j;
 for (i = 1; i < n; i++)
  if (a[i] < a[i - 1])
  {
   int temp = a[i];
   for (j = i - 1; j >= 0 && a[j] > temp; j--)
    a[j + 1] = a[j];
   a[j + 1] = temp;
  }
}

再对将a[j]插入到前面a[0…j-1]的有序区间所用的方法进行改写，用数据交换代替数据后移。如果a[j]前一个数据a[j-1] > a[j]，就交换a[j]和a[j-1]，再j--直到a[j-1] <= a[j]。这样也可以实现将一个新数据新并入到有序区间。

void Insertsort3(int a[], int n)
{
 int i, j;
 for (i = 1; i < n; i++)
  for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
   Swap(a[j], a[j + 1]);
}

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持我们！

赞 (0)

相关推荐

  • 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实现直接插入排序和折半插入排序算法示例

    直接插入排序​ 1 排序思想: 将待排序的记录Ri插入到已经排好序的记录R1,R2,--,R(N-1)中. 对于一个随机序列而言,就是从第二个元素开始,依次将这个元素插入到它之前的元素中的相应位置.它之前的元素已经排好序. 第1次排序:将第2个元素插入到前边的有序列表(此时前边只有一个元素,当然是有序的),之后,这个序列的前2个元素就是有序的了. 第2次排序:将第3个元素插入到前边长度为2的有序列表,使得前2个元素是有序的. 以此类推,直到将第N个元素插入到前面长度为(N-1)的有序列表中. 2

  • java直接插入排序示例

    java直接插入排序示例

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

  • 详解直接插入排序算法与相关的Java版代码实现

    详解直接插入排序算法与相关的Java版代码实现

    直接插入排序 直接插入排序的思路很容易理解,它是这样的: 1.把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的. 2.从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置. 3.重复上述过程直到最后一个元素被插入有序子数组中. 4.排序完成. 示例: 思路很简单,但代码并非像冒泡排序那么好写.首先,如何判断合适的位置?大于等于左边.小于等于右边?不行,很多边界条件需要考虑,而且判断次数太多.其次,数组中插入元素,必然需要移动大量元素,如何控制它们

  • Java 直接插入排序的三种实现

    直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止. 设数组为a[0-n-1]. 1. 初始时,a[0]自成1个有序区,无序区为a[1..n-1].令i=1 2. 将a[i]并入当前的有序区a[0-i-1]中形成a[0-i]的有序区间. 3. i++并重复第二步直到i==n-1.排序完成. 下面给出严格按照定义书写的代码(由小到大排序): void Insertsort1(int a[

  • 详解Java实现多线程的三种方式

    本文实例为大家分享了Java实现多线程的三种方式,供大家参考,具体内容如下 import java.util.concurrent.Callable; import java.util.concurrent.FutureTask; public class Main { public static void main(String[] args) { //方法一:继承Thread int i = 0; // for(; i < 100; i++){ // System.out.println(T

  • 基于java解析JSON的三种方式详解

    本文实例分析了基于java解析JSON的三种方式.分享给大家供大家参考,具体如下: 一.什么是JSON? JSON是一种取代XML的数据结构,和xml相比,它更小巧但描述能力却不差,由于它的小巧所以网络传输数据将减少更多流量从而加快速度. JSON就是一串字符串 只不过元素会使用特定的符号标注. {} 双括号表示对象 [] 中括号表示数组 "" 双引号内是属性或值 : 冒号表示后者是前者的值(这个值可以是字符串.数字.也可以是另一个数组或对象) 所以 {"name"

  • java定义数组的三种类型总结

    三种定义数组的格式如下: int[] arr1=new int[10]; int[] arr2={1,2,3,6}; int[] arr3=new int[]{1,2,3,4,5,6,7,22}; 注意:数组的length是一个属性,而字符串的length()是一个方法了!!!虽然都是求的他们各自的长度 package 第四天; public class 数组 { public void showArray(int[] arr) { for(int i=0;i<arr.length;i++) S

  • java 字符串分割的三种方法(总结)

    最近在项目中遇到一个小问题,一个字符串分割成一个数组,类似String str="aaa,bbb,ccc"; 然后以","为分割符,将其分割成一个数组,用什么方法去实现呢? 第一种方法: 可能一下子就会想到使用split()方法,用split()方法实现是最方便的,但是它的效率比较低 第二种方法: 使用效率较高的StringTokenizer类分割字符串,StringTokenizer类是JDK中提供的专门用来处理字符串分割子串的工具类.它的构造函数如下: publ

  • java 字符串截取的三种方法(推荐)

    众所周知,java提供了很多字符串截取的方式.下面就来看看大致有几种. 1.split()+正则表达式来进行截取. 将正则传入split().返回的是一个字符串数组类型.不过通过这种方式截取会有很大的性能损耗,因为分析正则非常耗时. String str = "abc,12,3yy98,0"; String[] strs=str.split(","); for(int i=0,len=strs.length;i<len;i++){ System.out.pri

  • Java字符串写入文件三种方式的实现

     Java字符串写入文件三种方式的实现 1.使用FileWriter String str="hello world!"; FileWriter writer; try { writer = new FileWriter("E:/token.txt"); writer.write(str); writer.flush(); writer.close(); } catch (IOException e) { e.printStackTrace(); } 2.使用Fil

  • 浅谈Java实体对象的三种状态以及转换关系

    浅谈Java实体对象的三种状态以及转换关系

    最新的Hibernate文档中为Hibernate对象定义了四种状态(原来是三种状态,面试的时候基本上问的也是三种状态),分别是:瞬时态(new, or transient).持久态(managed, or persistent).游状态(detached)和移除态(removed,以前Hibernate文档中定义的三种状态中没有移除态),如下图所示,就以前的Hibernate文档中移除态被视为是瞬时态. 瞬时态:当new一个实体对象后,这个对象处于瞬时态,即这个对象只是一个保存临时数据的内存区

  • Java实现克隆的三种方式实例总结

    Java实现克隆的三种方式实例总结

    本文实例讲述了Java实现克隆的三种方式.分享给大家供大家参考,具体如下: 1.浅复制(浅克隆)这种浅复制,其实也就是把被复制的这个对象的一些变量值拿过来了.最后生成student2还是一个新的对象. public class CloneTest1 { public static void main(String[] args) throws Exception { Student1 student = new Student1(); student.setAge(24); student.se

  • JAVA字符串反转的三种方法

    方法一:使用StringBuilder import java.util.Scanner; public class StrReversal { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); System.out.println(new StringBuilder(str).reverse()); } } 方法二

随机推荐