疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

直接插入排序(JAVA)


 

   

  1.直接插入排序思路

  (1)思想:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

  (2)做法:第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

  2.直接插入排序详细分析

  设需排序的数组 a={34,23,12,43 , 22 , 11 , 45 , 32,33 , 11}

  (1)首先对序列a进行一个循环,表示依次需要插入的数据(从第二个数据开始);

  (2)对于(1)中的每次循环再嵌套一个循环,此循环从第一个数据开始,到待排序的前一个数据,用来寻找待排序数据要插入的位置。

  3.算法性能

  (1)最坏时间复杂性为O(n^2)

  (2)空间复杂度:O(1)

  (3)稳定性:稳定

  4.算法实现(java)(递减)

  public static int[] InsertSort(int[] a){

  int n = a.length;

  if(n<=1) return a;

  for(int i = 1; i < n; i++){

  for(int j = i;j>0&&a[j]>a[j-1];j--){

  int temp = a[j];//此处每次交换都新建了一个位置,显然比较浪费资源,因此需要改进

  a[j] = a[j-1];

  a[j-1] = temp;

  }

  }

  return a;

  }

  改进后的代码

  public static int[] InsertSort(int[] a){

  int n = a.length;

  if(n<=1) return a;

  for(int i = 1; i < n; i++){

  if(a[i]>a[i-1]){

  int temp = a[i]; //此处将a[i]存储起来,就不要每次都建一个零时变量了

  int j = 0;

  for(j = i;j>0&&temp>a[j-1];j--){

  a[j] = a[j-1];

  }

  a[j] = temp;

  }

  }

  return a;

  }

  记录一个简单的知识点—for(a;b;c)循环中a,b,c的运行时间和顺序

  先执行a

  在判断b是否为真,若为真

  执行循环体,

  执行c

  然后再次判断b是否为真,若为真

  执行循环体

  执行c

  。。。

  直到b为假,跳出循环